LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Design HashMap

Bikin HashMap pakai bucket dan tangani collision lewat separate chaining.

Di artikel ini 4 bagian

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

Direct indexing juga bisa dipakai dengan batasan soal ini. Key 5 disimpan di index 5:

javascript
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:

  1. Chaining: Simpan list pasangan key value di tiap bucket
  2. 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

javascript
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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan