Aku pakai array berisi bucket untuk HashMap ini. Sebuah key memilih bucket, dan setiap bucket menyimpan list pasangan key dan value. Kalau dua key memilih bucket yang sama, list itu menyimpan keduanya.
Operasi dan batasan
Implementasinya mendukung tiga operasi:
put(key, value): Masukkan atau update pasangan key valueget(key): Kembalikan value untuk sebuah key, atau -1 kalau nggak ketemuremove(key): Hapus pasangan key value
Key dan value-nya berkisar dari 0 sampai 10^6, dengan paling banyak 10^4 operasi.
Direct indexing juga bisa dipakai dengan batasan soal ini. Key 5 disimpan di index 5:
class MyHashMapNaive {
constructor() {
this.data = new Array(1000001).fill(-1);
}
put(key, value) {
this.data[key] = value;
}
get(key) {
return this.data[key];
}
remove(key) {
this.data[key] = -1;
}
}
Ini jalan untuk batasan tadi, tapi mengalokasikan sejuta slot walaupun cuma ada beberapa key.
Bucket dan collision
Hash function memetakan setiap key ke index bucket. Key perlu tersebar ke berbagai bucket, dan perhitungannya nggak boleh mahal. Implementasi ini memakai key % bucketSize.
Dua key bisa menghasilkan index yang sama. Collision itu butuh aturan yang jelas:
- Chaining: Simpan list pasangan key value di tiap bucket
- Open Addressing: Cari slot kosong berikutnya
Aku pilih chaining. Tiap bucket adalah array berisi pasangan key dan value-nya. Collision berarti harus ada pencarian di dalam bucket itu.
Implementasi dengan chaining
class MyHashMap {
constructor() {
this.size = 1000; // Number of buckets
// Each bucket is an array for chaining
this.buckets = new Array(this.size).fill(null).map(() => []);
}
// Hash function: maps key to bucket index
_hash(key) {
return key % this.size;
}
// Insert or update a key-value pair
put(key, value) {
const hashKey = this._hash(key);
const bucket = this.buckets[hashKey];
// Check if key already exists in this bucket
for (let i = 0; i < bucket.length; i++) {
const [k, v] = bucket[i];
if (k === key) {
// Update existing key
bucket[i] = [key, value];
return;
}
}
// Key doesn't exist, add new pair
bucket.push([key, value]);
}
// Get value for a key
get(key) {
const hashKey = this._hash(key);
const bucket = this.buckets[hashKey];
// Search through the bucket
for (let [k, v] of bucket) {
if (k === key) {
return v;
}
}
// Key not found
return -1;
}
// Remove a key-value pair
remove(key) {
const hashKey = this._hash(key);
const bucket = this.buckets[hashKey];
// Find and remove the key
for (let i = 0; i < bucket.length; i++) {
const [k, v] = bucket[i];
if (k === key) {
bucket.splice(i, 1);
return;
}
}
}
}
Alur operasi dan tradeoff
Method _hash(key) memetakan key ke index dari 0 sampai 999. put(key, value) mencari di bucket itu lalu meng-update pasangan yang udah ada atau menambahkan pasangan baru. get(key) mencari di bucket yang sama dan mengembalikan value yang tersimpan atau -1. remove(key) menghapus pasangan yang cocok kalau ada.
Dengan n pasangan tersimpan dan m bucket, put, get, dan remove rata-rata butuh waktu O(1 + n/m) kalau key tersebar merata. Kode ini mematok m di 1.000 dan nggak melakukan resize. Jadi, rata-rata panjang bucket ikut tumbuh seiring n. Pencarian di bucket butuh O(n) kalau semua key memilih satu bucket yang sama. Total storage-nya O(n + m).
Jumlah bucket yang tetap menjadi batas implementasi ini. Semakin banyak pasangan yang disimpan, semakin panjang pencarian di dalam bucket. Untuk menjaga pencariannya tetap pendek, array perlu diperbesar dan isinya dibagi ulang.

Memuat komentar...