Bảng hash
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ề.
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))
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.
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]
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.
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).
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ý điều này, như bài học này làm, bằng dò tìm tuyến tính; nối chuỗi là phương pháp phổ biến khác.
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
A hash function sends each key to a bucket; clashes dây chuyền.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 đến size - 1. Example: hash_key("AB", 10) là (is) (65 + 66) % 10 = 1. The empty string gives 0.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 trống rỗng slot (key not there). Make sure it ends even if the table is đầy đủ — never loop forever.
Nhấn Chạy để xem kết quả ở đây.