Hash Map / Object — Struktur Data

Hash Map (di JavaScript: Object dan Map) menyimpan data sebagai pasangan key-value dengan pencarian super cepat. Bagaimana cara kerjanya? Key diproses oleh…

Hash map menyimpan data sebagai pasangan key dan value: key adalah nama yang dipakai untuk mencari, value adalah isinya. Kelebihannya, mengambil value lewat key-nya rata-rata cuma butuh satu langkah, sebanyak apa pun datanya. Mirip rak surat yang dibagi per huruf awal nama: surat untuk Budi langsung masuk kotak B, jadi mencarinya cukup membuka satu kotak.

🧪 Tebakan cepat: dua key berbeda jatuh ke kotak yang sama. Apa yang terjadi: key lama ditimpa, muncul error, atau dua-duanya disimpan? Tebak dulu, jawabannya ada di bagian "Collision: dua key, satu bucket".

Key, value, dan bucket

Di JavaScript, hash map yang siap pakai bernama Map:

const stok = new Map();
stok.set("apel", 5);
stok.set("melon", 2);
stok.set("anggur", 8);

console.log(stok.get("melon")); // 2
console.log(stok.has("jeruk")); // false
console.log(stok.get("jeruk")); // undefined
stok.delete("anggur");
console.log(stok.size);         // 2

Di dalamnya, hash map punya deretan kotak bernomor yang disebut bucket, misalnya 8 bucket. Sebuah fungsi hash mengubah key jadi angka, lalu sisa bagi angka itu dengan 8 jadi nomor bucket-nya:

Key Hasil fungsi hash Sisa bagi 8 Masuk bucket
"apel" 3000598 6 6
"melon" 103780019 3 3
"anggur" 2881786154 2 2

Waktu get("melon"), angka yang sama dihitung lagi, jadi langsung ke bucket 3 tanpa membuka bucket lain. Itu sebabnya hash map disebut O(1): jumlah langkahnya gak ikut bertambah walaupun datanya makin banyak.

Collision: dua key, satu bucket

stok.set("pepaya", 4) juga jatuh ke bucket 6, sama dengan "apel". Dua key berbeda di bucket yang sama disebut collision (tabrakan). Gak ada yang ditimpa dan gak ada error: dua-duanya disimpan di bucket 6 sebagai daftar pendek. Cara ini disebut chaining. Itu jawaban tebakan tadi.

get("pepaya") lalu membuka bucket 6 dan mengecek isinya satu per satu: "apel" bukan, "pepaya" ketemu. Jadi O(1) itu rata-rata, bukan jaminan:

Menghitung dengan Map

const belanja = ["apel", "melon", "apel"];
const jumlah = new Map();

for (const buah of belanja) {
  jumlah.set(buah, (jumlah.get(buah) || 0) + 1);
}

console.log(jumlah.get("apel"));  // 2
console.log(jumlah.get("melon")); // 1
console.log(jumlah.get("jeruk")); // undefined
console.log(jumlah.size);         // 2

Object juga dipakai sebagai hash map

Object biasa juga menyimpan pasangan key dan value: const harga = { apel: 5000 }, lalu harga["melon"] = 12000 dan harga["apel"]. Bedanya dengan Map:

Object Map
Key selalu teks: obj[1] dan obj["1"] key yang sama tipe apa saja, angka atau object juga bisa
Jumlah isi Object.keys(obj).length map.size
Urutan key berupa angka diurutkan dulu, sisanya urutan masuk selalu urutan masuk

Pakai object untuk data dengan nama field yang tetap, misalnya { nama, umur }. Pakai Map kalau key-nya berubah-ubah, sering ditambah dan dihapus, atau untuk menghitung.

⚠️ Jebakan yang sering ketemu

💡 Hash map sering mengubah dua loop jadi satu. Mencari "sudah pernah lihat nilai ini?" dengan dua loop bersarang butuh sekitar sejuta perbandingan untuk 1.000 data. Dengan satu loop yang menyimpan nilai ke Map dan mengecek pakai has, cukup sekitar 1.000 langkah.

TL;DR: Hash map menyimpan pasangan key dan value. Fungsi hash mengubah key jadi nomor bucket, jadi get, set, has dan delete rata-rata O(1). Dua key di bucket yang sama disebut collision, dan dua-duanya tetap disimpan (chaining). Kalau terlalu banyak key menumpuk di satu bucket, waktunya turun sampai O(n). Di JavaScript pakai new Map(): set dengan key yang sudah ada mengganti value-nya, size menghitung key yang berbeda. Menghitung: map.set(key, (map.get(key) || 0) + 1). Object juga key-value, tapi key-nya selalu teks.

Yang akan kamu pelajari