Hash tables · Tabel hash
Hash tables: fast lookup
- A hash table stores items so you can find them very fast — usually in one step.
- It is a list of slots. A hash function turns a key into a slot number.
- Instead of searching every item, you jump straight to the slot the key belongs in.
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.
A hash function
- A hash function takes a key and returns a slot index from
0tosize - 1. - The same key always gives the same slot, so you can find it again later.
- A simple one: add the character codes, then take
% sizeto stay in range.
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))
Collisions
- Two different keys can hash to the same slot. That is a collision.
- A table has limited slots, so collisions are unavoidable as it fills up.
- We need a rule for what to do when the slot we want is already taken.
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.
Linear probing
- Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
- Keep stepping
(slot + 1) % sizeuntil you find a free slot. - Below,
AandFboth want slot 0, soFis pushed to slot 1.
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]
Looking up a key
- To find a key: hash it, then probe forward, comparing each slot to the key.
- Stop and return the index when you find it.
- If you reach an empty slot (or check every slot), the key is not there — return
-1.
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.
Why hash tables are fast
- With few collisions, insert and find take about one step — we call this
O(1). - As the table fills, probing gets longer, so it is wise to keep some slots free.
- In the worst case (everything collides) it slows to a linear scan,
O(n).
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).
Common mistakes
- A hash function maps a key to an index in the table.
- Two keys can collide at the same index — handle it, for example by chaining.
Kesalahan umum
- Fungsi hash memetakan kunci ke indeks dalam tabel.
- Dua kunci dapat bertabrakan pada indeks yang sama — tangani hal ini, misalnya dengan rantai (chaining).
Now you try
- Build the three parts: the hash function, insert with probing, and find.
- Each task checks your function on collisions and wrap-around cases.
- Press Check answer to test it.
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 to a bucket · Hashing ke dalam bak
A hash function sends each key to a bucket; clashes chain. · Fungsi hash mengirimkan setiap kunci ke bak; benturan membentuk rantai.
Write hash_key(key, size). Add the character codes of key (use ord(ch)) and return the total % size, so the result is a slot from 0 to size - 1. Example: hash_key("AB", 10) is (65 + 66) % 10 = 1. The empty string gives 0. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
hash_key is provided. Write insert(table, key) using linear probing: go to the key's hash slot; while that slot is full (not None), step to (slot + 1) % len(table); put the key in the first free slot and return its index. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
hash_key is provided. Write find(table, key) that returns the index of key, or -1 if it is missing. Start at the hash slot and probe forward, comparing each slot. Stop at an empty slot (key not there). Make sure it ends even if the table is full — never loop forever. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.