跳轉到

4.2 線性雜湊#

概念說明#

線性雜湊（linear hashing）由 Witold Litwin 於 1980 年提出，它捨棄了可擴展雜湊的目錄，用「漸進分裂」達成擴張：表格不一次加倍，而是每次溢位時只分裂一個桶——而且分裂的對象不是溢位的桶，而是按固定順序輪到的桶（由指標 split 指定）。這樣分裂是可預測、增量的，不需要目錄，任何時刻磁碟上就是一個簡單的桶陣列。

核心機制：設目前桶數為 N'（介於 N 與 2N 之間，N 為上一次 2 的冪）。查詢鍵 k 時：

  1. 若 h(k) mod N' ≥ split（該桶尚未輪到分裂），用 h(k) mod N' 定位。
  2. 否則（該範圍已分裂過），用 h(k) mod 2N 定位。

插入導致溢位時，把 split 指到的桶分裂成兩個（依 h(k) mod 2N 分配記錄），split 前進一格；split 走到 N 時，一輪完成，N ← 2N，split 歸零。也可以用「負載因子超過門檻」而非溢位來觸發分裂，讓桶不必真的溢位。

演算法步驟#

插入（鍵 k）： 1. 以上述規則定位桶，插入記錄（必要時掛溢位頁）。 2. 若負載因子 > 門檻（例如 0.8）：分裂 split 桶，split += 1；若 split == N，N *= 2, split = 0。 3. 分裂時把溢位頁中的記錄一併重新分配，常常順便消解其他桶的溢位。

查詢（鍵 k）： 1. p = h(k) mod N'；若 p < split 則 p = h(k) mod (2N)。 2. 讀取桶 p 與其溢位鏈。

Python 範例#

class LinearHash:
    def __init__(self, bucket_size=3, load=0.8):
        self.N = 4                    # 目前桶陣列大小（2 的冪）
        self.split = 0                # 下一個要分裂的桶
        self.count = 0
        self.buckets = {i: [] for i in range(self.N)}
        self.bs = bucket_size
        self.load = load
        self.io = 0

    def _addr(self, key):
        self.io += 1
        p = key % self.N
        if p < self.split:
            p = key % (2 * self.N)
        return p

    def insert(self, key):
        p = self._addr(key)
        self.io += 1
        self.buckets.setdefault(p, []).append(key)
        self.count += 1
        if self.count / self.N > self.load:      # 觸發分裂
            old = self.buckets.pop(self.split, [])
            self.io += 1
            b0, b1 = self.split, self.split + self.N
            self.buckets[b0] = [k for k in old if k % (2*self.N) == b0 % (2*self.N)]
            self.buckets[b1] = [k for k in old if k % (2*self.N) == b1 % (2*self.N)]
            self.split += 1
            if self.split == self.N:
                self.N *= 2
                self.split = 0

    def search(self, key):
        p = self._addr(key)
        self.io += 1
        return key in self.buckets.get(p, [])

h = LinearHash(bucket_size=3)
for k in range(1, 31):
    h.insert(k)
print("桶數:", h.N, "split:", h.split, "最大桶長:",
      max(len(v) for v in h.buckets.values()))
print("查詢 17:", h.search(17), "查詢 99:", h.search(99))
print("總 I/O:", h.io)

複雜度與 I/O 成本分析#

  • 查詢：平均 1~2 次 I/O；桶有溢位鏈時加上鏈長。
  • 插入：1 次寫 + 分裂時約 3 次 I/O（讀舊桶、寫兩新桶），且分裂成本被「攤提」到多次插入上——任意時刻最多只有一個桶在分裂中。
  • 空間利用率可控（由負載因子門檻決定），無目錄開銷，這正是許多儲存引擎偏好它的原因。
  • 缺點：分裂的是「輪到的桶」而非「溢位的桶」，短期內溢位鏈可能存在；需要溢位頁處理。

練習#

  1. 以 N=4、load=0.8 依序插入 1..12，列出每次分裂發生的時機與 split 的變化。
  2. 比較線性雜湊與可擴展雜湊在「查詢 I/O 次數」與「插入尖峰延遲」上的差異。
  3. 修改程式改用「溢位即分裂」的觸發策略（分裂仍按 split 順序），觀察桶長分布變化。