Hash table: va chạm, load factor và vì sao O(1) chỉ là kỳ vọng

Câu hỏi bài này trả lời: vì sao tra cứu bằng hash table được gọi là O(1), nhưng một bảng quá đầy hoặc một hàm băm tệ lại chậm theo kiểu O(n), và load factor làm số bước dò (probe) đổi bao nhiêu?

Cần biết trước: Python cơ bản và ký hiệu big-O. Lab dùng thư viện chuẩn của Python 3.14.4 trên macOS arm64, không cần database hay mạng. Phần quan sát dict chỉ đúng cho bản Python này; bài không suy ra phiên bản hay ngôn ngữ khác.

Hàm băm, mảng và hai cách xử lý va chạm

Hash table đổi khóa bất kỳ thành chỉ số mảng: chỉ số = băm(khóa) mod m, với m là số ô (bucket). Số khóa có thể có lớn hơn m rất nhiều, nên có hai khóa rơi vào cùng một ô là điều không tránh được (nguyên lý chuồng bồ câu). Hai cách xử lý phổ biến:

• Chaining (nối chuỗi): mỗi ô giữ một danh sách các khóa rơi vào ô đó. Tìm kiếm đi tới ô rồi so sánh lần lượt trong danh sách.
• Open addressing (địa chỉ mở), ở đây là linear probing: mọi khóa nằm ngay trong mảng. Khóa đụng ô đã có người thì dò sang ô kế tiếp cho tới ô trống; tìm kiếm đi theo đúng đường đó và dừng ở ô chứa khóa, hoặc ở ô trống đầu tiên khi khóa không có.

Bài đo “probe” với nghĩa riêng cho từng cách: với chaining là số khóa phải so sánh; với linear probing là số ô phải xem, tính cả ô chứa khóa hoặc ô trống chặn đường dò. Tạo thư mục trống rồi lưu hai cách cài tối thiểu (chưa có xóa và chưa nới bảng):

import hashlib
from collections.abc import Callable


def spread(key: int) -> int:
    """Hàm băm gần như ngẫu nhiên: 64 bit đầu của BLAKE2b."""
    digest = hashlib.blake2b(key.to_bytes(8, "little"), digest_size=8).digest()
    return int.from_bytes(digest, "little")


def remainder_only(key: int) -> int:
    """Hàm băm tệ: giữ nguyên khóa, bảng sẽ lấy phần dư khi chia."""
    return key


class Chaining:
    """Mỗi bucket là một danh sách; probe là số khóa phải so sánh."""

    def __init__(self, size: int, hash_fn: Callable[[int], int] = spread) -> None:
        self.size = size
        self.hash_fn = hash_fn
        self.buckets: list[list[int]] = [[] for _ in range(size)]

    def insert(self, key: int) -> bool:
        """Trả về True nếu bucket đã có khóa khác (va chạm)."""
        bucket = self.buckets[self.hash_fn(key) % self.size]
        collided = bool(bucket)
        bucket.append(key)
        return collided

    def search(self, key: int) -> tuple[bool, int]:
        bucket = self.buckets[self.hash_fn(key) % self.size]
        probes = 0
        for stored in bucket:
            probes += 1
            if stored == key:
                return True, probes
        return False, probes


class LinearProbing:
    """Một mảng ô; probe là số ô phải xem, gồm ô chứa khóa hoặc ô trống chặn đường dò."""

    def __init__(self, size: int, hash_fn: Callable[[int], int] = spread) -> None:
        self.size = size
        self.hash_fn = hash_fn
        self.slots: list[int | None] = [None] * size
        self.count = 0

    def insert(self, key: int) -> bool:
        """Trả về True nếu ô đầu tiên đã bị chiếm (va chạm)."""
        if self.count == self.size:
            raise ValueError("bảng đã đầy")
        index = self.hash_fn(key) % self.size
        collided = self.slots[index] is not None
        while self.slots[index] is not None:
            index = (index + 1) % self.size
        self.slots[index] = key
        self.count += 1
        return collided

    def search(self, key: int) -> tuple[bool, int]:
        index = self.hash_fn(key) % self.size
        probes = 1
        while self.slots[index] is not None:
            if self.slots[index] == key:
                return True, probes
            index = (index + 1) % self.size
            probes += 1
        return False, probes

python3 --version

Va chạm đến rất sớm

Nếu băm rải đều, xác suất n khóa đầu đều rơi vào ô khác nhau xấp xỉ exp(−n²/2m). Khóa đầu tiên đụng ô đã có người vì thế thường xuất hiện sau khoảng √(2·ln 2·m) khóa, tức 1,18·√m (nghịch lý ngày sinh). Với m = 16.384 đó là khoảng 151 khóa, khi load factor mới chưa tới 1%. Lab lặp 2.000 lần: mỗi lần cho khóa ngẫu nhiên vào bảng 16.384 ô cho tới khi có va chạm, rồi so trung vị với công thức:

import math
import random
import statistics

from hashtable import spread

SIZE = 1 << 14
TRIALS = 2000


def first_collision(rng: random.Random) -> int:
    seen: set[int] = set()
    while True:
        bucket = spread(rng.getrandbits(48)) % SIZE
        if bucket in seen:
            return len(seen) + 1
        seen.add(bucket)


rng = random.Random(17)
counts = [first_collision(rng) for _ in range(TRIALS)]
median = statistics.median(counts)
formula = math.sqrt(2 * math.log(2) * SIZE)
print(f"bảng {SIZE} bucket, {TRIALS} lần thử")
print(f"khóa thứ {median:.0f} (trung vị) là khóa đầu tiên đụng bucket đã có người")
print(f"công thức sqrt(2 ln 2 · m) = {formula:.1f}; load factor lúc đó {median / SIZE:.4f}")
assert abs(median - formula) / formula < 0.1
print("va chạm đầu tiên khớp công thức")

python3 -B birthday.py

bảng 16384 bucket, 2000 lần thử
khóa thứ 154 (trung vị) là khóa đầu tiên đụng bucket đã có người
công thức sqrt(2 ln 2 · m) = 150.7; load factor lúc đó 0.0094
va chạm đầu tiên khớp công thức

Va chạm không báo hiệu bảng đang quá đầy; nó là trạng thái bình thường, nên mọi hash table phải có cách xử lý nó ngay từ đầu. Thứ cần điều khiển là mỗi va chạm tốn bao nhiêu bước dò, và đó là việc của load factor.

Load factor quyết định số probe

Load factor α = n/m là số khóa chia số ô. Với băm đều và độc lập, số probe kỳ vọng theo α như sau (chaining chịu được α lớn hơn 1, linear probing buộc α < 1):

Đây là các công thức kinh điển của giáo trình, trong đó phần linear probing là phân tích của Knuth (The Art of Computer Programming, tập 3, mục 6.4). Bài không có bản sách để dẫn trang nên không dựa vào việc đã đọc sách mà kiểm bằng đo: lab dựng bảng 65.536 ô, nạp tới α = 0,25; 0,5; 0,75; 0,9, lấy trung bình trên 3 bảng với khóa khác nhau, và dùng 20.000 khóa chưa có để đo trường hợp “không thấy”. Mỗi cặp số in dạng đo/công thức; lab dừng nếu có số nào lệch quá 10%. Cột va chạm là tỉ lệ khóa chèn vào bucket đã có khóa trong chaining, công thức xấp xỉ 1 − (1 − e^(−α))/α.

import random
import statistics

from hashtable import Chaining, LinearProbing

SIZE = 1 << 16
FRESH = 20_000
LOADS = (0.25, 0.5, 0.75, 0.9)
SEEDS = (17, 18, 19)


def draw(rng: random.Random, count: int, avoid: set[int]) -> list[int]:
    keys: list[int] = []
    seen = set(avoid)
    while len(keys) < count:
        key = rng.getrandbits(48)
        if key not in seen:
            seen.add(key)
            keys.append(key)
    return keys


def run(table_class, load: float, seed: int) -> tuple[float, float, float]:
    rng = random.Random(seed)
    count = int(SIZE * load)
    keys = draw(rng, count, set())
    fresh = draw(rng, FRESH, set(keys))
    table = table_class(SIZE)
    collisions = sum(table.insert(key) for key in keys)
    found = [table.search(key) for key in keys]
    missing = [table.search(key) for key in fresh]
    assert all(ok for ok, _ in found) and not any(ok for ok, _ in missing)
    return (
        collisions / count,
        statistics.fmean(p for _, p in found),
        statistics.fmean(p for _, p in missing),
    )


def average(table_class, load: float) -> tuple[float, ...]:
    rows = [run(table_class, load, seed) for seed in SEEDS]
    return tuple(statistics.fmean(column) for column in zip(*rows))


def close(measured: float, formula: float) -> bool:
    return abs(measured - formula) / formula < 0.1


for load in LOADS:
    count = int(SIZE * load)
    occupied = SIZE * (1 - (1 - 1 / SIZE) ** count)
    c_collide, c_ok, c_fail = average(Chaining, load)
    _, l_ok, l_fail = average(LinearProbing, load)
    f_collide = 1 - occupied / count
    f_c_ok = 1 + load / 2 - load / (2 * SIZE)
    f_c_fail = load
    f_l_ok = 0.5 * (1 + 1 / (1 - load))
    f_l_fail = 0.5 * (1 + 1 / (1 - load) ** 2)
    print(
        f"load {load:.2f} | va chạm {c_collide:.4f}/{f_collide:.4f}"
        f" | chaining thấy {c_ok:.3f}/{f_c_ok:.3f} vắng {c_fail:.3f}/{f_c_fail:.3f}"
        f" | linear thấy {l_ok:.3f}/{f_l_ok:.3f} vắng {l_fail:.3f}/{f_l_fail:.3f}"
    )
    assert close(c_collide, f_collide) and close(c_ok, f_c_ok) and close(c_fail, f_c_fail)
    assert close(l_ok, f_l_ok) and close(l_fail, f_l_fail)
print("đo khớp công thức, sai số dưới 10%")

python3 -B probes.py

load 0.25 | va chạm 0.1149/0.1152 | chaining thấy 1.125/1.125 vắng 0.250/0.250 | linear thấy 1.164/1.167 vắng 1.386/1.389
load 0.50 | va chạm 0.2134/0.2131 | chaining thấy 1.252/1.250 vắng 0.500/0.500 | linear thấy 1.502/1.500 vắng 2.508/2.500
load 0.75 | va chạm 0.2968/0.2965 | chaining thấy 1.375/1.375 vắng 0.755/0.750 | linear thấy 2.505/2.500 vắng 8.487/8.500
load 0.90 | va chạm 0.3418/0.3406 | chaining thấy 1.452/1.450 vắng 0.904/0.900 | linear thấy 5.521/5.500 vắng 51.871/50.500

Số đo bám công thức sát hơn nhiều so với ngưỡng 10% mà lab đòi. Ba điều đọc ra từ bảng:

• Chaining tăng chậm, linear probing tăng vọt. Từ α = 0,5 lên 0,9, số so sánh của chaining khi khóa vắng đi từ 0,5 lên 0,9; số ô linear probing phải xem đi từ 2,5 lên 51,9, gấp khoảng 20 lần. Giáo trình giải thích bằng hiện tượng cụm: các ô bị chiếm dính thành đoạn liền, đoạn dài dễ bị trúng hơn và còn dài thêm khi có khóa mới rơi vào (bài không đo độ dài cụm).
• Va chạm có sớm và nhiều. Ngay ở α = 0,5, hơn một phần năm khóa chèn vào bucket đã có người (đo ở chaining). Chọn α thấp không tránh được va chạm, chỉ giữ cho chuỗi dò ngắn.
• “O(1)” cần α bị chặn. Số probe là hằng số khi α nhỏ hơn một hằng số cố định, nên bảng thực tế cấp mảng lớn hơn và băm lại toàn bộ khóa khi α chạm ngưỡng. Mỗi lần nới tốn O(n) nhưng hiếm; nếu số ô tăng theo cấp số nhân thì chi phí trung bình trên mỗi lần chèn vẫn là hằng số (lập luận chuẩn của phân tích amortized, bài không đo chi phí nới).

Ngưỡng do người thiết kế chọn. Ghi chú trong mã nguồn CPython cho tải tối đa của dict viết rằng các tỉ lệ quanh 1/2 đến 2/3 có vẻ chạy tốt trong thực tế, và dict dùng 2/3 (xem phần quan sát dict bên dưới).

Công thức chỉ đúng khi băm đều

Mọi con số trên giả định hàm băm rải khóa đều và độc lập. Hàm băm tệ phá giả định đó mà không cần bảng đầy. Lab nạp 2.000 khóa là bội số của kích thước bảng (16.384 ô, α ≈ 0,12) hai lần: một lần qua hàm băm gần ngẫu nhiên (BLAKE2b), một lần qua hàm chỉ lấy dư (khóa giữ nguyên, bảng lấy khóa mod m). Đây là mô hình của khóa có bước nhảy trùng kích thước bảng, như địa chỉ căn lề hoặc mã tăng theo bước cố định. Dưới hàm chỉ lấy dư, mọi khóa rơi vào ô 0.

import statistics

from hashtable import Chaining, LinearProbing, remainder_only, spread

SIZE = 1 << 14
COUNT = 2000
FRESH = 1000

keys = [i * SIZE for i in range(COUNT)]
fresh = [(COUNT + i) * SIZE for i in range(FRESH)]
results = {}
for name, table_class in (("chaining", Chaining), ("linear", LinearProbing)):
    for label, hash_fn in (("BLAKE2b", spread), ("lấy dư", remainder_only)):
        table = table_class(SIZE, hash_fn)
        for key in keys:
            table.insert(key)
        found = statistics.fmean(table.search(key)[1] for key in keys)
        missing = statistics.fmean(table.search(key)[1] for key in fresh)
        results[name, label] = (found, missing)
        print(f"{name:8} {label:8} tìm thấy {found:8.2f} không thấy {missing:8.2f}")

for name in ("chaining", "linear"):
    assert results[name, "lấy dư"][0] == (COUNT + 1) / 2
assert results["chaining", "lấy dư"][1] == COUNT
assert results["linear", "lấy dư"][1] == COUNT + 1
assert all(results[n, "lấy dư"][0] > 100 * results[n, "BLAKE2b"][0] for n in ("chaining", "linear"))
print("hàm băm tệ làm probe tăng theo số khóa")

python3 -B badhash.py

chaining BLAKE2b  tìm thấy     1.06 không thấy     0.13
chaining lấy dư   tìm thấy  1000.50 không thấy  2000.00
linear   BLAKE2b  tìm thấy     1.07 không thấy     1.15
linear   lấy dư   tìm thấy  1000.50 không thấy  2001.00

Các dòng lấy dư trùng đúng với tính tay: mọi khóa nằm trong cùng một chuỗi (hoặc một đoạn ô liền nhau bắt đầu từ ô 0) và khóa thứ k cần k probe, nên tìm thấy trung bình (n+1)/2 = 1000,5; khóa vắng phải đi hết n khóa (chaining) hoặc n+1 ô kể cả ô trống (linear probing). Cùng bảng, cùng khóa, chỉ đổi hàm băm: cỡ 1 probe so với cỡ 1.000 probe. Vì vậy “O(1)” của hash table là kỳ vọng với một hàm băm và một phân phối khóa cho trước. Một thao tác vẫn có thể tốn O(n), và nạp n khóa có thể tốn O(n²).

Quan sát dict thật

CPython dùng open addressing nhưng chuỗi dò không phải linear probing (nguồn mô tả công thức j = (5·j) + 1 + perturb, với perturb dịch dần theo PERTURB_SHIFT để các bit cao của giá trị băm tham gia), nên công thức linear probing ở trên không áp thẳng cho dict; chúng giải thích vì sao người thiết kế giữ α thấp. Bốn quan sát sau chạy trên dict thật của Python 3.14.4:

1. Thứ tự duyệt là thứ tự chèn. Hướng dẫn Python nói list(d) trả các khóa theo thứ tự chèn, và ghi chú phát hành 3.7 nói tính chất này là một phần chính thức của đặc tả ngôn ngữ. Vì vậy không thể đọc ra vị trí ô hay giá trị băm từ thứ tự duyệt.
2. Mốc nới. Lab đếm các lần sys.getsizeof(d) đổi khi chèn khóa số nguyên rồi so với mô phỏng chính sách từ hai hằng số trong dictobject.c: tải dùng được của bảng n ô là USABLE_FRACTION(n) = (n << 1)/3, và khi đầy, bảng mới có số ô là lũy thừa của 2 nhỏ nhất không nhỏ hơn GROWTH_RATE = số mục × 3 (bảng nhỏ nhất có 8 ô).
3. Băm chuỗi có salt, băm số thì không. Tài liệu dòng lệnh nói nếu không đặt PYTHONHASHSEED (hoặc đặt random) thì giá trị băm của str và bytes được seed ngẫu nhiên; đặt một số nguyên thì seed cố định; đặt 0 tắt randomization. Số nguyên thì băm bằng phép lấy dư theo số nguyên tố sys.hash_info.modulus, nên dự đoán được; lab còn dựng 10.000 số nguyên khác nhau có cùng giá trị băm để xem dict thật chịu ra sao.
4. Cùng hash thì mỗi thao tác tốn O(n). Lab đếm số lần gọi __eq__ khi mọi khóa cùng giá trị băm và khi mỗi khóa một giá trị.

import os
import subprocess
import sys
import time

ORDER = [5, 3, 9, 1, 7, 2, 8, 4]


def insertion_order() -> None:
    table: dict[int, None] = {}
    for key in ORDER:
        table[key] = None
    assert list(table) == ORDER
    print("thứ tự duyệt", list(table), "= thứ tự chèn")


def observed_resizes(limit: int) -> list[int]:
    table: dict[int, None] = {}
    last = sys.getsizeof(table)
    marks = []
    for key in range(limit):
        table[key] = None
        size = sys.getsizeof(table)
        if size != last:
            marks.append(len(table))
            last = size
    return marks


def predicted_resizes(limit: int) -> list[int]:
    marks = [1]
    size = 8
    used = 1
    while used < limit:
        if used == size * 2 // 3:
            size = 1 << (3 * used - 1).bit_length()
            marks.append(used + 1)
        used += 1
    return marks


def resize_policy() -> None:
    seen = observed_resizes(700)
    expected = predicted_resizes(700)
    print("mốc nới quan sát được", seen)
    print("mốc theo hằng số trong nguồn", expected)
    assert seen == expected
    print("mốc nới khớp chính sách 2/3 và gấp 3 số mục")


def child_hash(seed: str | None) -> str:
    env = {k: v for k, v in os.environ.items() if k != "PYTHONHASHSEED"}
    if seed is not None:
        env["PYTHONHASHSEED"] = seed
    result = subprocess.run(
        [sys.executable, "-c", "print(hash('hash-demo'))"],
        env=env,
        capture_output=True,
        text=True,
        check=True,
    )
    return result.stdout.strip()


def hash_seed() -> None:
    free = [child_hash(None) for _ in range(3)]
    fixed = [child_hash("0") for _ in range(2)]
    assert len(set(free)) == 3, free
    assert fixed[0] == fixed[1]
    print("hash(str) ở 3 tiến trình không đặt seed: 3 giá trị khác nhau")
    print("hash(str) ở 2 tiến trình PYTHONHASHSEED=0: cùng một giá trị")
    assert hash(12345) == 12345
    assert hash(12345 + sys.hash_info.modulus) == 12345
    print("hash(12345) =", hash(12345), "; thuật toán băm chuỗi:", sys.hash_info.algorithm)


def build_seconds(keys: list[int]) -> float:
    start = time.perf_counter()
    table: dict[int, None] = {}
    for key in keys:
        table[key] = None
    return time.perf_counter() - start


def integer_collisions() -> None:
    modulus = sys.hash_info.modulus
    count = 10_000
    plain = list(range(1, count + 1))
    crafted = [i * modulus for i in range(1, count + 1)]
    assert len(set(crafted)) == count
    assert {hash(key) for key in crafted} == {0}
    fast = min(build_seconds(plain) for _ in range(3))
    slow = build_seconds(crafted)
    print(f"{count} bội số khác nhau của P đều có hash {hash(modulus)}")
    print(f"dựng dict từ chúng chậm hơn {slow / fast:.0f} lần so với {count} số liên tiếp")
    assert slow > 50 * fast
    print("số nguyên cùng hash dựng được mà không cần biết bí mật nào")


class Key:
    __slots__ = ("value", "bucket")
    comparisons = 0

    def __init__(self, value: int, bucket: int) -> None:
        self.value = value
        self.bucket = bucket

    def __hash__(self) -> int:
        return self.bucket

    def __eq__(self, other: object) -> bool:
        Key.comparisons += 1
        return isinstance(other, Key) and self.value == other.value


def equality_calls(count: int, same_hash: bool) -> tuple[int, dict[Key, None]]:
    Key.comparisons = 0
    table: dict[Key, None] = {}
    for value in range(count):
        table[Key(value, 7 if same_hash else value)] = None
    return Key.comparisons, table


def worst_case() -> None:
    table: dict[Key, None] = {}
    for count in (500, 1000, 2000):
        distinct_calls, _ = equality_calls(count, same_hash=False)
        same_calls, table = equality_calls(count, same_hash=True)
        assert distinct_calls == 0 and same_calls == count * (count - 1) // 2
        print(f"n={count}: hash khác nhau {distinct_calls} lần __eq__, cùng hash {same_calls} lần")
    Key.comparisons = 0
    assert Key(-5, 7) not in table
    assert Key.comparisons == 2000
    print("tra một khóa vắng khi cả 2000 khóa cùng hash:", Key.comparisons, "lần __eq__")


insertion_order()
resize_policy()
hash_seed()
integer_collisions()
worst_case()
print("dict thật khớp mô hình")

python3 -B realdict.py

thứ tự duyệt [5, 3, 9, 1, 7, 2, 8, 4] = thứ tự chèn
mốc nới quan sát được [1, 6, 11, 22, 43, 86, 171, 342, 683]
mốc theo hằng số trong nguồn [1, 6, 11, 22, 43, 86, 171, 342, 683]
mốc nới khớp chính sách 2/3 và gấp 3 số mục
hash(str) ở 3 tiến trình không đặt seed: 3 giá trị khác nhau
hash(str) ở 2 tiến trình PYTHONHASHSEED=0: cùng một giá trị
hash(12345) = 12345 ; thuật toán băm chuỗi: siphash13
10000 bội số khác nhau của P đều có hash 0
số nguyên cùng hash dựng được mà không cần biết bí mật nào
n=500: hash khác nhau 0 lần __eq__, cùng hash 124750 lần
n=1000: hash khác nhau 0 lần __eq__, cùng hash 499500 lần
n=2000: hash khác nhau 0 lần __eq__, cùng hash 1999000 lần
tra một khóa vắng khi cả 2000 khóa cùng hash: 2000 lần __eq__
dict thật khớp mô hình

Đọc kết quả:

• Mốc nới trùng khít. Các lần getsizeof đổi ở khóa thứ 1, 6, 11, 22, 43, 86, 171, 342, 683 đúng bằng mô phỏng: bảng đầu có 8 ô và dùng được 5; khi chèn khóa thứ 6 bảng nới lên 16 ô (dùng được 10), rồi 32, 64… mỗi lần gấp đôi. Mốc được đo gián tiếp qua sys.getsizeof, hàm này chỉ tính bộ nhớ trực tiếp của chính đối tượng; chính sách nới là chi tiết triển khai của bản v3.14.4, không phải hợp đồng của ngôn ngữ.
• Số nguyên không được salt, và cùng hash dựng được mà không cần bí mật. hash(12345) bằng chính 12345, và hash(12345 + P) cũng vậy với P = sys.hash_info.modulus: hai số nguyên khác nhau có cùng giá trị băm, và người ngoài tự dựng được chúng. Lab lấy 10.000 bội số khác nhau của P (hash đều bằng 0) và thấy dựng dict từ chúng chậm hơn cỡ vài nghìn lần so với 10.000 số liên tiếp (3.354 lần ở một lần chạy; lab chỉ đòi trên 50 lần vì thời gian dao động theo máy). Tài liệu chỉ nói randomization áp cho str và bytes. Mục đích của randomization theo tài liệu là chống tấn công từ chối dịch vụ dùng đầu vào chọn trước để đẩy việc dựng dict về trường hợp xấu nhất O(n²), đúng hiện tượng mà phép đo này và phép đo __eq__ ngay dưới cho thấy.
• __eq__ chỉ được gọi khi hash trùng. Với hash khác nhau, dict không gọi __eq__ lần nào trong lúc chèn. Với hash trùng, khóa thứ k phải so với k−1 khóa trước: tổng đúng n(n−1)/2 lần (124.750, 499.500 rồi 1.999.000: gấp đôi n thì công việc gấp bốn), và tra một khóa vắng tốn n lần. Hệ quả cho __hash__ tự viết: tài liệu chỉ đòi hai đối tượng bằng nhau phải có cùng hash, nên trả về hằng số vẫn đúng nhưng biến dict thành danh sách chậm; nên trộn các thành phần tham gia phép so sánh, ví dụ băm tuple của chúng như tài liệu gợi ý.

Chọn gì trong từng tình huống

Giới hạn

• Số đo thuộc Python 3.14.4 trên macOS arm64. Quan sát về dict (mốc nới, siphash13, không gọi __eq__ khi hash khác) là chi tiết triển khai của bản này; bài không kiểm bản Python khác, PyPy hay ngôn ngữ khác như Java, Go, Rust.
• Đơn vị đo là số probe và số lần gọi __eq__, không phải thời gian. Bài không đo cache, kích thước khóa, chi phí hàm băm hay tốc độ thật của chaining so với open addressing; cách đọc số đo xem Đọc benchmark.
• Bài không cài xóa (cần tombstone trong open addressing), quadratic probing, double hashing, Robin Hood hay cuckoo hashing, và không đo chi phí của một lần nới bảng, chỉ đo mốc nới của dict.
• Công thức linear probing không áp trực tiếp cho dict vì chuỗi dò của dict khác; bài dùng chúng để giải thích tác dụng của α, không để dự đoán tốc độ của dict.
• Hai thái cực được đo là hàm băm gần ngẫu nhiên và hàm chỉ lấy dư trên khóa có cấu trúc đặc biệt. Dữ liệu thật nằm giữa hai thái cực đó, và bài không đo hàm băm nào ngoài BLAKE2b, hash() của Python.
• Lab không dựng server hay tệp ngoài thư mục bạn đã tạo; xóa thư mục đó là dọn xong.

Học tiếp và nguồn

• Đọc benchmark: số đo và ngoại suy: cách đọc các con số probe và thời gian mà không suy quá phép đo.
• Python 3.14, Data model: object.__hash__: yêu cầu duy nhất của giá trị băm và việc hash() cắt giá trị trả về.
• Python 3.14, Dòng lệnh và biến môi trường: PYTHONHASHSEED, hash randomization và mục đích chống từ chối dịch vụ.
• Python 3.14, Hướng dẫn: cấu trúc dữ liệu: list(d) theo thứ tự chèn và khóa phải là kiểu bất biến.
• Python 3.14, Các kiểu chuẩn: băm của kiểu số theo phép lấy dư.
• Python 3.14, sys: sys.hash_info và sys.getsizeof.
• Python, What’s New in 3.7: thứ tự chèn của dict trở thành một phần của đặc tả ngôn ngữ.
• CPython v3.14.4, Objects/dictobject.c: USABLE_FRACTION, GROWTH_RATE, PERTURB_SHIFT và công thức chuỗi dò.
• Knuth, The Art of Computer Programming, tập 3, mục 6.4 (sách, không có liên kết): phân tích hashing mà bảng công thức ở trên dựa vào.

Nguồn trực tuyến đọc ngày 2026-10-04; số đo thuộc Python 3.14.4 trên macOS arm64, không có nghiệm thu Linux hay ngôn ngữ khác.