Bỏ qua đến nội dung chính
Mục lục

Bảng băm (hash table) trong Python và cách dict hoạt động

AIDev Team · duyệt: Nguyễn Việt Chung

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

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:

python
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
True

Số 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:

python
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 ==:

python
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à None

117 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:

python
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 1000

Mộ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

  1. Với bảng 8 ô, hash(204) % 8 chọn ô số mấy?

    • 5
    • 4
    • 204
  2. Với bảng 8 ô, những cặp khóa số nguyên nào va chạm?

    • 101 và 109
    • 3 và 11
    • 4 và 5
    • 8 và 9
  3. Trong ví dụ class May, nếu __hash__ trả về hash(self.so) thì dòng cuối in gì?

    • True 1000
    • False 1
    • True 1
  4. 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óa 101?

    • 'Lan'
    • 'Lan Anh'
    • None
Đúng hết lần đầu +15 XP

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ủa khoa, 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ủa khoa, không có thì None.

  • xoa(khoa): bỏ cặp của khoa khỏ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.

python
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):
        pass

Tó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.

  • dict và set là 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ủ đề

hash table

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập