Tabel hash

Dengan 47 disimpan dalam tabel berisi 7 bucket, komputer langsung menuju bucket 47 mod 7 = 5 alih-alih mencari di seluruh tabel.

Mengubah kunci menjadi posisi

Sejauh ini, mencari nilai berarti menelusuri: paling banyak n langkah pada array yang tidak terurut atau linked list. Padahal array bisa mencapai posisi mana pun dalam satu langkah. Bagaimana kalau kuncinya sendiri yang memberi tahu posisinya? Kalau kunci-kuncimu bilangan cacah kecil, misalnya nomor siswa dari 0 sampai 99, kamu bisa menyimpan array berisi 100 sel dan menaruh siswa k di sel k. Catatan MIT menyebutnya direct access array (array akses langsung). Cara ini gagal kalau kemungkinan kuncinya sangat banyak, seperti nomor telepon atau kata, karena kamu tidak mampu menyediakan satu sel untuk setiap kunci yang mungkin.

Fungsi hash mengatasinya dengan memampatkan kunci apa pun ke rentang posisi yang kecil, 0 sampai m − 1. Fungsi sederhana untuk bilangan cacah adalah h(k) = k mod m, yaitu sisa pembagian oleh m. Array berisi m sel itu adalah tabel hash, dan sel-selnya sering disebut bucket (wadah). Untuk menyimpan 47 dengan m = 7, hitung 47 mod 7 = 5 lalu taruh di bucket 5. Untuk mencari 47 nanti, hitung hal yang sama dan lihat hanya di bucket 5.

Tabrakan dan chaining

Ada masalah. Dengan 7 bucket dan lebih dari 7 kemungkinan kunci, sebagian kunci pasti berbagi bucket: 12, 33, dan 47 semuanya bersisa 5. Ini disebut tabrakan (collision), dan catatan MIT menunjukkan bahwa tabrakan tidak bisa dihindari, menurut prinsip sarang merpati. Obat yang biasa adalah chaining (perantaian): setiap bucket menyimpan list kecil, yaitu rantai, berisi setiap kunci yang di-hash ke sana. Mencari 47 lalu memakan 1 langkah untuk hash ditambah satu perbandingan untuk setiap kunci yang diperiksa di rantai 5. Kalau 12 dan 33 ada di depannya, jadinya 1 + 3 = 4 langkah.

Seberapa panjang rantainya? Kalau kuncinya tersebar merata, setiap rantai berisi sekitar n/m kunci, bilangan yang disebut faktor muatan (load factor). Buat m kira-kira sebesar n, maka rantainya tetap pendek, sehingga mencari, menyisipkan, dan menghapus rata-rata memakan jumlah langkah yang konstan. Bahayanya adalah sebaran yang buruk. Kalau setiap kunci di-hash ke bucket yang sama, satu rantai memuat semua n kunci dan tabelnya tidak lebih baik daripada linked list. Di laboratorium, atur 7 bucket lalu sisipkan 14, 21, dan 28: semuanya mendarat di bucket 0.

Tabel hash di JavaScript

Kamu jarang menulis tabel hash sendiri, karena JavaScript punya Map dan Set. Spesifikasi ECMAScript menyatakan keduanya "harus diimplementasikan dengan tabel hash atau mekanisme lain yang rata-rata memberikan waktu akses sublinear terhadap banyaknya elemen". Dengan kata lain, map.get(key) dan set.has(x) harus lebih cepat daripada menelusuri seluruh koleksi. MDN menambahkan bahwa Map menyimpan kunci sesuai urutan penyisipan dan, tidak seperti objek biasa, tidak berisi kunci bawaan yang bisa bertabrakan dengan kuncimu.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, tanpa menelusuri list
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true