Tabel hash
Tabel Hash: pencarian cepat
- Tabel hash menyimpan item sehingga Anda dapat menemukannya sangat cepat — biasanya dalam satu langkah.
- Ini adalah daftar slot. Fungsi hash mengubah kunci menjadi nomor slot.
- Daripada mencari setiap item, Anda langsung melompat ke slot tempat kunci tersebut berada.
Fungsi Hash
- Fungsi hash menerima kunci dan mengembalikan indeks slot dari
0hinggasize - 1. - Kunci yang sama selalu menghasilkan slot yang sama, sehingga Anda dapat menemukannya lagi nanti.
- Satu contoh sederhana: jumlahkan kode karakter, lalu ambil
% sizeagar tetap dalam rentang.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Tabrakan
- Dua kunci yang berbeda dapat dihash ke slot yang sama. Itu disebut tabrakan.
- Tabel memiliki slot terbatas, sehingga tabrakan tak terhindarkan saat tabel terisi.
- Kita memerlukan aturan tentang apa yang harus dilakukan jika slot yang diinginkan sudah terisi.
Pencarian Linear
- Pencarian linear: jika sebuah slot penuh, coba slot berikutnya, lalu berikutnya lagi, dengan melingkari kembali.
- Terus melangkah
(slot + 1) % sizesampai menemukan slot yang kosong. - Di bawah ini,
AdanFkeduanya menginginkan slot 0, sehinggaFdidorong ke slot 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Mencari Kunci
- Untuk menemukan kunci: hash kunci tersebut, lalu cari maju, membandingkan setiap slot dengan kunci.
- Berhenti dan kembalikan indeks ketika menemukannya.
- Jika Anda mencapai slot kosong (atau memeriksa setiap slot), kunci tidak ada di sana — kembalikan
-1.
Mengapa Tabel Hash Cepat
- Dengan sedikit tabrakan, sisipan dan pencarian memakan waktu sekitar satu langkah — ini kita sebut
O(1). - Seiring tabel terisi, pencarian menjadi lebih panjang, jadi bijak untuk menyisakan beberapa slot kosong.
- Dalam kasus terburuk (semua tabrakan) kecepatannya melambat menjadi pemindaian linear,
O(n).
Kesalahan umum
- Fungsi hash memetakan kunci ke indeks dalam tabel.
- Dua kunci dapat bertabrakan pada indeks yang sama. Tangani masalah ini, seperti yang dilakukan dalam pelajaran ini, dengan peng probing linear; rantai adalah metode umum lainnya.
Sekarang Anda coba
- Bangun tiga bagian: fungsi hash, sisipan dengan pencarian, dan pencarian.
- Setiap tugas memeriksa fungsi Anda pada kasus tabrakan dan pelingkaran kembali.
- Tekan Cek jawaban untuk mengujinya.
Hashing ke dalam bak
Fungsi hash mengirimkan setiap kunci ke bak; benturan membentuk rantai.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis hash_key(key, size). Jumlahkan kode karakter dari key (gunakan ord(ch)) dan kembalikan total % size, sehingga hasilnya adalah slot dari 0 hingga size - 1. Contoh: hash_key("AB", 10) menghasilkan (65 + 66) % 10 = 1. String kosong menghasilkan 0.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
hash_key disediakan. Tulis insert(table, key) menggunakan probing linear: pergi ke slot hash kunci; selama slot itu penuh (bukan None), melangkah ke (slot + 1) % len(table); masukkan kunci ke slot pertama yang kosong dan kembalikan indeksnya.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
hash_key disediakan. Tulis find(table, key) yang mengembalikan indeks dari key, atau -1 jika tidak ada. Mulai dari slot hash dan probed maju, membandingkan setiap slot. Berhenti saat menemukan slot kosong (kunci tidak ada). Pastikan berhenti meskipun tabel penuh—jangan pernah looping selamanya.
Klik Jalankan untuk melihat output di sini.