Solusi Leetcode - Design HashMap

Bikin HashMap sendiri dari nol awalnya kedengeran menakutkan. Lookup array aja nggak cukup: key harus dipetakan ke bucket, dan beberapa key bisa jatuh ke bucket yang sama. Saya pilih chaining karena cara ini menyimpan pasangan key value yang collision di tempat yang sama dan bikin operasinya gampang diikuti.

Operasi dan batasan

Implementasinya mendukung tiga operasi:

• put(key, value): Masukkan atau update pasangan key value
• get(key): Kembalikan value untuk sebuah key, atau -1 kalau nggak ketemu
• remove(key): Hapus pasangan key value

Key dan value-nya berkisar dari 0 sampai 10^6, dengan paling banyak 10^4 operasi.

Ide pertama saya adalah direct indexing. Kalau key-nya 5, simpan value-nya 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

Sebagai gantinya, saya petakan tiap key ke array bucket yang lebih kecil. Hash function harus menghasilkan index bucket yang valid, menyebarkan key ke berbagai bucket, dan murah untuk dihitung. Pilihan yang simpel adalah key % bucketSize. Pilihan ukuran bucket memengaruhi gimana key dipetakan ke bucket.

Dua key bisa menghasilkan index yang sama. Collision itu butuh aturan yang jelas:

1. Chaining: Simpan list pasangan key value di tiap bucket
2. Open Addressing: Cari slot kosong berikutnya

Saya 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).

Mengimplementasikan struktur ini bikin peran hash function dan aturan collision jadi konkret. Collision nggak bisa dihindari, dan ukuran bucket memengaruhi kerja lookup sekaligus pemakaian memori.

Hash function memilih bucket. Chaining menyimpan pasangan dengan index bucket yang sama, dan jumlah bucket memengaruhi rata-rata biaya pencarian.