4.2 鏈接法與開放定址法#

概念說明#

碰撞無法避免，只能妥善處理。兩大主流：

鏈接法（chaining）：每個格子放一個小串列，撞在一起的鍵都掛上去。實作簡單、刪除容易、允許負載因子 α > 1。
開放定址法（open addressing）：所有資料都放在陣列本體。碰撞時依「探測序列」找下一個空格：線性探測（+1、+2、+3…）、平方探測（+1²、+2²…）、雙重雜湊。刪除需要特殊標記（墓碑 tombstone），否則會截斷探測鏈。

Python 的 dict 採用開放定址法（類似線性探測的變形），Java 的 HashMap 採用鏈接法（串列過長時轉紅黑樹）。

操作步驟#

鏈接法：put(k, v) → 算 i = h(k) % m → 在格子 i 的串列中找 k，找到就更新，找不到就插入頭部。get(k) → 同樣定位後線性搜尋。

開放定址（線性探測）：put → 從 i = h(k) % m 開始，該格為空則放入；已被佔用則試 (i+1) % m、(i+2) % m……直到找到空格或更新既有鍵。get → 沿同一序列走，遇到空格即確定不存在。

Python 實作#

class ChainingHashMap:
    def __init__(self, capacity=8):
        self._m = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._n = 0

    def _index(self, key):
        return hash(key) % self._m

    def put(self, key, value):
        b = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, value)
                return
        b.append((key, value))
        self._n += 1
        if self._n / self._m > 0.75:       # 負載因子超過 0.75 → 擴容
            self._resize(2 * self._m)

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

    def remove(self, key):
        b = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(b):
            if k == key:
                del b[i]
                self._n -= 1
                return True
        return False

    def _resize(self, new_m):
        old = [kv for b in self._buckets for kv in b]
        self._m = new_m
        self._buckets = [[] for _ in range(new_m)]
        self._n = 0
        for k, v in old:
            self.put(k, v)

    def __len__(self):
        return self._n

h = ChainingHashMap()
h.put("蘋果", 30)
h.put("香蕉", 15)
h.put("蘋果", 35)              # 覆蓋
print(h.get("蘋果"), h.get("芭樂", 0))   # 35 0
print(h.remove("香蕉"), len(h))          # True 2

class OpenAddressingMap:
    EMPTY = object()       # 從未使用
    DELETED = object()     # 墓碑：曾用過、已刪除

    def __init__(self, capacity=8):
        self._keys = [self.EMPTY] * capacity
        self._vals = [None] * capacity
        self._n = 0

    def _probe(self, key):
        m = len(self._keys)
        i = hash(key) % m
        first_tomb = -1
        for step in range(m):
            slot = (i + step) % m
            k = self._keys[slot]
            if k is self.EMPTY:
                return (first_tomb if first_tomb != -1 else slot, False)
            if k == key:
                return (slot, True)
            if k is self.DELETED and first_tomb == -1:
                first_tomb = slot       # 記住第一個墓碑可重用
        raise RuntimeError("雜湊表已滿")

    def put(self, key, value):
        slot, exists = self._probe(key)
        if not exists:
            self._n += 1
        self._keys[slot], self._vals[slot] = key, value

    def get(self, key, default=None):
        try:
            slot, exists = self._probe(key)
        except RuntimeError:
            return default
        return self._vals[slot] if exists else default

    def remove(self, key):
        slot, exists = self._probe(key)
        if exists:
            self._keys[slot] = self.DELETED     # 留墓碑，不能清成 EMPTY
            self._vals[slot] = None
            self._n -= 1
            return True
        return False

m = OpenAddressingMap()
m.put(1, "a"); m.put(9, "b")      # 假設兩者碰撞，9 會探測到下一格
m.put(1, "A")
print(m.get(9), m.get(1))         # b A
m.remove(1)
print(m.get(1), m.get(9))         # None b（墓碑沒有截斷探測）

複雜度分析#

平均情況下查詢成本與負載因子 α 直接相關：鏈接法約 O(1 + α)；線性探測約 O(1 / (1 − α))，α 越接近 1 越糟（叢集現象）。擴容是 O(n) 但攤攤 O(1)。最壞情況（全部撞同一格）鏈接法退化为 O(n)，開放定址表滿時找不到位置。

練習#

在 ChainingHashMap 加上 keys() 與 items()，並思考擴容時為什麼必須「全部重新雜湊」而不是直接複製桶。
把線性探測改成平方探測 slot = (i + step*step) % m，用 1 萬筆隨機鍵統計兩者「每次查詢的平均探測步數」，比較叢集程度。
刪除時若把墓碑格直接清回 EMPTY，會出什麼問題？請構造一組「插入、刪除、再查詢」的具體操作順序重現錯誤。