Hash tables · Bảng 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.
Bảng băm: tìm kiếm nhanh
- Một bảng băm lưu trữ các mục sao cho bạn có thể tìm thấy chúng rất nhanh — thường chỉ trong một bước.
- Nó là một danh sách các ngăn. Một hàm băm biến khóa thành số ngăn.
- Thay vì tìm kiếm từng mục, bạn nhảy thẳng đến ngăn mà khóa thuộc về.
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.
Một hàm băm
- Một hàm băm nhận một khóa và trả về chỉ số ngăn từ
0đếnsize - 1. - Khóa giống nhau luôn tạo ra cùng một ngăn, nên bạn có thể tìm lại nó sau này.
- Một hàm đơn giản: cộng các mã ký tự, rồi lấy modulo
% sizeđể nằm trong khoảng.
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.
Va chạm
- Hai khóa khác nhau có thể bị băm về cùng một ngăn. Đó là va chạm.
- Bảng có số ngăn giới hạn, nên va chạm là điều không thể tránh khỏi khi bảng đầy.
- Chúng ta cần quy tắc về việc làm thế nào khi ngăn mong muốn đã bị chiếm.
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.
Thăm dò tuyến tính
- Thăm dò tuyến tính: nếu một ngăn đầy, hãy thử ngăn tiếp theo, rồi ngăn tiếp theo, quay vòng lại.
- Tiếp tục bước
(slot + 1) % sizecho đến khi tìm thấy ngăn trống. - Dưới đây,
AvàFđều muốn ngăn 0, nênFbị đẩy sang ngăn 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.
Tìm kiếm một khóa
- Để tìm một khóa: băm nó, sau đó thăm dò tiến lên, so sánh từng ngăn với khóa.
- Dừng lại và trả về chỉ số khi tìm thấy.
- Nếu bạn chạm phải ngăn trống (hoặc kiểm tra hết mọi ngăn), khóa không tồn tại — trả về
-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).
Tại sao bảng băm lại nhanh
- Với ít va chạm, chèn và tìm mất khoảng một bước — chúng ta gọi điều này là
O(1). - Khi bảng đầy, việc thăm dò trở nên dài hơn, nên tốt nhất nên giữ lại một số ngăn trống.
- Trong trường hợp xấu nhất (tất cả đều va chạm), tốc độ chậm lại thành quét tuyến tính,
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.
Lỗi thường gặp
- Một hàm băm ánh xạ một khóa sang chỉ số trong bảng.
- Hai khóa có thể va chạm tại cùng một chỉ số — xử lý nó, ví dụ bằng cách nối chuỗi.
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.
Bây giờ bạn thử
- Xây dựng ba phần: hàm băm, chèn kèm thăm dò, và tìm kiếm.
- Mỗi bài toán kiểm tra hàm của bạn trong các trường hợp va chạm và quay vòng.
- Nhấn Kiểm tra đáp án để thử nghiệm.
Hashing to a bucket · Hashing vào bucket
A hash function sends each key to a bucket; clashes chain. · Hàm hash gửi mỗi key đến một bucket; khi xảy ra va chạm thì tạo chuỗi liên kết (chain).
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. · Viết hash_key(key, size). Cộng các mã ký tự của key (sử dụng ord(ch)) và trả về tổng % size, sao cho kết quả nằm trong khoảng từ 0 đến size - 1. Ví dụ: hash_key("AB", 10) là (65 + 66) % 10 = 1. Chuỗi rỗng cho ra 0.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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 đã được cung cấp. Viết insert(table, key) sử dụng tìm kiếm tuyến tính: đi đến ô hash của key; trong khi ô đó đầy (không phải None), bước sang (slot + 1) % len(table); đặt key vào ô trống đầu tiên và trả về chỉ số của nó.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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 đã được cung cấp. Viết find(table, key) trả về chỉ số của key, hoặc -1 nếu không tìm thấy. Bắt đầu từ ô hash và dò tìm theo chiều tiến, so sánh từng ô. Dừng lại khi gặp ô trống (không có khóa). Đảm bảo hàm kết thúc ngay cả khi bảng đầy—không bao giờ lặp vô hạn.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.