跳轉到

4.1 靜態雜湊與可擴展雜湊#

概念說明#

靜態雜湊把檔案預先切成 M 個桶，每桶占一個（或少數幾個）分頁，插入記錄時計算 h(key) mod M 落桶。優點是查詢剛好 1 次 I/O；缺點是 M 固定——資料成長後桶內溢位，必須依賴溢位頁鏈，查詢退化成多次 I/O；而資料減少時又浪費空間。傳統做法只能預估資料量建表，或定期重組（reorganize），都很僵硬。

可擴展雜湊（extendible hashing）解決成長問題。它使用兩層結構：

  • 一個目錄（directory），含 2^d 個項目（d 稱為全域深度 global depth），每個項目指向一個桶。
  • 每個桶有局部深度（local depth） l ≤ d，桶只依鍵值的後（低）l 個位元分類。

插入時若桶未滿直接放；若滿了就分裂：桶的局部深度 l 加 1，原桶內容依新增的那個位元重新分配成兩個桶。若分裂後 l > d，則先將目錄加倍（d 加 1，項目數翻倍，所有指標複製一份），再分裂。因為只分裂一個桶，其他桶的指標在目錄加倍後只是「多個項目指向同一桶」，不需移動資料。

查詢成本：1 次目錄讀取 + 1 次桶讀取 = 2 次 I/O（目錄通常小到可常駐記憶體，實際上常視為 1 次 I/O）。

演算法步驟#

插入（鍵 k）： 1. 計算 h(k)，取低 d 位元定位目錄項目 → 得到桶頁。 2. 讀取桶頁；若有空位，寫入，結束（2 次 I/O）。 3. 桶滿：令該桶局部深度 l。 - 若 l == d：目錄加倍，d += 1。 - 分裂桶：新舊兩桶局部深度 l+1，依第 l+1 位元重新分配記錄。 - 更新目錄中相關項目的指標。 - 若某一桶仍滿（所有記錄同位元），繼續分裂。 4. 寫回桶頁與目錄。

Python 範例#

class ExtendibleHash:
    def __init__(self, bucket_size=3):
        self.d = 1                       # 全域深度
        self.dir = [0, 1]                # 目錄項目 → 桶編號
        self.buckets = {0: [], 1: []}    # 桶編號 → (記錄, 局部深度)
        self.depth = {0: 1, 1: 1}
        self.bs = bucket_size
        self.io = 0
        self._next_id = 2

    def _bucket_of(self, key):
        self.io += 1                     # 讀目錄
        idx = key & ((1 << self.d) - 1)
        return self.dir[idx]

    def insert(self, key, val=None):
        b = self._bucket_of(key)
        while len(self.buckets[b]) >= self.bs:   # 桶滿 → 分裂
            l = self.depth[b]
            if l == self.d:                       # 目錄加倍
                self.dir = self.dir * 2
                self.d += 1
            self.io += 1                          # 讀滿桶
            old = self.buckets.pop(b); self.depth.pop(b)
            b0, b1 = self._next_id, self._next_id + 1
            self._next_id += 2
            self.buckets[b0], self.buckets[b1] = [], []
            self.depth[b0] = self.depth[b1] = l + 1
            for r in old:
                nb = b0 if (r & (1 << l)) == 0 else b1
                self.buckets[nb].append(r)
            for i, p in enumerate(self.dir):      # 更新指標
                if p == b: self.dir[i] = b0 if (i & (1 << l)) == 0 else b1
            b = self._bucket_of(key)
        self.io += 1                              # 寫桶
        self.buckets[b].append(key)

    def search(self, key):
        b = self._bucket_of(key)
        self.io += 1
        return key in self.buckets[b]

h = ExtendibleHash(bucket_size=2)
for k in [4, 12, 16, 8, 20, 3, 7, 11]:
    h.insert(k)
print("全域深度:", h.d, "目錄:", h.dir)
for q in [4, 7, 20, 99]:
    print(q, "存在?" , h.search(q))
print("總 I/O:", h.io)

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

  • 查詢：2 次 I/O（目錄 + 桶）；目錄常駐記憶體時 1 次。
  • 插入無分裂：2 次 I/O；有分裂：約 4~6 次；目錄加倍：再 + 1 次寫目錄，且最壞情況（所有記錄同位元）會連續分裂。
  • 目錄大小最壞 O(2^d)，鍵偏斜時目錄可能遠大於桶數——這是可擴展雜湊的主要弱點，也是線性雜湊存在的理由。

練習#

  1. 依序插入 1, 5, 9, 13, 17（bucket_size=1），畫出每次插入後的目錄與桶。
  2. 說明「目錄加倍」時為何不必移動任何桶內資料。
  3. 若雜湊函數使 80% 的鍵落在同一個位元模式，可擴展雜湊會發生什麼？如何緩解？