Bảng băm (hash table) trong Python và cách dict hoạt động
Bài 6/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 7 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Bảng băm (hash table) là cách cất cặp khóa và giá trị sao cho tìm một khóa chỉ cần nhìn vào một ô nhỏ thay cho đi qua cả dãy. dict và set của Python đều là bảng băm, và bài này dựng một hash table nhỏ cho danh bạ máy lẻ để bạn thấy nó chạy ra sao bên trong.
Cần biết trước: dictionary, set và độ phức tạp Big O.
hash() biến một giá trị thành số nguyên
Hàm hash() nhận một giá trị hashable (băm được) và trả về một số nguyên gọi là mã băm. Hai giá trị bằng nhau luôn có cùng mã băm:
print(hash(101), hash(True))
print(hash(101) == hash(101.0))
print(hash("Bến Ngự") == hash("Bến Ngự"))KẾT QUẢ
101 1
True
TrueSố nguyên nhỏ có mã băm là chính nó, và 101.0 bằng 101 nên băm ra cùng số. Mã băm của chuỗi thì đổi theo từng lần chạy chương trình: tài liệu Python (docs.python.org/3/faq/design.html, mục "How are dictionaries implemented in CPython?", xem ngày 15/11/2026) ghi rằng nó phụ thuộc vào một hạt giống riêng của mỗi tiến trình. Vì vậy bài này in mã băm của số nguyên, còn chuỗi chỉ đem so với nhau. List không có mã băm, như bài dictionary đã cho thấy với lỗi unhashable type.
Từ mã băm tới một ô
Bảng băm là một list gồm nhiều ô, mỗi ô là một list cặp [khoa, gia_tri]. Ô của một khóa là phần dư hash(khoa) % so_o, luôn nằm trong khoảng từ 0 tới so_o - 1. Các ô được dựng từng cái bằng append([]), giống cách bài mảng 2 chiều dựng từng hàng:
so_o = 8
cac_o = []
for i in range(so_o):
cac_o.append([])
cac_cap = [[101, "Lan"], [204, "Minh"], [109, "Hà"]]
for may_le, ten in cac_cap:
cac_o[hash(may_le) % so_o].append([may_le, ten])
for i in range(so_o):
if cac_o[i]:
print(i, cac_o[i])KẾT QUẢ
4 [[204, 'Minh']]
5 [[101, 'Lan'], [109, 'Hà']]Muốn tìm máy lẻ 204, bạn tính 204 % 8 ra 4 và chỉ nhìn ô 4. Danh bạ có thêm bao nhiêu người thì phép tính đó vẫn là một bước. Đổi so_o = 8 thành so_o = 10 rồi chạy lại: in ba dòng, dòng đầu là 1 [[101, 'Lan']].
Va chạm: hai khóa chung một ô
101 và 109 cùng rơi vào ô 5 vì cả hai chia 8 đều dư 5. Hiện tượng này gọi là va chạm (collision). Bảng của bài xử lý va chạm bằng cách để nhiều cặp trong cùng ô, và khi tìm thì đi qua ô đó, so từng khóa bằng ==:
class BangBam:
def __init__(self, so_o):
self.cac_o = []
for i in range(so_o):
self.cac_o.append([])
def lay(self, khoa):
o = self.cac_o[hash(khoa) % len(self.cac_o)]
for cap in o:
if cap[0] == khoa:
return cap[1]
return None
bang = BangBam(8)
bang.cac_o[5] = [[101, "Lan"], [109, "Hà"]]
print(bang.lay(109), bang.lay(117))KẾT QUẢ
Hà None117 cũng rơi vào ô 5 nhưng không cặp nào mang khóa đó, nên lay() trả về None. Số lần so bằng độ dài của ô. Khi n khóa chia đều cho m ô, mỗi ô có khoảng n / m cặp, và bảng chỉ cần thêm ô khi danh bạ lớn lên để giữ con số đó nhỏ: tra cứu trung bình là O(1). Nếu mọi khóa dồn vào cùng một ô, lay() thành một vòng lặp qua cả danh bạ, tức O(n).
dict và set bên trong
Tài liệu Python ở mục đã dẫn ghi rằng dict của CPython là bảng băm tự đổi kích thước. Mã băm của khóa chọn ra một vị trí trong một mảng bên trong, và khi các khóa có mã băm khác nhau thì lấy một khóa tốn thời gian hằng số. Cách CPython xử lý va chạm khác bảng của bài, nhưng ý chính giống: so mã băm trước, chỉ gọi __eq__ khi mã băm trùng. Đoạn dưới cho mọi khóa cùng mã băm 0 và đếm số lần __eq__ được gọi khi tra một khóa:
class May:
so_lan_so = 0
def __init__(self, so):
self.so = so
def __eq__(self, khac):
May.so_lan_so += 1
return self.so == khac.so
def __hash__(self):
return 0
danh_ba = {}
for so in range(1000):
danh_ba[May(so)] = "Nhân viên"
May.so_lan_so = 0
print(May(999) in danh_ba, May.so_lan_so)KẾT QUẢ
True 1000Một lần tra phải so với cả nghìn khóa: đó là trường hợp xấu nhất O(n) mà trang "Time complexity of operations on built-in types" (docs.python.org/3/builtins/time-complexity.html, xem ngày 15/11/2026) ghi cho dict. Đổi return 0 thành return hash(self.so) rồi chạy lại: in True 1, vì mã băm khác nhau đưa thẳng tới đúng khóa. set dùng cùng cơ chế, chỉ không cất giá trị. Đây là lý do khóa phải bất biến và __hash__ phải đi cùng __eq__ như bài dunder methods đã dặn: khóa đổi mã băm sau khi vào dict thì nằm sai ô.
Kiểm tra nhanh
Với bảng 8 ô,
hash(204) % 8chọn ô số mấy?54204
Với bảng 8 ô, những cặp khóa số nguyên nào va chạm?
101và1093và114và58và9
Trong ví dụ class
May, nếu__hash__trả vềhash(self.so)thì dòng cuối in gì?True 1000False 1True 1
Trong khung bẫy thêm cặp mà không tìm khóa cũ,
lay()đi từ đầu ô trả về gì cho khóa101?'Lan''Lan Anh'None
Bài tập
Viết bảng băm cho danh bạ máy lẻ
Danh bạ máy lẻ là một bảng băm: self.cac_o là list các ô, mỗi ô là list cặp [khoa, gia_tri]. Ô của một khóa là self.cac_o[hash(khoa) % len(self.cac_o)]. Viết thân ba phương thức của BangBam, không dùng dict hay set:
dat(khoa, gia_tri): trong ô củakhoa, gặp cặp cùng khóa thì sửa giá trị, không gặp thì thêm cặp[khoa, gia_tri]vào cuối ô.lay(khoa): giá trị củakhoa, không có thìNone.xoa(khoa): bỏ cặp củakhoakhỏi ô và trả vềTrue, không có thìFalse.
Trả về: lay() trả về giá trị đã đặt hoặc None, xoa() trả về một bool.
class BangBam:
def __init__(self, so_o=8):
self.cac_o = []
for i in range(so_o):
self.cac_o.append([])
def dat(self, khoa, gia_tri):
pass # Viết thân các phương thức thay cho các dòng pass
def lay(self, khoa):
pass
def xoa(self, khoa):
passTóm tắt
hash()biến một giá trị hashable thành số nguyên, hai giá trị bằng nhau luôn cùng mã băm.Bảng băm chọn ô của khóa bằng
hash(khoa) % so_o, nên tìm một khóa chỉ cần nhìn một ô.Hai khóa chung một ô là va chạm, khi đó ô giữ nhiều cặp và việc tìm phải so từng khóa bằng
==.Đặt một khóa đã có phải sửa cặp cũ, thêm cặp mới làm ô giữ hai cặp cùng khóa.
dictvàsetlà bảng băm: trung bình O(1), xấu nhất O(n) khi mọi khóa cùng mã băm.
Câu hỏi thường gặp
Hash table là gì, có khác dict không?
Hash table là cách tổ chức dữ liệu, còn dict là kiểu dựng sẵn của Python làm theo cách đó. Trong chương trình thật bạn dùng dict hoặc set, bảng tự viết của bài chỉ để thấy chúng làm gì khi bạn viết d[k].
Có dùng hash() để cất mật khẩu được không?
Không. hash() cho ra mã băm nhanh để chọn ô trong dict và set, và mã của chuỗi đổi theo từng lần chạy. Module hashlib tính mã băm cố định như SHA-256 để kiểm tra một file có bị đổi không. Mật khẩu thì không cất bằng SHA-256 trần mà cần một hàm băm chậm có muối, bài hashlib, secrets và uuid giải thích vì sao.
Vì sao tìm trong set nhanh hơn tìm trong list?
Tìm trong list là đi qua từng phần tử, còn set tính ô của giá trị rồi chỉ nhìn ô đó. Bài toán tử in và not in so hai cách tìm trên cùng dữ liệu.
Nhiều khóa va chạm thì dict có chậm đi không?
Có, nếu nhiều khóa cùng mã băm, như ví dụ class May trả về 0. Với các kiểu dựng sẵn như số nguyên và chuỗi, mã băm trải đều nên va chạm hiếm, và dict tự thêm chỗ khi lớn lên để giữ trung bình O(1).
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.