Hashing
| English | Bahasa Indonesia |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | fungsi hash |
| key/kiː/ | key |
| address/əˈdres/ | alamat |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | deterministik |
| collision/kəˈlɪʒn/ | tabrakan |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | probing linear |
| chaining/ˈtʃeɪnɪŋ/ | pengantingan |
| load factor/ləʊd ˈfæktə/ | faktor beban |
Menemukan satu baris dalam lima puluh juta tanpa mencari
- Kasir supermarket memindai barcode dan harga muncul sebelum tangan Anda meninggalkan barang. File produk memegang lima puluh juta baris.
- Tidak ada yang mencarinya. Nomor barcode melewati perhitungan singkat yang menghasilkan posisi, dan komputer membaca posisi itu: satu baca, tanpa perbandingan, waktu yang sama apakah file berisi lima puluh baris atau lima puluh juta.
- Perhitungan itu adalah fungsi hash, dan seluruh ide bergantung padanya: jangan simpan data di tempat yang muat, simpan di tempat kunci miliknya sendiri mengatakan ia berada.
- Pelajaran ini tentang algoritma hashing, apa yang terjadi ketika dua kunci menginginkan slot yang sama, dan bagaimana cara mencari dan menyisipkan.
Fungsi hash
- Fungsi hash, atau algoritma hashing, mengambil kunci rekaman dan menghasilkan alamat di mana rekaman disimpan.
- Yang bagus itu cepat, deterministik (kunci yang sama selalu menghasilkan alamat yang sama), dan menyebarkan kunci merata di seluruh slot yang tersedia.
- Untuk $N$ slot, tiga hal yang diharapkan oleh silabus adalah: modulo,
address ← key MOD N; folding, pisahkan kunci menjadi bagian-bagian, jumlahkan, lalu MOD $N$; string hash, jumlahkan kode karakter, lalu MOD $N$.
Fungsi hash:
Fungsi hash memetakan kunci ke alamat, memungkinkan pencarian langsung hampir instan.
Apa yang membuat fungsi hash menjadi fungsi yang baik? Pilih semua yang berlaku.
Cepat, deterministik, dan tersebar merata. Tidak ada hash realistis yang menghindari tabrakan sepenuhnya, oleh karena itu setiap desain mencakup strategi resolusi.
Contoh terpecah: terapkan setiap algoritma
- Sebuah file memiliki 10 slot, bernomor 0 hingga 9. Di mana kunci 4517 akan masuk?
- Modulo: $4517 \bmod 10 = 7$, jadi slot 7.
- Folding berpasangan: $45 + 17 = 62$, kemudian $62 \bmod 10 = 2$, jadi slot 2.
- Dan kunci "CAB" melalui string hash? $67 + 65 + 66 = 198$, kemudian $198 \bmod 10 = 8$, jadi slot 8.
- Tunjukkan perhitungannya. Nilai diberikan untuk perhitungan tersebut, bukan hanya nomor slotnya.
Menggunakan hash modulo address ← key MOD N dengan key = 27 dan N = 10, alamat apa yang dihasilkan?
27 MOD 10 = 7 (sisa bagi saat 27 dibagi 10).
Tabel memiliki 10 slot. Menggunakan lipatan berpasangan pada key 4517 (tambahkan 45 dan 17, lalu MOD 10), slot manakah yang dituju?
45 + 17 = 62, dan 62 MOD 10 = 2. Key yang sama di bawah hash modulo akan masuk ke slot 7.
Tabrakan
- Tabrakan terjadi ketika dua kunci berbeda dihash ke alamat yang sama. Dengan fungsi hash apa pun dan file yang realistis, tabrakan pasti terjadi, sehingga strategi menanganinya merupakan bagian dari desain, bukan pertimbangan terakhir.
- Linear probing menempatkan rekaman di slot kosong berikutnya, melingkar kembali ke awal di akhir tabel. Sederhana, tetapi rekaman menumpuk: area penuh membesar dan setiap kunci yang mendarat di dalamnya membutuhkan waktu lebih lama.
- Chaining menjadikan setiap slot sebagai kepala dari daftar taut (linked list) dari semua rekaman yang dihash ke sana. Tidak ada penumpukan, tetapi memerlukan memori tambahan untuk pointer dan perjalanan singkat sepanjang daftar.
- Rehashing menerapkan fungsi hash kedua untuk menemukan slot lain, menyebarkan kunci dengan lebih baik dengan mengorbankan lebih banyak komputasi.
Tabrakan terjadi ketika:
Dua key yang memetakan ke slot yang sama adalah tabrakan; hal ini harus diselesaikan melalui probing, pengantian, atau rehashing.
Pasangkan setiap ide penanganan tabrakan dengan fungsinya.
Tabrakan diselesaikan dengan pengantian atau probing; mempertahankan faktor beban rendah menjaga pencarian tetap mendekati O(1).
Pencarian dan penyisipan
- Untuk menyisipkan: hash kunci. Jika slot kosong, tulis rekaman di sana. Jika tidak, ikuti strategi penyelesaian, slot kosong berikutnya untuk linear probing, atau depan daftar slot tersebut untuk chaining.
- Untuk mencari: hash kunci dan baca slot itu. Jika kunci yang tersimpan cocok, rekaman ditemukan. Jika tidak, ikuti strategi yang sama, hingga kunci cocok atau slot kosong membuktikan rekaman tidak ada dalam file.
- Kedua operasi menggunakan strategi yang sama. Pencarian yang berhenti pada ketidakcocokan pertama akan melewatkan setiap rekaman yang pernah digeser oleh tabrakan.
Contoh terpecah: telusuri tabrakan
- Sebuah tabel 10 slot menggunakan
key MOD 10dengan linear probing. Sisipkan 23, 33, 43 secara berurutan, lalu cari 43. - 23 dihash ke 3; slot 3 kosong, jadi masuk ke sana. 33 dihash ke 3; slot 3 sudah diisi oleh 23, jadi linear probing memasukkannya ke slot 4. 43 dihash ke 3; slot 3 dan 4 sudah terisi, jadi masuk ke slot 5.
- Mencari 43: hash ke 3, baca slot 3, kuncinya 23, tidak cocok, jadi lanjutkan probe; slot 4 berisi 33, tidak cocok; slot 5 berisi 43, ditemukan, setelah tiga kali baca.
- Rangkaian tiga yang membesar itu adalah penumpukan yang disebabkan oleh linear probing.
Hash setiap kunci langsung ke ember (bucket)
Fungsi hash mengubah kunci menjadi nomor ember, sehingga Anda melompat langsung ke rekaman bukan mencari. Ketika dua kunci mendarat di ember yang sama itu adalah tabrakan — mereka berantai bersama di ember tersebut.
Saat mencari dalam tabel hash, rekaman tersebut tidak ada di file begitu saja setelah slot pertama yang dibaca memegang key yang berbeda.
Rekaman mungkin telah dipindahkan akibat tabrakan. Pencarian mengikuti strategi resolusi yang sama hingga ditemukan kecocokan atau slot kosong.
Faktor beban
- Faktor beban adalah jumlah rekaman dibagi dengan jumlah slot. Ini adalah satu angka yang memprediksi seberapa baik tabel berkinerja.
- Di bawah sekitar 70% rata-rata pencarian mendekati satu kali baca. Di atasnya, urutan probe memanjang tajam dan kinerja menurun menuju pencarian linier.
- Solusinya adalah membuat tabel lebih besar dan melakukan rehashing pada setiap rekaman ke dalamnya, itulah sebabnya tabel hash dibuat berdasarkan data yang akan ditampungnya, bukan data yang dimilikinya hari ini.
Tabel 10 slot menggunakan key MOD 10 dengan probing linear. Setelah memasukkan 23, 33, dan 43 secara berurutan, slot manakah yang menyimpan 43?
Ketiganya dihash ke 3. 23 mengambil slot 3, 33 diprobing ke 4, dan 43 ke 5. Tiga key berurutan adalah tepat klasterisasi yang disebabkan oleh probing linear.
⟦⟧ Nilai yang sering terlewat
- Tabrakan adalah dua kunci, satu alamat. Ini bukan kesalahan dan bukan rekaman hilang; ini adalah kasus normal yang ditangani oleh strategi.
- Pencarian harus mengikuti strategi resolusi yang sama seperti penyisipan, dan berhenti hanya pada kecocokan atau slot kosong.
- Linear probing menumpuk; chaining membiayai memori. Berikan trade-off-nya, bukan hanya mekanismenya.
- Faktor beban adalah rekaman dibagi dengan slot, dan ambangnya sekitar 70%, bukan 100%.
Untuk menjaga pencarian hash tetap cepat, faktor beban (rekaman ÷ slot) harus dijaga:
Faktor beban yang lebih rendah berarti lebih sedikit tabrakan, sehingga pencarian tetap dekat dengan O(1).
Anda telah memahaminya
- sebuah fungsi hash mengubah kunci menjadi alamat: cepat, deterministik, tersebar merata; modulo, folding, dan string hash adalah tiga yang perlu diketahui
- sebuah tabrakan adalah dua kunci dihash ke satu alamat, diselesaikan dengan linear probing (slot kosong berikutnya, menumpuk), chaining (daftar taut per slot, lebih banyak memori) atau rehashing
- penyisipan dan pencarian keduanya mengikuti strategi yang sama; pencarian berakhir pada kecocokan atau slot kosong
- jaga faktor beban, rekaman dibagi slot, di bawah sekitar 70% untuk pencarian hampir satu kali baca