Hash TableHash Tables

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Hash table là câu trả lời cho một câu hỏi rất cụ thể: array cho phép truy cập O(1) bằng index kiểu số nguyên — vậy làm sao để truy cập O(1) bằng một key bất kỳ? Câu trả lời là tính ra index từ chính key đó. Một hash function biến key thuộc kiểu bất kỳ thành một số nguyên, số nguyên đó được rút gọn theo modulo kích thước bảng thành số hiệu slot, và value được lưu tại đó. Khi tra cứu, ta lặp lại đúng phép tính ấy và rơi vào đúng slot cũ. Không tìm kiếm, không so sánh tuần tự — chỉ một phép tính số học và một lần truy cập bộ nhớ.

Đây là cấu trúc dữ liệu hữu dụng nhất trong lập trình hàng ngày. dict và set của Python, HashMap của Java, map của Go, Object và Map của JavaScript, unordered_map của C++, toàn bộ keyspace của Redis, symbol table bên trong compiler, hash table dùng cho phép join trong database, khử trùng lặp, memoization cache — tất cả đều là hash table. Nếu profile một backend service điển hình, bạn sẽ thấy một tỷ lệ rất lớn thời gian nằm ở các thao tác hash lookup.

Vấn đề nằm ở cụm từ “rút gọn theo modulo kích thước bảng”. Hash function ánh xạ một không gian key vô hạn (mọi chuỗi có thể có) vào một không gian slot hữu hạn (giả sử 8 slot). Theo nguyên lý chuồng bồ câu (pigeonhole principle), collision không phải là khả năng cần tránh; nó là điều chắc chắn xảy ra và phải được xử lý. Mọi thứ thú vị về hash table — chaining hay open addressing, load factor, resize, clustering, worst case O(n), tấn công hash flooding — đều bắt nguồn từ cách một implementation cụ thể xử lý tình huống hai key rơi vào cùng một slot.

Một điều nữa cần thấm từ sớm: O(1) của hash table là giá trị trung bình dựa trên một hash function có tính ngẫu nhiên hóa. Nó không phải một bảo đảm. Với input do kẻ tấn công dựng lên, hoặc với một __hash__ viết tệ, mọi thao tác đều suy biến thành O(n), và service nào giả định O(1) sẽ sập. Đây là kiểu hỏng hóc có thật, đã từng đánh sập hệ thống production thật, và là lý do các ngôn ngữ hiện đại đều ngẫu nhiên hóa việc hash chuỗi.

Kiến thức nền tảng

Ý tưởng cốt lõi

1. 01key "banana"Thứ mà người gọi thực sự muốn lưu hoặc tra cứu. Bất kỳ giá trị hashable nào cũng được — table không bao giờ diễn giải nội dung của nó.
2. 02hash functionhash("banana") = 8093131396522585862 — một số nguyên cỡ machine word, trải đều nhất có thể trên toàn miền giá trị.
3. 03nén về chỉ số slot8093131396522585862 & (8 - 1) = 6 — mask với capacity−1 chỉ giữ lại các bit thấp, và đó là lý do capacity luôn là lũy thừa của 2.
4. 04slot 6Lưu ở đây, và mọi lần tra cứu sau cũng tìm đúng ở đây. Cùng một key luôn rơi vào cùng một slot — đó chính là điều làm cho việc truy xuất là O(1).

Hai bước, cả hai đều O(1):

1. Hashing — hash(key) → số nguyên. Phụ thuộc vào nội dung của key, không phụ thuộc vào bảng.
2. Nén (compression) — số nguyên → [0, capacity). Thường là h % capacity, hoặc h & (capacity - 1) khi capacity là lũy thừa của 2 (phép AND bit rẻ hơn nhiều so với phép chia — đó là lý do gần như mọi implementation thực tế đều dùng capacity là lũy thừa của 2).

Thế nào là một hash function tốt

• Deterministic — cùng một key phải cho ra cùng một giá trị hash trong suốt vòng đời của bảng. Đây là lý do object có thể thay đổi (mutable) là key rất tệ: sửa một list sau khi đã dùng nó làm key thì entry đó trở nên không thể tìm lại, vì lần sau bạn sẽ hash ra slot khác. Python cưỡng chế điều này bằng cách từ chối hash list, dict, và set.
• Uniform — output phải trải đều trên không gian slot, không thiên vị slot nào. Một hash function trả về len(s) cho chuỗi thì vừa deterministic vừa nhanh, nhưng phân bố cực kỳ tệ: mọi từ 5 chữ cái đều collide với nhau.
• Avalanche — thay đổi một bit trong key phải làm lật khoảng một nửa số bit output. Không có tính chất này, các key gần giống nhau (user:1000, user:1001) sẽ dồn cụm vào các slot liền kề.
• Nhanh — hash được tính ở mọi thao tác. Một hash function mạnh về mặt mật mã như SHA-256 tuy phân bố đều nhưng quá chậm cho hash table; các bảng production dùng hash không mật mã (FNV-1a, MurmurHash, xxHash) hoặc một hash có khóa nhẹ (SipHash — xem phần bảo mật bên dưới).

Lưu ý thứ không được yêu cầu: tính không thể đảo ngược. Hash cho hash table và hash mật mã giải quyết hai bài toán khác nhau và được tinh chỉnh theo hai hướng khác nhau.

Hợp đồng __hash__ / __eq__

Trong Python (và mọi ngôn ngữ khác, chỉ khác tên gọi), key do người dùng định nghĩa phải thỏa một quy tắc:

Nếu a == b thì hash(a) == hash(b).

Chiều ngược lại không bắt buộc — hai object khác nhau có thể trùng hash; đó chỉ là collision, và bảng sẽ xử lý bằng cách so sánh tiếp bằng ==. Nhưng nếu hai object bằng nhau lại hash khác nhau, chúng sẽ rơi vào hai slot khác nhau, bảng sẽ vui vẻ lưu cả hai, và “cache hit” của bạn sẽ âm thầm trở thành cache miss vĩnh viễn.

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

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        # Tính hash từ đúng những field mà __eq__ đem ra so sánh.
        # Hash một tuple gồm các field đó là cách đúng và idiomatic nhất.
        return hash((self.x, self.y))

Định nghĩa __eq__ mà không định nghĩa __hash__ sẽ khiến class trở nên unhashable trong Python 3 — một biện pháp bảo vệ có chủ đích để chặn đúng loại bug này. @dataclass(frozen=True) sinh ra cả hai một cách chính xác và là thứ bạn nên dùng trong thực tế.

Load factor

Load factor α = n / capacity (số entry chia cho số slot) là con số duy nhất chi phối hiệu năng của hash table. Mọi thứ liên quan tới tốc độ của hash table đều là hàm của α:

• α gần 0 — nhanh, nhưng phần lớn array bị lãng phí.
• α khoảng 0.5–0.75 — vùng tối ưu mà mọi implementation thực tế nhắm tới.
• α gần 1 — collision khắp nơi; với open addressing, chuỗi probe dài ra một cách thảm họa.
• α > 1 — bất khả thi với open addressing (không còn chỗ để đặt entry); chỉ là chậm với chaining.

Với separate chaining, độ dài chain kỳ vọng đúng bằng α, nên một lần lookup tốn trung bình 1 + α/2 phép so sánh — vẫn là O(1) với α là hằng số bất kỳ, chỉ là hằng số nhân lớn dần khi α tăng.

Với linear probing, chi phí bùng nổ phi tuyến. Phân tích kinh điển (Knuth) cho số lần probe kỳ vọng:

Load factor α	Lookup thành công ½(1 + 1/(1−α))	Lookup thất bại / insert ½(1 + 1/(1−α)²)
0.25	1.2	1.4
0.50	1.5	2.5
0.75	2.5	8.5
0.90	5.5	50.5
0.95	10.5	200.5

Hãy nhìn dòng cuối. Khi bảng đầy 95%, một lần lookup thất bại — chính là thứ mà mọi lần insert phải thực hiện — chạm trung bình 200 slot. Đây là lý do các bảng open addressing resize rất sớm, và là lý do câu “cứ để nó đầy đi, dù sao cũng O(1)” là sai. dict của CPython grow ở mức 2/3; HashMap của Java ở 0.75; map của Go ở mức 6.5 entry mỗi bucket (bucket của nó chứa 8).

Khái niệm chính

Xử lý collision 1 — separate chaining

Mỗi slot chứa một container các entry thay vì một entry đơn lẻ. Truyền thống là linked list; thực tế thường là một array nhỏ, và trong Java 8+ là một list tự chuyển thành red-black tree khi vượt quá 8 node (một biện pháp giảm thiểu trực tiếp cho tấn công flooding mô tả bên dưới).

6 slot4 key được lưu, load factor 0.67

• slot 1
  ("apricot", 3)Một key, một link — trường hợp thông thường, và tra cứu ở đây chỉ tốn đúng một phép so sánh.
• slot 3 — collision
  ("cat", 9) → ("dog", 4)Hai key khác nhau nhưng hash về cùng một slot, nên cả hai nằm chung một chain. Lookup phải duyệt chain và so sánh key; đây chính là chỗ O(1) bắt đầu suy giảm.
• slot 5
  ("fig", 7)
• slot 0, 2, 4
  NoneTrống. Một nửa table không được dùng dù load factor vẫn ở mức lành mạnh — chính khoảng trống đó giữ cho các chain luôn ngắn.

_MISSING = object()   # sentinel để value là None không bị nhập nhằng với "không có"


class ChainedHashTable:
    """Hash table dùng separate chaining. Mỗi bucket là một list Python chứa các
    cặp (key, value) — implementation thật sẽ dùng linked list, nhưng list cho
    cùng độ phức tạp tiệm cận và dễ đọc hơn."""

    def __init__(self, capacity=8):
        self.capacity = capacity          # luôn là lũy thừa của 2
        self.size = 0                     # số entry đang tồn tại
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        # `& (capacity - 1)` tương đương `% capacity` khi capacity là lũy thừa
        # của 2, và rẻ hơn nhiều so với phép chia. Nó cũng xử lý đúng trường hợp
        # hash âm trong Python.
        return hash(key) & (self.capacity - 1)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                  # key đã tồn tại: ghi đè
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > self.capacity * 0.75:   # giữ load factor trong giới hạn
            self._resize(self.capacity * 2)

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def delete(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)             # xóa rất đơn giản: không cần tombstone
                self.size -= 1
                return True
        return False

    def _resize(self, new_capacity):
        # Mọi key phải được rehash: slot phụ thuộc vào capacity.
        old_buckets = self.buckets
        self.capacity = new_capacity
        self.buckets = [[] for _ in range(new_capacity)]
        for bucket in old_buckets:
            for key, value in bucket:
                self.buckets[hash(key) & (new_capacity - 1)].append((key, value))

    def __len__(self):
        return self.size

    def __contains__(self, key):
        return self.get(key, _MISSING) is not _MISSING


t = ChainedHashTable()
for word in ["apricot", "cat", "dog", "fig", "banana"]:
    t.put(word, len(word))
assert t.get("dog") == 3 and t.get("nope") is None
assert t.delete("cat") and "cat" not in t

Tính chất. Xóa rất đơn giản (chỉ cần gỡ node ra khỏi chain). Load factor có thể vượt 1 mà không sai. Chi phí bộ nhớ là một pointer/object header cho mỗi entry cộng với bucket array — đáng kể trong ngôn ngữ mà mỗi node là một lần cấp phát heap riêng. Hành vi cache kém: đi theo chain là pointer chasing, và mỗi bước nhảy nhiều khả năng là một cache miss (xem ./05-linked-lists.md).

Xử lý collision 2 — open addressing với linear probing

Mọi thứ nằm trực tiếp trong array. Khi collision, probe tiến về phía trước để tìm slot trống kế tiếp; khi lookup, đi theo đúng chuỗi đó cho tới khi gặp key hoặc gặp một slot chưa từng được dùng.

1. 01insert "dog" → slot 3Hash đưa "dog" về slot 3, y hệt như trong một table dùng chaining.
2. 02slot 3 đã bị "cat" chiếmOpen addressing không có chỗ nào để treo chain — mọi entry đều phải nằm ngay trong array, nên lần insert này buộc phải tìm chỗ khác.
3. 03probe slot 4 — trốngLinear probing đơn giản là đi tới từng slot một cho tới khi gặp chỗ trống. "dog" được đặt ở slot 4, không phải slot hash của chính nó.
4. 04slot 3–5 giờ là một clusterMột dãy slot bị chiếm liền kề nhau. Mọi key sau này hash vào bất kỳ đâu trong dãy đều phải probe hết cả dãy, và mỗi lần insert lại làm dãy dài thêm — clustering tự khuếch đại chính nó, và đó là lý do open addressing suy giảm rất nhanh khi load factor vượt ~0.7.

Điểm tinh tế nằm ở thao tác xóa. Bạn không thể chỉ đơn giản xóa trắng slot: làm vậy sẽ phá vỡ chuỗi probe của mọi key đã probe vượt qua slot đó. Nếu dog nằm ở slot 4 chỉ vì cat đang chiếm slot 3, mà bạn xóa cat thành _EMPTY, thì lần lookup dog sẽ dừng ở slot 3 và báo “không tìm thấy”. Giải pháp là tombstone — một dấu hiệu nghĩa là “slot này từng được dùng; hãy probe tiếp” — nó kết thúc quá trình quét khi insert nhưng không kết thúc quá trình quét khi lookup.

_EMPTY = object()     # slot chưa từng dùng — kết thúc một chuỗi probe
_DELETED = object()   # tombstone — KHÔNG kết thúc chuỗi probe


class LinearProbingHashTable:
    """Hash table open addressing với linear probing và xóa bằng tombstone."""

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0     # số entry đang tồn tại
        self.used = 0     # entry đang tồn tại + tombstone = số slot không kết thúc probe
        self.slots = [_EMPTY] * capacity

    def _probe(self, key):
        """Sinh ra các chỉ số slot cho `key`, quay vòng quanh bảng."""
        i = hash(key) & (self.capacity - 1)
        for _ in range(self.capacity):
            yield i
            i = (i + 1) & (self.capacity - 1)   # linear probing: bước nhảy bằng 1

    def put(self, key, value):
        first_tombstone = None
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is _DELETED:
                if first_tombstone is None:
                    first_tombstone = i         # ghi nhớ, nhưng vẫn probe tiếp:
                continue                        # key có thể nằm xa hơn nữa
            if slot is _EMPTY:
                # Slot trống chứng minh key không tồn tại. Chèn vào, ưu tiên dùng
                # lại tombstone đầu tiên đã đi qua để bảng gọn hơn.
                if first_tombstone is None:
                    self.slots[i] = (key, value)
                    self.used += 1              # tiêu tốn một slot chưa từng dùng
                else:
                    self.slots[first_tombstone] = (key, value)
                self.size += 1
                self._maybe_grow()
                return
            if slot[0] == key:
                self.slots[i] = (key, value)    # ghi đè key đã tồn tại
                return
        raise RuntimeError("hash table full")   # không bao giờ tới: đã grow ở mức 2/3

    def get(self, key, default=None):
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is _EMPTY:
                return default                  # chưa từng dùng: key không thể ở đây
            if slot is _DELETED:
                continue                        # đi tiếp qua tombstone
            if slot[0] == key:
                return slot[1]
        return default

    def delete(self, key):
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is _EMPTY:
                return False
            if slot is not _DELETED and slot[0] == key:
                self.slots[i] = _DELETED        # tombstone, KHÔNG phải _EMPTY
                self.size -= 1                  # `used` giữ nguyên: slot vẫn chắn đường
                return True
        return False

    def _maybe_grow(self):
        # Độ dài probe phụ thuộc vào `used`, không phải `size` — tombstone tốn chi
        # phí y hệt entry thật khi phải đi qua một chuỗi probe.
        if self.used * 3 >= self.capacity * 2:          # load factor >= 2/3
            if self.size * 3 >= self.capacity:
                self._resize(self.capacity * 2)         # thật sự đầy: tăng gấp đôi
            else:
                self._resize(self.capacity)             # chủ yếu là tombstone: dọn dẹp

    def _resize(self, new_capacity):
        old = self.slots
        self.capacity = new_capacity
        self.slots = [_EMPTY] * new_capacity
        self.size = 0
        self.used = 0
        for slot in old:
            if slot is not _EMPTY and slot is not _DELETED:
                self.put(*slot)                 # tombstone bị bỏ đi, không copy sang

    def __len__(self):
        return self.size


t = LinearProbingHashTable()
for i, word in enumerate(["apricot", "cat", "dog", "fig", "banana"]):
    t.put(word, i)
assert t.get("dog") == 2
t.delete("cat")
assert t.get("dog") == 2      # chuỗi probe vẫn nguyên vẹn sau khi xóa
assert t.get("cat") is None

Clustering, và các lựa chọn thay thế linear probing

Linear probing mắc bệnh primary clustering: các dãy slot bị chiếm liền kề nhau hợp nhất thành dãy dài hơn, và dãy càng dài thì càng là mục tiêu lớn cho lần insert tiếp theo, khiến nó lại dài thêm nữa. Đây là vòng lặp tự khuếch đại, và chính là lý do số lần probe bùng nổ khi α → 1 trong bảng phía trên.

Sơ đồ probe	Slot kế tiếp	Khắc phục	Đánh đổi
Linear	h + i	—	Primary clustering
Quadratic	h + c₁i + c₂i²	Primary clustering	Secondary clustering (hash bằng nhau vẫn dùng chung nguyên chuỗi); cần chọn tham số cẩn thận để chuỗi phủ hết bảng
Double hashing	h₁ + i·h₂(key)	Cả hai loại clustering	Phải tính hai hash; h₂ không được bằng 0 và phải nguyên tố cùng nhau với capacity
Robin Hood	linear, nhưng đẩy ra entry có quãng probe ngắn hơn	Phương sai độ dài probe	Thêm chi phí lưu trữ phụ mỗi slot

Dù lý thuyết nói vậy, linear probing thường thắng trong thực tế ở load factor vừa phải, vì nó đi tuần tự trên bộ nhớ: sau lần cache miss đầu tiên, vài lần probe tiếp theo gần như miễn phí (đã nằm sẵn trong cache line). Double hashing có số lần probe đẹp hơn trên giấy nhưng thời gian thực tế tệ hơn, vì mỗi lần probe là một cache miss mới. Đây là ví dụ tốt cho thấy mô hình RAM trong ./01-programming-fundamentals-and-pseudocode.md chỉ là một phép xấp xỉ.

Chaining và open addressing

	Separate chaining	Open addressing
Load factor α	Có thể vượt 1	Phải nhỏ hơn 1; suy giảm mạnh trên ~0.75
Xóa	Đơn giản (gỡ node)	Cần tombstone + dọn dẹp định kỳ
Bộ nhớ mỗi entry	Thêm node/pointer cho mỗi entry	Không thêm gì ngoài chính slot
Cache locality	Kém — pointer chasing	Rất tốt — quét tuần tự
Nhạy cảm với hash yếu	Suy giảm êm dịu thành quét list	Suy giảm thảm họa (clustering)
Chi phí duyệt	O(capacity + n)	O(capacity)
Được dùng bởi	Java HashMap, C++ unordered_map (chuẩn bắt buộc)	Python dict, Go map (lai), Rust HashMap (SwissTable)

unordered_map của C++ là một bài học cảnh giác: chuẩn ngôn ngữ yêu cầu tính ổn định của reference và khả năng duyệt theo bucket, điều này gần như bắt buộc phải dùng chaining, và container này chậm hơn rõ rệt so với một bảng open addressing tốt — đó là lý do gần như mọi codebase C++ nghiêm túc đều dùng absl::flat_hash_map hoặc tương đương thay thế.

Resize và O(1) amortized

Khi α vượt ngưỡng, bảng cấp phát một array lớn hơn (hầu như luôn là gấp đôi capacity) và rehash toàn bộ entry. Bạn không thể copy nguyên slot sang — chỉ số slot phụ thuộc vào capacity, nên hash(k) & (8-1) và hash(k) & (16-1) là hai slot khác nhau.

Một lần resize tốn O(n). Việc nhân đôi có nghĩa là chèn n phần tử sẽ kích hoạt resize tại các kích thước 1, 2, 4, ..., n, tổng chi phí là 1 + 2 + 4 + ... + n < 2n = O(n) — nên chi phí mỗi lần insert là O(1) amortized. Đây chính là lập luận tăng trưởng theo cấp số nhân giúp append của dynamic array cũng đạt O(1) amortized; xem ./04-arrays.md và ./03-algorithmic-complexity.md.

Hai hệ quả thực tế đáng nhớ:

• Amortized không phải worst case. Một lần insert kém may mắn tốn O(n). Trong một service nhạy cảm với latency, điều đó hiện ra ở p99.9 chứ không phải ở giá trị trung bình. Hệ thống real-time dùng resize tăng dần (Redis rehash lười biếng, rải chi phí qua nhiều thao tác, giữ hai bảng cùng sống trong lúc di chuyển) để san đều chi phí.
• Cấp phát trước khi biết kích thước. dict(zip(keys, values)) hoặc dựng từ comprehension cho phép CPython định kích thước bảng một lần duy nhất. Grow một dict lên một triệu entry sẽ thực hiện khoảng 20 lần rehash và copy tổng cộng khoảng 2 triệu entry.

Vì sao worst case là O(n)

Nếu mọi key đều hash về cùng một slot, cấu trúc suy biến:

• với chaining, một bucket chứa toàn bộ n entry và lookup trở thành quét list tuyến tính;
• với open addressing, chuỗi probe phải đi qua một cluster dài n.

Cách nào cũng vậy, get/put/delete đều là O(n) và việc dựng bảng là O(n²). Đây không phải trường hợp lý thuyết xa vời — nó xảy ra bất cứ khi nào hash function không phù hợp với phân bố key thực tế:

class BadKey:
    def __init__(self, v):
        self.v = v

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.v == other.v

    def __hash__(self):
        return 0          # hợp lệ! thỏa mãn "a == b kéo theo hash(a) == hash(b)"
                          # ...và biến mọi dict chứa BadKey thành một linked list


d = {}
for i in range(20_000):
    d[BadKey(i)] = i      # O(n^2): mỗi lần insert phải quét mọi entry trước đó

hash() == 0 cho mọi thứ là hoàn toàn hợp lệ theo hợp đồng và tai hại hoàn toàn trong thực tế. Bài học: hợp đồng bảo đảm tính đúng đắn; chỉ có tính phân bố đều mới cho bạn hiệu năng.

Hash flooding — biến worst case O(n) thành một cuộc tấn công DoS

Kẻ tấn công nào có thể (a) đưa vào nhiều key rồi kết thúc trong một hash table, và (b) đoán được hash function của bạn, thì có thể cố ý dựng ra hàng nghìn key collide với nhau và biến một cấu trúc O(1) thành O(n²). Vector kinh điển là một web framework parse POST body hoặc query string thành dictionary: vài trăm kilobyte tên tham số được chọn khéo léo sẽ đốt hàng phút CPU trên server. Vài request kiểu đó là đủ để hạ gục một máy.

Lỗ hổng này được công bố công khai tại 28C3 năm 2011 (CVE-2011-4815 và một loạt CVE liên quan) và ảnh hưởng tới Python, PHP, Ruby, Java, ASP.NET và node.js gần như đồng thời — tất cả đều đang dùng một hash chuỗi nhanh, deterministic, và công khai.

Biện pháp giảm thiểu tiêu chuẩn là hash có khóa và ngẫu nhiên hóa: trộn một seed ngẫu nhiên theo tiến trình vào hash để kẻ tấn công không thể tính trước collision nếu không biết seed. Python áp dụng SipHash trong PEP 456 (SipHash-2-4 từ 3.4, SipHash-1-3 từ 3.11); hash randomization được bật mặc định từ Python 3.3.

# Hash của chuỗi khác nhau giữa các tiến trình — seed là ngẫu nhiên theo tiến trình
$ python3 -c "print(hash('spam'))"
-4157093734590757790
$ python3 -c "print(hash('spam'))"
 8093131396522585862

# Đặt seed cố định làm hash trở nên tái lập được — hữu ích khi debug,
# nguy hiểm với bất cứ thứ gì có thể tiếp cận từ mạng
$ PYTHONHASHSEED=0 python3 -c "print(hash('spam'))"

Ba điều mà biện pháp này không bảo vệ bạn:

1. Key kiểu số. hash(n) == n với int nhỏ trong Python, một cách có chủ đích (nó làm dict với key số nguyên nhanh hơn và giữ được hash(1) == hash(1.0) == hash(True)). Randomization không áp dụng ở đây. Một dict có key là số nguyên do kẻ tấn công cung cấp vẫn có thể bị flood bằng cách gửi các bội số của capacity hiện tại.
2. Bất cứ thứ gì bạn tự hash. Nếu code của bạn shard, partition, hay cache theo md5(key) % N, thì randomization ở tầng interpreter chẳng giúp được gì.
3. PYTHONHASHSEED được đặt để tái lập kết quả. Nhiều team ghim biến này để test output ổn định rồi mang nguyên biến môi trường đó lên production. Đừng làm vậy.

Các lớp phòng thủ bổ sung: giới hạn số tham số một request được phép chứa (Django, Rails và các framework khác giờ đều làm thế), coi dict theo request là có giới hạn, và — cách sửa mang tính cấu trúc — hạ cấp một bucket thành cấu trúc có thứ tự khi nó dài bất thường, giống như HashMap của Java 8 chuyển chain dài thành red-black tree (O(log n) worst case, xem ./11-balanced-and-multiway-trees.md).

dict của Python: compact và giữ thứ tự chèn

Từ Python 3.6 (chi tiết implementation) và 3.7 (bảo đảm ở mức ngôn ngữ), dict giữ nguyên thứ tự chèn. Đây không phải một yêu cầu tính năng — nó là hệ quả phụ của một tối ưu bộ nhớ, compact dict của Raymond Hettinger, tách bảng thành hai array:

• một index array thưa chứa số nguyên nhỏ (slot → vị trí trong entries), đây mới là phần cần giữ ở load factor thấp;
• một entries array dày đặc chứa các bản ghi (hash, key, value), được append theo thứ tự chèn nên nằm liền kề nhau.

capacity 8, ba key được chèn theo thứ tự  a, b, c

indices:   [ -1,  1, -1,  0, -1,  2, -1, -1 ]   ← 8 số nguyên nhỏ, phần lớn trống
                  │       │       │
                  │       │       └──────────────┐
                  │       └───────────┐          │
                  ▼                   ▼          ▼
entries:   [ (h_a, 'a', 1), (h_b, 'b', 2), (h_c, 'c', 3) ]   ← dày đặc, đúng thứ tự

Layout cũ lưu nguyên một bản ghi 24 byte trong mọi slot của array thưa, lãng phí một phần ba số đó ở load factor 2/3. Layout mới chỉ lãng phí 1–8 byte cho mỗi slot trống, giảm 20–25% bộ nhớ của dict. Duyệt entries từ trên xuống vừa thân thiện với cache vừa đúng thứ tự chèn — tính thứ tự là món quà miễn phí.

class CompactDict:
    """Mô hình đơn giản hóa của dict trong CPython: một index array thưa trỏ vào
    một entry array dày đặc, giữ thứ tự chèn."""

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.indices = [-1] * capacity     # -1 nghĩa là "slot trống"
        self.entries = []                  # các cặp [key, value], theo thứ tự chèn

    def _lookup(self, key):
        """Trả về (slot, entry_index); entry_index là -1 khi key không tồn tại."""
        i = hash(key) & (self.capacity - 1)
        while True:
            e = self.indices[i]
            if e == -1:
                return i, -1               # slot trống: key không có trong bảng
            if self.entries[e] is not None and self.entries[e][0] == key:
                return i, e
            i = (i + 1) & (self.capacity - 1)

    def __setitem__(self, key, value):
        slot, e = self._lookup(key)
        if e != -1:
            self.entries[e][1] = value     # cập nhật tại chỗ nên vị trí không đổi
            return
        self.indices[slot] = len(self.entries)
        self.entries.append([key, value])  # append == thứ tự chèn, miễn phí
        if len(self.entries) * 3 >= self.capacity * 2:
            self._grow()

    def __getitem__(self, key):
        _, e = self._lookup(key)
        if e == -1:
            raise KeyError(key)
        return self.entries[e][1]

    def __delitem__(self, key):
        _, e = self._lookup(key)
        if e == -1:
            raise KeyError(key)
        self.entries[e] = None             # để lại lỗ hổng; dọn dẹp khi grow

    def keys(self):
        return [e[0] for e in self.entries if e is not None]

    def _grow(self):
        self.capacity *= 2
        self.indices = [-1] * self.capacity
        self.entries = [e for e in self.entries if e is not None]   # bỏ các lỗ hổng
        for e_idx, entry in enumerate(self.entries):
            i = hash(entry[0]) & (self.capacity - 1)
            while self.indices[i] != -1:
                i = (i + 1) & (self.capacity - 1)
            self.indices[i] = e_idx


d = CompactDict()
for k, v in [("z", 1), ("a", 2), ("m", 3)]:
    d[k] = v
assert d.keys() == ["z", "a", "m"]        # thứ tự chèn, không phải thứ tự sắp xếp
del d["a"]
assert d.keys() == ["z", "m"]

Chú ý hệ quả của các “lỗ hổng”: một dict bị xóa nhiều sẽ giữ entry array phình to cho tới lần resize kế tiếp dọn dẹp nó. collections.OrderedDict vẫn tồn tại và chưa lỗi thời — nó là một doubly linked list phủ lên các entry, nên hỗ trợ move_to_end() và popitem(last=False) ở O(1) và so sánh == có tính đến thứ tự, điều mà dict thường không làm. LRU cache là use case kinh điển (functools.lru_cache được xây trên đúng ý tưởng này; xem ../../backend/vi/11-caching.md).

Bảng tổng hợp độ phức tạp

Thao tác	Trung bình	Worst case	Vì sao worst case như vậy
get(key)	O(1)	O(n)	Mọi key collide → quét một chain / một cluster
put(key, v)	O(1) amortized	O(n)	Như trên, cộng thêm O(n) cho lần rehash khi resize
delete(key)	O(1)	O(n)	Như trên
in / kiểm tra thành viên	O(1)	O(n)	Như trên
Duyệt toàn bộ entry	O(n + capacity)	O(n + capacity)	Phải bỏ qua slot trống (CPython: O(n) — entry dày đặc)
Tìm key nhỏ nhất / lớn nhất	O(n)	O(n)	Hoàn toàn không có thứ tự — đây là thứ hash table không làm được
Range query a ≤ k ≤ b	O(n)	O(n)	Cùng lý do
Bộ nhớ	O(n / α) ≈ O(n)		Array được cố ý giữ trống khoảng 1/3

Hai dòng cuối chính là đánh đổi thật sự. Hash table mua O(1) cho truy cập điểm bằng cách phá bỏ thứ tự. Ngay khi bạn cần “key nhỏ nhất”, “key kế tiếp sau x”, hay “mọi key giữa a và b”, bạn cần một balanced tree (./11-balanced-and-multiway-trees.md) hoặc một array đã sắp xếp cùng binary search (./09-search-algorithms.md). Đây đúng là lý do B-tree index trong database áp đảo hash index: chúng phục vụ được cả equality lẫn range lẫn ORDER BY — xem ../../postgresql-dba/vi/08-indexing-strategies.md và ./18-indexing.md.

Thực tế bạn dùng gì trong Python

from collections import Counter, defaultdict

# dict / set — là hash table, và là lựa chọn mặc định đúng cho truy cập theo key
seen = set()                              # membership O(1), add O(1)
index = {"a": 1, "b": 2}

# Đếm: idiom chuẩn, và bên dưới vẫn là dict
counts = Counter("mississippi")           # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

# Gom nhóm: tránh được điệu nhảy "kiểm tra rồi mới chèn"
groups = defaultdict(list)
for word in ["apple", "avocado", "banana"]:
    groups[word[0]].append(word)          # {'a': [...], 'b': [...]}

# frozenset / tuple làm key phức hợp — hashable vì bất biến
edge_weights = {frozenset({"A", "B"}): 4} # cạnh vô hướng như một key không thứ tự

Hai idiom đáng nêu tên vì chúng biến code bậc hai thành code tuyến tính:

# Two-sum ở O(n) thay vì O(n^2): đánh đổi bộ nhớ để bỏ vòng lặp trong
def two_sum(nums, target):
    seen = {}                             # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:            # O(1) thay vì quét toàn bộ tiền tố
            return seen[target - x], i
        seen[x] = i
    return None

# Khử trùng lặp mà vẫn giữ thứ tự — key của dict vừa có thứ tự vừa duy nhất
def dedupe(items):
    return list(dict.fromkeys(items))

Best Practices

• Dùng cấu trúc có sẵn. dict và set là code C được tối ưu rất kỹ, có hash randomized, layout compact, và fast path riêng cho trường hợp key toàn là chuỗi. Chỉ tự viết để học, hoặc cho một trường hợp thật sự đặc thù (bảng open addressing chứa int nguyên thủy, không boxing) mà bạn đã đo đạc.
• Key phải bất biến, và hash phải được tính từ đúng những field mà __eq__ so sánh. @dataclass(frozen=True) hoặc NamedTuple làm đúng chuyện này miễn phí. Sửa một object sau khi đã dùng nó làm key là loại bug hiện ra dưới dạng entry biến mất một cách khó hiểu.
• Đừng bao giờ viết __eq__ mà không viết __hash__. Python biến class thành unhashable để chặn bạn; trong Java và C# chẳng có gì chặn cả và bug sẽ hoàn toàn im lặng.
• Cấp phát trước khi đã biết kích thước. dict.fromkeys(...), một comprehension, hoặc dict(zip(...)) tránh được cả chuỗi rehash. Nếu không, grow lên 10⁶ entry sẽ copy tổng cộng khoảng 2×10⁶ entry.
• Theo dõi load factor nếu bạn tự viết. Grow ở 0.75 (chaining) hoặc 0.66 (open addressing) và luôn nhân đôi capacity — đừng bao giờ tăng theo một hằng số cộng, vì điều đó khiến insert trở thành O(n) amortized thay vì O(1).
• Dùng capacity lũy thừa của 2 với hash tốt, hoặc capacity số nguyên tố với hash yếu. & (cap-1) chỉ giữ lại các bit thấp, nên hash có entropy kém ở bit thấp sẽ dồn cụm rất tệ. CPython né chuyện này bằng cách nhiễu loạn chuỗi probe với các bit cao của hash.
• Đừng giả định gì về thứ tự duyệt, trừ trong Python. Thứ tự của dict trong CPython là bảo đảm ở mức ngôn ngữ; Go cố ý ngẫu nhiên hóa thứ tự duyệt map để chặn bạn phụ thuộc vào nó; thứ tự của HashMap trong Java đổi sau mỗi lần resize. Code dựa vào thứ tự tình cờ sẽ vỡ khi nâng cấp.
• Đừng bao giờ để input do kẻ tấn công kiểm soát đổ vào một dict không giới hạn mà không nghĩ tới flooding. Giới hạn số tham số, giữ hash randomization bật, và không bao giờ ghim PYTHONHASHSEED trên production.
• Đừng dùng hash table khi bạn cần thứ tự. Range, “key kế tiếp sau x”, top-k, và duyệt theo thứ tự đều cần một tree, một heap (./12-heaps-and-priority-queues.md), hoặc một array đã sắp xếp. Sort key của dict ở mỗi request để giả lập thứ tự là O(n log n) mỗi lần gọi và là một performance bug rất phổ biến.
• Nhớ chi phí bộ nhớ. Một dict Python chứa một triệu int nhỏ tốn hàng chục megabyte; cùng dữ liệu đó trong array của module array hoặc trong một list đã sắp xếp chỉ tốn một phần nhỏ. Khi bộ nhớ là ràng buộc chính và lookup thưa thớt, array đã sắp xếp cộng binary search có thể là cấu trúc tốt hơn.
• Với kiểm tra thành viên gần đúng ở quy mô cực lớn, cân nhắc Bloom filter. Nó trả lời “chắc chắn không có” / “có thể có” chỉ với vài bit mỗi phần tử — công cụ đúng khi một hash set chính xác không thể nhét vừa RAM.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Hash table — Wikipedia
• Open addressing — Wikipedia
• Collision resolution / separate chaining — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 11: Hash Tables
• PEP 456 — Secure and interchangeable hash algorithm (SipHash)
• Python Documentation — object.__hash__
• Python Documentation — collections (Counter, defaultdict, OrderedDict)
• CPython source — Objects/dictobject.c (design notes at the top)
• Python Documentation — TimeComplexity of built-in types
• Big-O Cheat Sheet
• SipHash — Wikipedia
• VisuAlgo — Hash Table

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

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        # Derive the hash from exactly the fields __eq__ compares.
        # Hashing a tuple of them is the idiomatic and correct way to do it.
        return hash((self.x, self.y))

_MISSING = object()   # sentinel so that a stored value of None is not ambiguous


class ChainedHashTable:
    """Hash table with separate chaining. Each bucket is a Python list of
    (key, value) pairs — a real implementation would use a linked list, but a
    list is the same asymptotics and easier to read."""

    def __init__(self, capacity=8):
        self.capacity = capacity          # always a power of two
        self.size = 0                     # number of live entries
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        # `& (capacity - 1)` == `% capacity` when capacity is a power of two,
        # and it is far cheaper than a division. It also handles negative
        # hashes correctly in Python.
        return hash(key) & (self.capacity - 1)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                  # key already present: overwrite
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > self.capacity * 0.75:   # keep the load factor bounded
            self._resize(self.capacity * 2)

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def delete(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)             # deletion is trivial: no tombstone needed
                self.size -= 1
                return True
        return False

    def _resize(self, new_capacity):
        # Every key must be rehashed: the slot depends on the capacity.
        old_buckets = self.buckets
        self.capacity = new_capacity
        self.buckets = [[] for _ in range(new_capacity)]
        for bucket in old_buckets:
            for key, value in bucket:
                self.buckets[hash(key) & (new_capacity - 1)].append((key, value))

    def __len__(self):
        return self.size

    def __contains__(self, key):
        return self.get(key, _MISSING) is not _MISSING


t = ChainedHashTable()
for word in ["apricot", "cat", "dog", "fig", "banana"]:
    t.put(word, len(word))
assert t.get("dog") == 3 and t.get("nope") is None
assert t.delete("cat") and "cat" not in t

_EMPTY = object()     # slot never used — ends a probe sequence
_DELETED = object()   # tombstone — does NOT end a probe sequence


class LinearProbingHashTable:
    """Open-addressed hash table with linear probing and tombstone deletion."""

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0     # live entries
        self.used = 0     # live entries + tombstones = slots that end no probe
        self.slots = [_EMPTY] * capacity

    def _probe(self, key):
        """Yield the slot indices for `key`, wrapping around the table."""
        i = hash(key) & (self.capacity - 1)
        for _ in range(self.capacity):
            yield i
            i = (i + 1) & (self.capacity - 1)   # linear probing: step of 1

    def put(self, key, value):
        first_tombstone = None
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is _DELETED:
                if first_tombstone is None:
                    first_tombstone = i         # remember it, but keep probing:
                continue                        # the key may still be further on
            if slot is _EMPTY:
                # An empty slot proves the key is absent. Insert it, reusing the
                # first tombstone we passed so the table stays compact.
                if first_tombstone is None:
                    self.slots[i] = (key, value)
                    self.used += 1              # consumed a never-used slot
                else:
                    self.slots[first_tombstone] = (key, value)
                self.size += 1
                self._maybe_grow()
                return
            if slot[0] == key:
                self.slots[i] = (key, value)    # overwrite existing key
                return
        raise RuntimeError("hash table full")   # unreachable: we grow at 2/3 load

    def get(self, key, default=None):
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is _EMPTY:
                return default                  # never used: the key cannot be here
            if slot is _DELETED:
                continue                        # keep walking past tombstones
            if slot[0] == key:
                return slot[1]
        return default

    def delete(self, key):
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is _EMPTY:
                return False
            if slot is not _DELETED and slot[0] == key:
                self.slots[i] = _DELETED        # tombstone, NOT _EMPTY
                self.size -= 1                  # `used` stays: the slot still blocks
                return True
        return False

    def _maybe_grow(self):
        # Probe length depends on `used`, not `size` — tombstones cost just as
        # much as live entries when walking a probe sequence.
        if self.used * 3 >= self.capacity * 2:          # load factor >= 2/3
            if self.size * 3 >= self.capacity:
                self._resize(self.capacity * 2)         # genuinely full: grow
            else:
                self._resize(self.capacity)             # mostly tombstones: purge

    def _resize(self, new_capacity):
        old = self.slots
        self.capacity = new_capacity
        self.slots = [_EMPTY] * new_capacity
        self.size = 0
        self.used = 0
        for slot in old:
            if slot is not _EMPTY and slot is not _DELETED:
                self.put(*slot)                 # tombstones are dropped, not copied

    def __len__(self):
        return self.size


t = LinearProbingHashTable()
for i, word in enumerate(["apricot", "cat", "dog", "fig", "banana"]):
    t.put(word, i)
assert t.get("dog") == 2
t.delete("cat")
assert t.get("dog") == 2      # the probe chain survived the deletion
assert t.get("cat") is None

class BadKey:
    def __init__(self, v):
        self.v = v

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.v == other.v

    def __hash__(self):
        return 0          # legal! satisfies "a == b implies hash(a) == hash(b)"
                          # ...and turns every dict of BadKey into a linked list


d = {}
for i in range(20_000):
    d[BadKey(i)] = i      # O(n^2): each insert scans every previous entry

# String hashes differ between processes — the seed is random per process
$ python3 -c "print(hash('spam'))"
-4157093734590757790
$ python3 -c "print(hash('spam'))"
 8093131396522585862

# Setting the seed makes hashing reproducible — useful for debugging,
# dangerous in anything reachable from the network
$ PYTHONHASHSEED=0 python3 -c "print(hash('spam'))"

capacity 8, three keys inserted in the order  a, b, c

indices:   [ -1,  1, -1,  0, -1,  2, -1, -1 ]   ← 8 small ints, mostly empty
                  │       │       │
                  │       │       └──────────────┐
                  │       └───────────┐          │
                  ▼                   ▼          ▼
entries:   [ (h_a, 'a', 1), (h_b, 'b', 2), (h_c, 'c', 3) ]   ← dense, in order

class CompactDict:
    """A simplified model of CPython's dict: a sparse index array pointing
    into a dense, insertion-ordered entry array."""

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.indices = [-1] * capacity     # -1 means "empty slot"
        self.entries = []                  # [key, value] pairs, in insertion order

    def _lookup(self, key):
        """Return (slot, entry_index); entry_index is -1 when the key is absent."""
        i = hash(key) & (self.capacity - 1)
        while True:
            e = self.indices[i]
            if e == -1:
                return i, -1               # free slot: key is not in the table
            if self.entries[e] is not None and self.entries[e][0] == key:
                return i, e
            i = (i + 1) & (self.capacity - 1)

    def __setitem__(self, key, value):
        slot, e = self._lookup(key)
        if e != -1:
            self.entries[e][1] = value     # in-place update keeps the position
            return
        self.indices[slot] = len(self.entries)
        self.entries.append([key, value])  # append == insertion order, for free
        if len(self.entries) * 3 >= self.capacity * 2:
            self._grow()

    def __getitem__(self, key):
        _, e = self._lookup(key)
        if e == -1:
            raise KeyError(key)
        return self.entries[e][1]

    def __delitem__(self, key):
        _, e = self._lookup(key)
        if e == -1:
            raise KeyError(key)
        self.entries[e] = None             # leave a hole; compaction happens on grow

    def keys(self):
        return [e[0] for e in self.entries if e is not None]

    def _grow(self):
        self.capacity *= 2
        self.indices = [-1] * self.capacity
        self.entries = [e for e in self.entries if e is not None]   # drop the holes
        for e_idx, entry in enumerate(self.entries):
            i = hash(entry[0]) & (self.capacity - 1)
            while self.indices[i] != -1:
                i = (i + 1) & (self.capacity - 1)
            self.indices[i] = e_idx


d = CompactDict()
for k, v in [("z", 1), ("a", 2), ("m", 3)]:
    d[k] = v
assert d.keys() == ["z", "a", "m"]        # insertion order, not sorted order
del d["a"]
assert d.keys() == ["z", "m"]

from collections import Counter, defaultdict

# dict / set — hash tables, and the right default for keyed access
seen = set()                              # O(1) membership, O(1) add
index = {"a": 1, "b": 2}

# Counting: the idiom, and it is a dict underneath
counts = Counter("mississippi")           # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

# Grouping: avoids the "check then insert" dance
groups = defaultdict(list)
for word in ["apple", "avocado", "banana"]:
    groups[word[0]].append(word)          # {'a': [...], 'b': [...]}

# frozenset / tuple as a compound key — hashable because immutable
edge_weights = {frozenset({"A", "B"}): 4} # undirected edge as an unordered key

# Two-sum in O(n) instead of O(n^2): trade memory for the inner loop
def two_sum(nums, target):
    seen = {}                             # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:            # O(1) instead of scanning the prefix
            return seen[target - x], i
        seen[x] = i
    return None

# Deduplicate while preserving order — dict keys are ordered and unique
def dedupe(items):
    return list(dict.fromkeys(items))