Dict và Set: bảng băm bên trong CPython

Dict có mặt ở khắp nơi trong Python: biến toàn cục là một dict, thuộc tính của object nằm trong dict, module là dict, keyword arguments cũng là dict. Vì vậy dict là cấu trúc dữ liệu được tối ưu kỹ nhất trong CPython. Bài này giải thích nó hoạt động ra sao và những hệ quả bạn gặp khi code hằng ngày.

Trong bài này, bạn sẽ học:

• Bảng băm hoạt động thế nào: hàm băm, open addressing, va chạm
• Compact dict - vì sao dict giữ thứ tự chèn từ Python 3.7
• Load factor, resize, và vì sao dict không tự co lại
• Quy tắc __eq__/__hash__ và cách viết đúng cho class của bạn
• Hash tệ biến O(1) thành O(n) như thế nào
• Set khác dict ở đâu, và các biến thể hữu ích trong collections

1. Ý tưởng cơ bản của bảng băm

Mục tiêu: tìm d[key] trong O(1) mà không phải duyệt hết các phần tử.

1. Tính h = hash(key) - một số nguyên.
2. Lấy index = h & (size - 1) (tương đương h % size vì size luôn là luỹ thừa của 2).
3. Nhìn vào ô index. Nếu ô đó chứa key có cùng hash và == key cần tìm → tìm thấy.
4. Nếu ô đã bị key khác chiếm (va chạm - collision), tính ô tiếp theo theo một công thức “nhảy” giả ngẫu nhiên và thử lại. Kỹ thuật này gọi là open addressing (không dùng danh sách liên kết như Java).

print(hash("abc"))    # số nguyên lớn, thay đổi mỗi lần chạy chương trình
print(hash(42))       # 42
print(hash(-1))       # -2  (!) -1 được dùng làm mã lỗi trong C
print(hash((1, 2)))   # tuple hash được nếu mọi phần tử hash được

Ghi chú

Hash của str và bytes được ngẫu nhiên hoá mỗi lần chạy (biến môi trường PYTHONHASHSEED). Đây là biện pháp chống tấn công “hash flooding”: kẻ xấu gửi hàng nghìn key cố tình va chạm để làm server chậm như O(n²). Vì vậy đừng bao giờ lưu hash(str) xuống file hay dùng nó qua nhiều tiến trình.

2. Compact dict: vì sao dict giữ thứ tự chèn?

Trước Python 3.6, dict lưu các entry (hash, key, value) trực tiếp trong bảng băm thưa thớt - vừa tốn chỗ vừa không có thứ tự. Từ 3.6 (và chính thức đảm bảo từ 3.7), CPython tách thành hai mảng:

d = {"an": 1, "binh": 2, "chi": 3}

indices (bảng băm, mỗi ô chỉ 1-8 byte tuỳ kích thước)
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ -1 │  1 │ -1 │ -1 │  0 │ -1 │  2 │ -1 │     (-1 = ô trống)
└────┴────┴────┴────┴────┴────┴────┴────┘

entries (mảng liền mạch, theo THỨ TỰ CHÈN)
┌───┬─────────────┬────────┬───────┐
│ 0 │ hash("an")  │ "an"   │ 1     │
│ 1 │ hash("binh")│ "binh" │ 2     │
│ 2 │ hash("chi") │ "chi"  │ 3     │
└───┴─────────────┴────────┴───────┘

• Bảng indices thưa nhưng mỗi ô rất nhỏ (1 byte nếu dict có ít hơn 128 phần tử).
• Mảng entries dày đặc và theo thứ tự chèn → duyệt dict chính là duyệt mảng này, nên thứ tự được giữ nguyên và duyệt rất nhanh.
• Tiết kiệm 20-25% bộ nhớ so với thiết kế cũ.

3. Load factor và resize

Bảng băm sẽ chậm nếu quá đầy (nhiều va chạm). CPython giữ bảng đầy tối đa 2/3. Khi vượt ngưỡng, dict cấp phát bảng mới lớn hơn và chèn lại toàn bộ phần tử.

import sys

d = {}
prev = -1
for i in range(50):
    size = sys.getsizeof(d)
    if size != prev:
        print(f"len={len(d):2}  size={size}")
        prev = size
    d[i] = i

len= 0  size=64
len= 1  size=224
len= 6  size=352
len=11  size=632
len=22  size=1168
len=43  size=2264

Bảng 8 ô chứa tối đa 5 phần tử (2/3 × 8), bảng 16 ô chứa 10, bảng 32 ô chứa 21…

Dict không tự co lại

import sys
d = {i: i for i in range(10_000)}
print(sys.getsizeof(d))          # 294992
for i in range(9_990):
    del d[i]
print(len(d), sys.getsizeof(d))  # 10 294992  <- vẫn giữ nguyên bộ nhớ!
d = dict(d)                      # tạo dict mới để "nén" lại
print(sys.getsizeof(d))          # 352

Xoá phần tử chỉ đánh dấu ô là “đã xoá” (dummy) chứ không trả bộ nhớ. Nếu bạn có dict cache lớn, đã xoá gần hết, hãy tạo lại bằng dict(d).

4. Vì sao key phải hashable?

Vị trí của key trong bảng phụ thuộc vào hash(key). Nếu key thay đổi sau khi được chèn, hash của nó đổi → dict tìm sai ô và “mất” phần tử. Vì vậy Python cấm dùng object mutable như list, dict, set làm key:

try:
    {[1, 2]: "a"}
except TypeError as e:
    print(e)   # unhashable type: 'list'

Dùng tuple hoặc frozenset thay thế.

Quy tắc vàng: a == b ⟹ hash(a) == hash(b)

print(hash(1) == hash(1.0) == hash(True))   # True
print({1: "a", 1.0: "b", True: "c"})         # {1: 'c'}  <- chỉ 1 key!

Vì 1 == 1.0 == True nên chúng phải có cùng hash và bị coi là cùng một key. Key đầu tiên (1) được giữ, value bị ghi đè.

5. Tự viết __hash__ và __eq__ đúng cách

Khi bạn định nghĩa __eq__ trong class, Python tự đặt __hash__ = None (object không còn hashable). Muốn dùng làm key thì phải định nghĩa __hash__ phù hợp:

class Point:
    __slots__ = ("x", "y")

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))   # băm tuple các trường dùng trong __eq__

visited = {Point(1, 2)}
print(Point(1, 2) in visited)   # True

Cách gọn nhất: @dataclass(frozen=True) tự sinh __eq__ và __hash__ đúng.

from dataclasses import dataclass

@dataclass(frozen=True)
class Point:
    x: int
    y: int

print({Point(1, 2): "A"}[Point(1, 2)])   # A

Hash tệ = dict chậm như list

import timeit

class Bad:
    def __hash__(self):
        return 42              # mọi object cùng hash -> va chạm liên tục
    def __eq__(self, other):
        return self is other

print(timeit.timeit("{Bad() for _ in range(2000)}", globals=globals(), number=1))    # ~0.08s
print(timeit.timeit("{object() for _ in range(2000)}", globals=globals(), number=1)) # ~0.0001s

Với hash hằng số, mỗi lần chèn phải dò qua mọi phần tử trước → O(n²). Chậm hơn ~700 lần chỉ với 2000 phần tử.

6. Set: bảng băm không có value

set dùng bảng băm riêng (không phải compact dict): mỗi ô chứa (hash, key), không giữ thứ tự chèn. Set được tối ưu cho phép thử in và các phép toán tập hợp:

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a & b)   # {3, 4}        giao
print(a | b)   # {1, 2, 3, 4, 5} hợp
print(a - b)   # {1, 2}        hiệu
print(a ^ b)   # {1, 2, 5}     hiệu đối xứng

Set có tải tối đa khoảng 60% và dò tuyến tính vài ô liền kề trước khi nhảy (tận dụng cache CPU), nên set thường tốn bộ nhớ hơn dict cùng số phần tử:

import sys
print(sys.getsizeof(set(range(100))))            # 8408
print(sys.getsizeof({i: i for i in range(100)})) # 4688

Mẹo: cần một “set có thứ tự”? Dùng dict.fromkeys(items):

items = ["b", "a", "b", "c", "a"]
print(list(dict.fromkeys(items)))   # ['b', 'a', 'c'] - bỏ trùng, giữ thứ tự

7. Không được thay đổi kích thước khi đang duyệt

d = {"a": 1}
try:
    for k in d:
        d["b"] = 2
except RuntimeError as e:
    print(e)   # dictionary changed size during iteration

Thêm phần tử có thể gây resize, làm iterator trỏ vào vùng nhớ cũ. Hãy duyệt trên bản sao: for k in list(d): ....

8. Dict của object và key-sharing

Mỗi instance thường có một __dict__. Nếu mỗi object một dict đầy đủ thì hàng triệu object sẽ tốn rất nhiều bộ nhớ. CPython tối ưu:

• Key-sharing dict (PEP 412): các instance cùng class dùng chung một bảng key, mỗi instance chỉ lưu mảng value riêng.
• Inline values (3.11+/3.13): value được lưu ngay trong object, __dict__ chỉ được tạo khi bạn thực sự truy cập nó.

Để tận dụng tối ưu này: gán đủ mọi thuộc tính trong __init__, theo cùng một thứ tự. Thêm thuộc tính “lung tung” ở nơi khác có thể làm object rơi về dict thường. Muốn tiết kiệm triệt để hơn, xem bài __slots__ và weakref.

9. Các biến thể hữu ích trong collections

Kiểu	Dùng khi
defaultdict(list)	gom nhóm mà không cần kiểm tra key tồn tại
Counter	đếm tần suất, most_common(n)
ChainMap	tra cứu qua nhiều dict theo thứ tự ưu tiên (config mặc định + người dùng)
OrderedDict	cần move_to_end() hoặc so sánh == có tính thứ tự (ví dụ viết LRU cache)
types.MappingProxyType	tạo “view chỉ đọc” của dict

from types import MappingProxyType

_config = {"debug": False}
CONFIG = MappingProxyType(_config)
print(CONFIG["debug"])     # False
# CONFIG["debug"] = True   # TypeError: không cho phép sửa

Bài tập

1. Viết class Money(amount, currency) dùng được làm key của dict, với Money(100, "VND") == Money(100, "VND"). Làm bằng hai cách: tự viết __eq__/__hash__ và @dataclass(frozen=True).
2. Đo thời gian chèn 10.000 object vào set khi __hash__ trả về id(self) % 10 so với hash(id(self)). Giải thích kết quả.
3. Dùng dict.fromkeys loại bỏ phần tử trùng trong một list 1 triệu phần tử mà vẫn giữ thứ tự; so sánh tốc độ với cách dùng vòng lặp + set.

Kết luận

Bạn đã đi qua những kiến thức cốt lõi của bài này:

• Dict/set tra cứu O(1) trung bình nhờ bảng băm + open addressing.
• Compact dict (3.6+) tách indices và entries → tiết kiệm bộ nhớ và giữ thứ tự chèn.
• Bảng đầy 2/3 thì resize; xoá phần tử không làm dict co lại.
• a == b phải kéo theo hash(a) == hash(b); dùng @dataclass(frozen=True) cho gọn.
• Hash tệ biến O(1) thành O(n).
• Set tốn bộ nhớ hơn dict nhưng phép toán tập hợp rất nhanh.

Bài tiếp theo: Bộ cấp phát bộ nhớ, GC và truy tìm memory leak.