Bloom filter và skip list: ngẫu nhiên có chủ đích, sai số đo được

Câu hỏi bài này trả lời: Bloom filter báo nhầm “có” để đổi lấy bộ nhớ nhỏ, skip list tung đồng xu thay cho phép xoay cây; sai số của hai thứ đó dự đoán và đo được đến đâu, và khi nào không nên dùng chúng?

Cần biết trước: hash table (hàm băm và va chạm) 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. Số đo không nói gì về tốc độ thật của Redis, RocksDB hay thư viện nào khác.

Hai cách dùng ngẫu nhiên

Cả hai cấu trúc dùng ngẫu nhiên, nhưng cái giá khác nhau. Bloom filter chạy với thời gian cố định và đôi khi trả lời sai, chỉ theo một chiều: có thể báo nhầm “có”, không bao giờ báo nhầm “không”. Skip list luôn trả lời đúng; thứ ngẫu nhiên là thời gian chạy, có kỳ vọng O(log n) nhưng từng lần tìm có thể chậm hơn.

Bài đọc hai nguồn: bài báo của Pugh về skip list (CACM 1990, bản công khai trên trang một môn học, đọc đủ cả bài) và bản khảo sát của Broder và Mitzenmacher về Bloom filter (Internet Mathematics, 2004, đọc phần toán học). Bài báo gốc của Bloom (1970) không có bản công khai đọc được lúc viết nên bài không dựa vào nó.

Bloom filter

Cơ chế và công thức

Bloom filter là một mảng m bit, ban đầu toàn 0, cùng k hàm băm có giá trị trong 0..m−1. Thêm một khóa: đặt k bit mà k hàm băm chỉ tới. Hỏi một khóa: nếu có bit nào bằng 0 thì khóa chắc chắn chưa được thêm; nếu cả k bit đều bằng 1 thì khóa có thể có, hoặc đó là dương tính giả do các khóa khác đã đặt đúng những bit này. Bit chỉ được đặt chứ không bị xóa, nên khóa đã thêm luôn báo “có”: không có âm tính giả.

Khảo sát cũng nêu ví dụ m = 8n: xác suất dương tính giả chỉ hơn 0,02. Lab dưới đây dựng lại các con số đó.

Lab: dương tính giả theo k và theo mục tiêu

Tạo thư mục trống rồi lưu cách cài tối thiểu. Mỗi bit chiếm một byte cho dễ đọc (đóng gói bit sẽ nhỏ hơn 8 lần); k vị trí lấy từ k lần băm BLAKE2b riêng của (khóa, chỉ số), gần với giả định “hàm băm độc lập” của công thức.

import hashlib
from collections.abc import Iterator


def positions(key: int, k: int, m: int) -> Iterator[int]:
    """k vị trí bit; mỗi vị trí lấy từ một lần băm BLAKE2b riêng của (khóa, chỉ số)."""
    for i in range(k):
        digest = hashlib.blake2b(
            key.to_bytes(8, "little") + bytes([i]), digest_size=8
        ).digest()
        yield int.from_bytes(digest, "little") % m


class Bloom:
    def __init__(self, m: int, k: int) -> None:
        self.m = m
        self.k = k
        self.bits = bytearray(m)

    def add(self, key: int) -> None:
        for position in positions(key, self.k, self.m):
            self.bits[position] = 1

    def __contains__(self, key: int) -> bool:
        return all(self.bits[position] for position in positions(key, self.k, self.m))

Lab dùng n = 10.000 khóa và 200.000 khóa chưa có để đếm dương tính giả. Mỗi cấu hình dựng 3 filter với khóa khác nhau rồi lấy trung bình. Lab dừng nếu có khóa đã thêm bị báo “không có”, nếu số đo lệch công thức từ 10% trở lên, hoặc nếu k cho dương tính giả thấp nhất không rơi vào 5 hoặc 6 (công thức cho k tối ưu là 5,55 khi m = 8n). Phần hai chọn kích thước từ mục tiêu: m/n = −ln ε / (ln 2)² bit mỗi khóa và k = round(−log₂ ε).

import math
import random

from bloom import Bloom

N = 10_000
FRESH = 200_000
SEEDS = (1, 2, 3)


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


def measure(m: int, k: int) -> float:
    rates = []
    for seed in SEEDS:
        members = draw(seed, N, set())
        fresh = draw(seed + 100, FRESH, set(members))
        bloom = Bloom(m, k)
        for key in members:
            bloom.add(key)
        assert all(key in bloom for key in members), "có âm tính giả"
        rates.append(sum(1 for key in fresh if key in bloom) / FRESH)
    return sum(rates) / len(rates)


def formula(m: int, n: int, k: int) -> float:
    return (1 - math.exp(-k * n / m)) ** k


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


m = 8 * N
measured_by_k = {}
for k in range(1, 11):
    measured = measure(m, k)
    expected = formula(m, N, k)
    measured_by_k[k] = measured
    print(f"m/n=8 k={k:2}: đo {measured:.3%} công thức {expected:.3%}")
    assert close(measured, expected)
best = min(measured_by_k, key=measured_by_k.__getitem__)
print(f"k tối ưu theo công thức ln2·m/n = {math.log(2) * m / N:.2f}; đo thấp nhất ở k={best}")
assert best in (5, 6)
for target in (0.1, 0.01, 0.001):
    bits = -math.log(target) / math.log(2) ** 2
    size = math.ceil(N * bits)
    k = round(-math.log2(target))
    measured = measure(size, k)
    expected = formula(size, N, k)
    print(f"mục tiêu {target:.1%}: {bits:.2f} bit/khóa, k={k}: đo {measured:.3%} công thức {expected:.3%}")
    assert close(measured, expected) and close(measured, target)
print("không có âm tính giả; tỉ lệ dương tính giả đo khớp công thức, sai số dưới 10%")

python3 -B bloom_fp.py

m/n=8 k= 1: đo 11.801% công thức 11.750%
m/n=8 k= 2: đo 4.921% công thức 4.893%
m/n=8 k= 3: đo 3.081% công thức 3.058%
m/n=8 k= 4: đo 2.410% công thức 2.397%
m/n=8 k= 5: đo 2.178% công thức 2.168%
m/n=8 k= 6: đo 2.165% công thức 2.158%
m/n=8 k= 7: đo 2.263% công thức 2.293%
m/n=8 k= 8: đo 2.517% công thức 2.549%
m/n=8 k= 9: đo 2.904% công thức 2.922%
m/n=8 k=10: đo 3.367% công thức 3.419%
k tối ưu theo công thức ln2·m/n = 5.55; đo thấp nhất ở k=6
mục tiêu 10.0%: 4.79 bit/khóa, k=3: đo 10.058% công thức 10.071%
mục tiêu 1.0%: 9.59 bit/khóa, k=7: đo 1.020% công thức 1.004%
mục tiêu 0.1%: 14.38 bit/khóa, k=10: đo 0.102% công thức 0.100%
không có âm tính giả; tỉ lệ dương tính giả đo khớp công thức, sai số dưới 10%

Đọc kết quả:

• k có điểm tối ưu. Với 8 bit mỗi khóa, k = 1 cho 11,8% dương tính giả; tăng k làm giảm tới k = 5 hoặc 6 (khoảng 2,2%, đúng ví dụ “hơn 0,02” của khảo sát), rồi dương tính giả tăng lại vì thêm hàm băm là thêm bit 1 và filter đầy dần.
• Công thức đủ để chọn kích thước. Số đo bám công thức trong khoảng 2% ở mọi dòng. Muốn dương tính giả 1% thì cần khoảng 9,6 bit mỗi khóa và 7 hàm băm, muốn 0,1% thì 14,4 bit và 10 hàm băm; con số này phụ thuộc m/n, không phụ thuộc kích thước của khóa. Với khóa 8 byte (64 bit), 9,6 bit mỗi khóa nhỏ hơn khoảng 6,7 lần chỉ riêng phần dữ liệu khóa thô, chưa tính chi phí của một hash table.
• Không có âm tính giả ở mọi cấu hình. Lab kiểm từng khóa đã thêm trên cả 39 filter đã dựng (13 cấu hình, mỗi cấu hình 3 filter).

Lab: vì sao không xóa được bằng cách xóa bit

Khảo sát nêu rõ: xóa một khóa bằng cách đặt lại các bit của nó về 0 có thể xóa luôn bit mà khóa khác dùng chung, khiến filter không còn phản ánh đúng tập khóa. Lab tìm hai khóa dùng chung bit trong filter 64 bit với k = 3, “xóa” khóa thứ nhất rồi hỏi khóa thứ hai, vẫn là thành viên:

from bloom import Bloom, positions

M, K = 64, 3


def shared_pair() -> tuple[int, int]:
    seen: dict[int, set[int]] = {}
    for key in range(1, 10_000):
        bits = set(positions(key, K, M))
        for other, other_bits in seen.items():
            if bits & other_bits:
                return other, key
        seen[key] = bits
    raise RuntimeError("không tìm thấy cặp dùng chung bit")


first, second = shared_pair()
bloom = Bloom(M, K)
bloom.add(first)
bloom.add(second)
assert first in bloom and second in bloom
shared = sorted(set(positions(first, K, M)) & set(positions(second, K, M)))
for position in positions(first, K, M):
    bloom.bits[position] = 0
print(f"hai khóa dùng chung bit {shared}")
print("sau khi xóa bit của khóa thứ nhất, khóa thứ hai (vẫn là thành viên) báo", "có" if second in bloom else "không có")
assert second not in bloom
print("xóa bit tạo ra âm tính giả")

python3 -B bloom_delete.py

hai khóa dùng chung bit [41]
sau khi xóa bit của khóa thứ nhất, khóa thứ hai (vẫn là thành viên) báo không có
xóa bit tạo ra âm tính giả

Bloom filter chuẩn vì vậy chỉ thêm, không xóa. Khảo sát mô tả biến thể counting Bloom filter: mỗi ô là một bộ đếm nhỏ (khoảng 4 bit đủ cho phần lớn ứng dụng theo phân tích mà khảo sát dẫn), thêm thì tăng, xóa thì giảm. Bài không cài và không đo biến thể này.

Skip list

Cơ chế và công thức

Skip list là danh sách liên kết có thứ tự, trong đó mỗi nút có một số con trỏ tiến (gọi là tầng) chọn ngẫu nhiên: mọi nút có tầng 1, rồi với xác suất p nút lên thêm tầng 2, và tiếp tục với xác suất p cho mỗi tầng kế (hàm random_level trong bài báo). Tìm kiếm xuất phát từ tầng cao nhất: đi tiếp trên tầng đó khi khóa của nút kế còn nhỏ hơn khóa cần tìm, nếu không thì hạ xuống tầng dưới; xuống tới tầng 1 thì nút kế là chỗ khóa cần tìm nằm, nếu nó có. Không có phép xoay hay cân bằng: chèn chỉ nối lại vài con trỏ. Bài báo ghi giả định của phân tích: người dùng không biết mức của các nút, vì nếu biết thì có thể xóa mọi nút không ở tầng 1 để ép trường hợp xấu nhất.

Bài báo khuyên dùng p = 1/4 trừ khi độ biến thiên của thời gian chạy là mối quan tâm chính, khi đó dùng p = 1/2: cùng chi phí tìm kiếm cỡ 2·log₂n, nhưng ít con trỏ hơn mỗi nút và dao động nhiều hơn. Bài báo còn tính cận xác suất cho trường hợp chậm bất thường (ví dụ với p = 1/2 và 4.096 phần tử, xác suất một lần tìm tốn hơn ba lần kỳ vọng nhỏ hơn một phần 200 triệu); lab bên dưới không đo đuôi cỡ đó.

Lab: số tầng, con trỏ và số so sánh

Lab cài đúng vòng lặp trong bài báo: NIL là nút có khóa lớn hơn mọi khóa, mỗi phép thử khóa nút kế < khóa cần tìm tính một so sánh, cộng một so sánh bằng ở cuối.

import random
from collections.abc import Iterator

MAX_LEVEL = 32


class Node:
    __slots__ = ("key", "forward")

    def __init__(self, key: float, level: int) -> None:
        self.key = key
        self.forward: list[Node | None] = [None] * level


class SkipList:
    def __init__(self, p: float, rng: random.Random) -> None:
        self.p = p
        self.rng = rng
        self.nil = Node(float("inf"), 0)
        self.header = Node(float("-inf"), MAX_LEVEL)
        self.header.forward = [self.nil] * MAX_LEVEL
        self.level = 1

    def random_level(self) -> int:
        level = 1
        while self.rng.random() < self.p and level < MAX_LEVEL:
            level += 1
        return level

    def insert(self, key: int) -> None:
        update: list[Node] = [self.header] * MAX_LEVEL
        node = self.header
        for i in range(self.level - 1, -1, -1):
            while node.forward[i].key < key:  # type: ignore[union-attr]
                node = node.forward[i]  # type: ignore[assignment]
            update[i] = node
        level = self.random_level()
        self.level = max(self.level, level)
        new = Node(key, level)
        for i in range(level):
            new.forward[i] = update[i].forward[i]
            update[i].forward[i] = new

    def search(self, key: int) -> tuple[bool, int]:
        """Trả về (có không, số lần so sánh khóa)."""
        comparisons = 0
        node = self.header
        for i in range(self.level - 1, -1, -1):
            while True:
                comparisons += 1
                if node.forward[i].key < key:  # type: ignore[union-attr]
                    node = node.forward[i]  # type: ignore[assignment]
                else:
                    break
        comparisons += 1
        return node.forward[0].key == key, comparisons  # type: ignore[union-attr]

    def levels(self) -> Iterator[int]:
        node = self.header.forward[0]
        while node is not self.nil:
            yield len(node.forward)  # type: ignore[union-attr]
            node = node.forward[0]  # type: ignore[union-attr]

Lab dựng 10 skip list cho mỗi cặp (p, n) với n = 256, 2.048 và 16.384, mỗi danh sách có khóa và mức khác nhau, rồi tìm 5.000 khóa có sẵn trên mỗi danh sách. Lab dừng nếu số so sánh trung bình nằm ngoài khoảng 80% đến 100% của cận trên của bài báo, nếu con trỏ mỗi nút lệch 1/(1−p) từ 3% trở lên, nếu tỉ lệ nút theo tầng lệch p^(i−1) từ 5% trở lên ở n lớn nhất, nếu độ tăng số so sánh mỗi lần gấp đôi n ngoài khoảng 1,5 đến 2,5, hoặc nếu p = 1/4 không ít con trỏ hơn và dao động nhiều hơn p = 1/2.

import math
import random
import statistics

from skiplist import SkipList

SIZES = (1 << 8, 1 << 11, 1 << 14)
LISTS = 10
SEARCHES = 5_000


def build(p: float, n: int, seed: int) -> tuple[SkipList, list[int], random.Random]:
    rng = random.Random(seed)
    keys = rng.sample(range(10 * n), n)
    skip = SkipList(p, rng)
    for key in keys:
        skip.insert(key)
    return skip, keys, rng


def study(p: float, n: int) -> dict[str, float]:
    counts: list[int] = []
    list_means: list[float] = []
    pointers: list[float] = []
    tops: list[int] = []
    at_least = [0, 0, 0]
    for seed in range(LISTS):
        skip, keys, rng = build(p, n, seed)
        levels = list(skip.levels())
        assert len(levels) == n
        results = [skip.search(rng.choice(keys)) for _ in range(SEARCHES)]
        assert all(found for found, _ in results)
        found_counts = [c for _, c in results]
        counts += found_counts
        list_means.append(statistics.fmean(found_counts))
        pointers.append(statistics.fmean(levels))
        tops.append(skip.level)
        for index, tier in enumerate((2, 3, 4)):
            at_least[index] += sum(1 for level in levels if level >= tier)
    return {
        "mean": statistics.fmean(counts),
        "stdev": statistics.pstdev(counts),
        "low": min(list_means),
        "high": max(list_means),
        "pointers": statistics.fmean(pointers),
        "top": statistics.fmean(tops),
        **{f"tier{t}": at_least[i] / (LISTS * n) for i, t in enumerate((2, 3, 4))},
    }


table: dict[tuple[float, int], dict[str, float]] = {}
for p in (0.5, 0.25):
    for n in SIZES:
        row = table[p, n] = study(p, n)
        depth = math.log(n, 1 / p)
        bound = depth / p + 1 / (1 - p) + 1
        print(
            f"p={p} n={n}: so sánh TB {row['mean']:.2f} (cận trên {bound:.2f},"
            f" mỗi danh sách {row['low']:.2f}-{row['high']:.2f}), độ lệch chuẩn {row['stdev']:.2f}"
            f" | con trỏ/nút {row['pointers']:.3f} ({1 / (1 - p):.3f})"
            f" | tầng cao nhất TB {row['top']:.1f} (L(n)+1/(1-p) = {depth + 1 / (1 - p):.1f})"
        )
        assert 0.8 * bound <= row["mean"] <= bound
        assert abs(row["pointers"] * (1 - p) - 1) < 0.03
        assert row["top"] <= depth + 1 / (1 - p) + 1
for p in (0.5, 0.25):
    row = table[p, SIZES[-1]]
    expected = [p ** (tier - 1) for tier in (2, 3, 4)]
    measured = [row[f"tier{tier}"] for tier in (2, 3, 4)]
    print(f"p={p} n={SIZES[-1]}: tỉ lệ nút từ tầng 2/3/4 trở lên " + " ".join(f"{a:.4f}/{b:.4f}" for a, b in zip(measured, expected)))
    assert all(abs(a - b) / b < 0.05 for a, b in zip(measured, expected))
    slope = (row["mean"] - table[p, SIZES[0]]["mean"]) / 6
    print(f"p={p}: thêm {slope:.2f} so sánh mỗi lần gấp đôi n")
    assert 1.5 <= slope <= 2.5
half, quarter = table[0.5, SIZES[-1]], table[0.25, SIZES[-1]]
print(
    f"n={SIZES[-1]}: p=1/2 {half['mean']:.2f} so sánh, lệch chuẩn {half['stdev']:.2f}, {half['pointers']:.2f} con trỏ/nút;"
    f" p=1/4 {quarter['mean']:.2f} so sánh, lệch chuẩn {quarter['stdev']:.2f}, {quarter['pointers']:.2f} con trỏ/nút"
)
assert abs(half["mean"] - quarter["mean"]) / half["mean"] < 0.15
assert quarter["stdev"] > half["stdev"] and quarter["pointers"] < 0.7 * half["pointers"]
print("số tầng, con trỏ và số so sánh khớp bài báo")

python3 -B skiplist_stats.py

p=0.5 n=256: so sánh TB 17.04 (cận trên 19.00, mỗi danh sách 15.00-22.50), độ lệch chuẩn 3.78 | con trỏ/nút 1.997 (2.000) | tầng cao nhất TB 9.3 (L(n)+1/(1-p) = 10.0)
p=0.5 n=2048: so sánh TB 23.34 (cận trên 25.00, mỗi danh sách 20.90-26.70), độ lệch chuẩn 4.48 | con trỏ/nút 2.007 (2.000) | tầng cao nhất TB 12.3 (L(n)+1/(1-p) = 13.0)
p=0.5 n=16384: so sánh TB 28.59 (cận trên 31.00, mỗi danh sách 26.70-31.03), độ lệch chuẩn 4.85 | con trỏ/nút 1.999 (2.000) | tầng cao nhất TB 14.4 (L(n)+1/(1-p) = 16.0)
p=0.25 n=256: so sánh TB 15.59 (cận trên 18.33, mỗi danh sách 13.75-18.43), độ lệch chuẩn 5.25 | con trỏ/nút 1.319 (1.333) | tầng cao nhất TB 5.1 (L(n)+1/(1-p) = 5.3)
p=0.25 n=2048: so sánh TB 21.45 (cận trên 24.33, mỗi danh sách 19.35-23.40), độ lệch chuẩn 6.41 | con trỏ/nút 1.330 (1.333) | tầng cao nhất TB 6.8 (L(n)+1/(1-p) = 6.8)
p=0.25 n=16384: so sánh TB 26.78 (cận trên 30.33, mỗi danh sách 25.46-28.42), độ lệch chuẩn 7.67 | con trỏ/nút 1.331 (1.333) | tầng cao nhất TB 8.0 (L(n)+1/(1-p) = 8.3)
p=0.5 n=16384: tỉ lệ nút từ tầng 2/3/4 trở lên 0.5002/0.5000 0.2480/0.2500 0.1248/0.1250
p=0.5: thêm 1.92 so sánh mỗi lần gấp đôi n
p=0.25 n=16384: tỉ lệ nút từ tầng 2/3/4 trở lên 0.2486/0.2500 0.0614/0.0625 0.0156/0.0156
p=0.25: thêm 1.87 so sánh mỗi lần gấp đôi n
n=16384: p=1/2 28.59 so sánh, lệch chuẩn 4.85, 2.00 con trỏ/nút; p=1/4 26.78 so sánh, lệch chuẩn 7.67, 1.33 con trỏ/nút
số tầng, con trỏ và số so sánh khớp bài báo

Đọc kết quả:

• Tầng và con trỏ khớp công thức. Ở n = 16.384, tỉ lệ nút theo tầng bám p^(i−1) trong 1% (ví dụ 0,2480 so với 0,2500 ở p = 1/2, tầng 3), và số con trỏ mỗi nút là 1,999 và 1,331 so với 2 và 1,33.
• Số so sánh dưới cận và tăng đều theo log n. Trung bình 28,6 (p = 1/2) và 26,8 (p = 1/4) ở n = 16.384, dưới cận trên 31,0 và 30,3 của bài báo; mỗi lần gấp đôi n thêm khoảng 1,9 so sánh, đúng hệ số 2 của L(n)/p. Với log₂ 16.384 = 14, tìm kiếm nhị phân trên mảng đã sắp cần cỡ 14 so sánh, nên skip list tốn cỡ gấp đôi số so sánh, đổi lại chèn không phải dời phần tử; bài báo cũng ghi skip list so sánh nhiều hơn các cấu trúc khác.
• Kỳ vọng không phải bảo đảm. Mỗi danh sách có hình dạng riêng: trung bình từng danh sách ở n = 16.384 và p = 1/2 dao động từ 26,7 đến 31,0 so sánh. Một danh sách cụ thể có thể chậm hơn kỳ vọng, và độ lệch chuẩn (gộp 10 danh sách) cho thấy từng lần tìm còn dao động hơn nữa.
• Chọn p là chọn giữa bộ nhớ và độ ổn định. p = 1/4 cho cùng cỡ chi phí (26,8 so với 28,6 so sánh) với 1,33 con trỏ mỗi nút thay vì 2, nhưng độ lệch chuẩn của số so sánh lớn hơn (7,7 so với 4,9). Điều này khớp lời khuyên của bài báo: dùng p = 1/4 trừ khi độ biến thiên của thời gian là mối quan tâm chính.

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. Đơn vị đo là số so sánh, số bit và dương tính giả, không phải thời gian; bài không đo tốc độ thật, cache hay bộ nhớ của cài đặt nào, và không nói gì về Redis, RocksDB hay thư viện khác.
• Bloom filter trong lab dùng k lần băm BLAKE2b độc lập, sát giả định của công thức. Bộ băm nhanh hơn dùng trong thực tế (ví dụ tổ hợp từ hai giá trị băm) có thể lệch công thức; bài không đo.
• Công thức dương tính giả là xấp xỉ; khảo sát nêu cả dạng chính xác hơn (1 − (1 − 1/m)^(kn))^k. Với m cỡ chục nghìn bit trở lên hai dạng khác nhau không đáng kể, và bài đo bằng filter thật nên không dựa vào việc chọn dạng nào.
• Skip list trong lab chỉ có chèn và tìm; xóa, truy vấn khoảng và cập nhật đồng thời (bài báo có công trình riêng về cập nhật đồng thời) không được cài và không được đo. Bộ sinh số ngẫu nhiên của Python không dành cho dùng trong tình huống có kẻ tấn công.
• Cận trên của bài báo là cận của kỳ vọng. Số so sánh đo thấp hơn cận từ khoảng 1,7 đến 3,6 so sánh; bài không đối chiếu với phân tích chính xác. Mỗi danh sách có hình dạng riêng nên trung bình từng danh sách dao động quanh kỳ vọng (cột “mỗi danh sách”); kỳ vọng không phải bảo đảm cho một danh sách cụ thể.
• Không đo đuôi xác suất cỡ một phần triệu; bài chỉ trích điều bài báo tính.
• 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

• Hash table: va chạm, load factor và vì sao O(1) chỉ là kỳ vọng: hàm băm, va chạm và khi nào giả định “băm đều” sụp đổ.
• Đọc benchmark: số đo và ngoại suy: cách đọc số đo mà không suy quá phép đo.
• William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Communications of the ACM 33(6), 1990 (bản công khai trên trang một môn học): random_level, L(n), cận chi phí, bảng chọn p.
• Andrei Broder và Michael Mitzenmacher, Network Applications of Bloom Filters: A Survey, Internet Mathematics 1(4), 2004: công thức dương tính giả, k tối ưu, cận dưới kích thước, counting Bloom filter.
• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13(7), 1970 (bài báo gốc, liên kết DOI là con trỏ tới bản của nhà xuất bản; bài này chưa đọc được bản công khai): nguồn gốc của Bloom filter.

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.