岳氏礦泉水

泉源思緒，細品人生

0%

資料結構與演算法筆記 | 哈希表 (Hash Table)

發表於 分類於 ， Disqus：
文章字數： 9k 所需閱讀時間 ≈ 45 分鐘

當我們在做資料處理時，除了新增與刪除資料外，另一項最常見的用途就是查詢資料。假設有一堆學生的資料，簡化假設，每個學生都有有學號與姓名。現在需要快速查出某個學號對應的學生姓名。做法有以下幾種：

  • 陣列：可以用索引快速查找（但索引是整數，學號可能不是），但若用學號當所有會浪費空間，例如學號是 1023001
  • 迴圈：假設資料存在陣列或其他資料結當中，用迴圈逐一匹配是否有對應的學號，但時間複雜度會是 $\mathcal{O}(n)$，假設今天有數千名甚至數萬名筆資料，恐怕要查到天荒地老

哈希表的數學觀點

為了解決這個問題，我們可以使用哈希表，其定義是根據鍵直接查詢在記憶體中儲存位置之值的資料結構。簡單來說，哈希表是一種使用鍵 (key) 查找值 (value) 的資料結構，底層通常是用陣列儲存資料，但用一種特殊的方式：哈希函數 (Hash function) 將鍵映射到陣列的索引。

哈希表

在數學上，哈希表可以理解為一種從集合 $A$ 映射 (maps) 到集合 $B$ 的函數結構。

  • $K$：鍵集合 (key set)，例如學號、身分證號等
  • $V$：值集合 (value set)，例如姓名、居住地等
  • $T$：儲存資料的陣列，大小為 $m$，稱為哈希表的容量 (capacity)

因此哈希表 ($H$) 的結構可以表示為：

$$
H:K \to V
$$

哈希函數

誠如上述所言，哈希表是一個實踐映射的資料結構，而這種映射就是哈希函數：

$$
h: K \to {0, 1, 2, \cdots, m - 1}
$$

也就是說，把任意的 key（可能是字串、元組、物件等）轉換成一個固定範圍的整數，這個整數就是哈希表中的索引值。假設我們有一個鍵是 k="A123456789"，然後我們定義一個簡單的哈希函數：

$$
h(k) = \left(\sum_{i = 1}^{n} \operatorname{ASCII}(k_{i})\right) \bmod m
$$

這個意思是：

  • 把字串每個字元轉成 ASCII 值
  • 加總起來
  • 對表長 $m$ 取餘數

這樣就保證會落在 $0$ 到 $m - 1$ 的範圍內。而一個好的哈希算法必須同時滿足以下數學與特性：

  1. 確定性 (determinism)：相同輸入鍵一定輸出相同哈希值，高度可重現
  2. 高效能 (computational efficiency)：算哈希成本要低，如 $\mathcal{O}(1)$ 操作級別，不能太慢
  3. 均勻分布 (uniform distribution)：哈希值的分布要平均，才能讓鍵均分配到各桶中，降低碰撞機率。

這三者缺一不可，尤其關於哈希表性能，均勻分布至關重要。

哈希表資料存取行為

插入操作，即是給定一對鍵值對 $(k, v)$，先計算索引 $i = h(k)$，並在表格的第 $i$ 格儲存該資料 $v$：

$$
T[h(k)] = v
$$

要查詢鍵值為 $k$ 的資料時，即是回傳 $T[h(k)]$。

哈希表範例

例如下面我們初始化一個名為 hmap的字典，以數字作為鍵，對應到不同人物名稱，展現哈希表的基本操作：新增、查詢與刪除：

1
2
3
4
5
6
7
8
9
# 初始化哈希表
hmap: dict = {}

# 新增元素
hmap[12836] = "喪彪"
hmap[15937] = "金髮"
hmap[16750] = "小美"
hmap[13276] = "小帥"
hmap[10583] = "大壯"

查詢元素的語法為 dict[key]：

1
2
3
# 查詢元素
name: str = hmap[12836]
print(name)

刪除元素則是 dict.pop(key) ：

1
2
3

# 刪除元素
hmap.pop(15937)

我們也可以使用迴圈來實作走訪：

1
2
3
4
5
6
7
8
9
10
11
# 走訪鍵值對
for key, val in hmap.items():
    print(key, "->", val)

# 單獨走訪鍵
for key in hmap.keys():
    print(f"key: {key}")

# 單獨走訪值
for val in hmap.values():
    print(f"val: {val}")

哈希表實作

Python 中的 dict 就是內建的哈希表實作，允許使用任意的可哈希 (hashable) 鍵來快速對應到一個值。因此我們需要先建立鍵值對的類，方便之後操作：

1
2
3
4
class Pair:
    def __init__(self, key: int, val: str):
        self.key = key
        self.val = val

為簡化設計，此處將哈希函數設定為鍵值對容量取餘，哈希函數透過 key % 100 將鍵映射到 100 個桶之一，並將鍵值對儲存在對應位置。查詢與刪除也透過相同哈希函數找對應索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class ArrayHashMap:
    def __init__(self):
        self.buckets: list[Pair | None] = [None] * 100

    def hash_func(self, key: int) -> int:
        index = key % 100
        return index

    def put(self, key: int, val: str) -> None:
        pair = Pair(key, val)
        index: int = self.hash_func(key)
        self.buckets[index] = pair

    def remove(self, key: int) -> None:
        index: int = self.hash_func(key)
        self.buckets[index] = None
    
    def get(self, key: int) -> str:
        index: int = self.hash_func(key)
        pair: Pair = self.buckets[index]
        
        if pair is None:
            return None
        return pair.val
    
    def entry_set(self) -> list[Pair]:
        result: list[Pair] = []
        for pair in self.buckets:
            if pair is not None:
                result.append(pair)
        return result
    
    def key_set(self) -> list[int]:
        keys: list[int] = []
        for pair in self.buckets:
            if pair is not None:
                keys.append(pair.key)
        return keys
    
    def val_set(self) -> list[int]:
        vals: list[int] = []
        for pair in self.buckets:
            if pair is not None:
                vals.append(pair.val)
        return vals
    
    def __str__(self) -> str:
        entries = []
        for pair in self.buckets:
            if pair is not None:
                entries.append(f"{pair.key} -> {pair.val}")
        return "\n".join(entries)

練習題

給一個整數陣列 nums 和一個目標數 target，請你返回陣列中兩個數字的索引，使得它們的總和為 target。

1
2
3
輸入: nums = [2, 7, 11, 15], target = 9
輸出: [0, 1]
原因: nums[0] + nums[1] = 2 + 7 = 9
解答 
1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen_idx = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen_idx:
                return [seen_idx[complement], i]
            seen_idx[num] = i

給一個字串 s，找出第一個只出現一次的字元，並回傳它的索引。如果不存在，就回傳 -1。

1
2
3
4
5
6
7
8
輸入: s = "leetcode"
輸出: 0

輸入: s = "loveleetcode"
輸出: 2

輸入: s = "aabb"
輸出: -1
解答 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def firstUniqChar(self, s: str) -> int:
        ch_freq = {}
        
        for ch in s:
            if ch in ch_freq:
                ch_freq[ch] += 1
            else:
                ch_freq[ch] = 1

        for i in range(len(s)):
            if ch_freq[s[i]] == 1:
                return i
        
        return -1

哈希衝突 (Hash Collision)

雖然：

$$
h: K \to {0, 1, …, m-1}
$$

但通常 $|K| \gg m$，即鍵的種類遠多於表格容量，按照鴿籠原理 (Pigeonhole Principle)，必定會有兩個不同的 key 被映射到同一個位置：

$$
\exists \ k_1 \ne k_2 \ni h(k_1) = h(k_2)
$$

這就稱為哈希衝突。因此，設計哈希表時，除了設計好的 $h(k)$，還要選好解衝突的方法。舉例來說，上面的例子限制表容量為 100 個，但如果查詢 12836 與 21636 時，經過哈希函數後（對 100 取餘），均會得到 36，此時會指向同一個輸出。為了解決此問題，我們可以會依照狀況採取策略：

  • 改良哈希表的資料結構
  • 若衝突不斷發生，才會採用擴容

鏈式地址 (Separate Chaining)

每個桶位不是放單一資料，而是放一個鏈結串列或陣列來儲存多個 Pair(key, val)。當多個鍵對應到同一個索引時，它們會被加入這條鏈中，避免覆蓋掉原資料。

1
2
3
4
5
6
buckets = [
    [(1, "A"), (5, "B")],   # 1 % 4 = 1, 5 % 4 = 1
    [],                     # index 1
    [],                     # index 2
    []                      # index 3
]

操作流程為：

  • 插入時：把新資料加到對應桶位的串列裡（尾端或頭端）
  • 查找時：先找到桶，再逐一掃描串列

負載因子 (Load Factor)

我們會使用負載因子 (load factor) 來衡量哈希表的擁擠程度，因此：

  • 若太大，代表許多 bucket 裡面堆太多資料，平均查找時間會退化
  • 若太小，空間浪費

在鏈式哈希表中，平均每個 bucket 長度為負載因子的大小，所以查找平均複雜度為 $\mathcal{O}(1 + \alpha)$，其中 $\alpha$ 為負載因子。

為了方便理解，設：

  • $n$：當前資料筆數

  • $M$：桶數量

  • $r$：擴容倍率

  • $\alpha$：負載因子，計算方式為：

    $$
    \alpha = \dfrac{n}{M}
    $$

因此我們可以設計為：當負載因子超過 $2/3$ 時，就將原哈希表擴容為兩倍。當擴容後，負載因子會降低：

$$
\alpha^{\prime} = \dfrac{n}{2 M} = \dfrac{1}{2} \times \dfrac{n}{M} = \dfrac{\alpha}{2}
$$

且注意到，擴容後必須重新哈希，因爲一旦哈希表容量變了，索引的分布也會跟著改變。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class HashMapChaining:
    def __init__(self):
        self.size = 0                   # 鍵值對數量
        self.capacity = 4               # 哈希表容量
        self.load_thres = 2.0 / 3.0     # 負載因子閾值
        self.extend_ratio = 2           # 擴容倍數
        self.buckets: list[list[Pair]] = [[] for _ in range(self.capacity)]

    def hash_func(self, key: int) -> int:
        return key % self.capacity
    
    def load_factor(self) -> float:
        return self.size / self.capacity
    
    def put(self, key: int, val: str) -> None:
        if self.load_factor() > self.load_thres:
            self.extend()
        
        index: int = self.hash_func(key)
        bucket = self.buckets[index]

        for pair in bucket:
            if pair.key == key:
                pair.val = val
                return
        pair = Pair(key, val)
        bucket.append(pair)
        self.size += 1

    def remove(self, key: int) -> None:
        index: int = self.hash_func(key)
        bucket = self.buckets[index]
        
        for pair in bucket:
            if pair.key == key:
                bucket.remove(pair)
                self.size -= 1
                break
    
    def get(self, key: int) -> str | None:
        index: int = self.hash_func(key)
        bucket = self.buckets[index]

        for pair in bucket:
            if pair.key == key:
                return pair.val
        return None
    
    def extend(self) -> None:
        # 暫存既有桶
        buckets = self.buckets
        # 擴容
        self.capacity *= self.extend_ratio
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        # 將既有桶放入新桶中
        for bucket in buckets:
            for pair in bucket:
                self.put(pair.key, pair.val)

    def __str__(self) -> str:
        entries = []
        for pair in self.buckets:
            if pair is not None:
                entries.append(f"{pair.key} -> {pair.val}")
        return "\n".join(entries)

開放定址 (Open Addressing)

開放定址的核心想法是：如果哈希衝突了，就去找下一個「空位」來放，整張表就像是停車場，車位排滿就往後找空位停。假設去全聯買完東西要停車，但原本想停的位置已經有人停了，那麼就往後找。對於每個鍵，計算方式如下：

$$
h(k, i) = g\left(h^{\prime}(k) + f(i)\right)
$$

  • $h(k, i)$：第 $i$ 次嘗試的位置（實際使用的位置）
  • $g$：哈希函數
  • $h^{\prime}$：原始哈希值（例如 key % m）
  • $f(i)$：探查函數（決定下一次探查往哪裡移動）
  • $m$：表格容量

常見的探查策略有三種：

探查策略 探查公式 說明
線性探查 (linear probing) $f(i)=i$ 每次往後一格找
二次探查 (quadratic probing) $f(i) = i^2$ 跳著找、減少群聚
雙重雜湊 (double hashing) $f(i) = i \cdot h_2(k)$ 使用第二個 hash function

以線性探查為例，所有資料直接儲存在一維陣列中，插入時，如果計算出來的位置被佔用了（發生衝突），就用線性探查繼續往後找空位，查找與刪除時，也用同樣的探查方式來找到正確的位置。但如果今天直接把刪除的格子設為 None，會發生以下問題：

  • 查找時：如果你遇到 None 就會以為 key 不存在，提早終止線性探查
  • 但實際上 key 可能被插在後面的桶

假設 capacity 為 4，插入的鍵為：

  • key=1 → 1 % 4 = 1 → 存在索引 1
  • key=5 → 5 % 4 = 1（衝突）→ 線性探查到索引 2，插在該處

如果你刪除了 key=1，然後查找 key=5，則會：

  • 索引 1 是 None
  • 程式看到 None 就結束了 → 找不到 key=5

這就導致了錯誤的查找結果。為此，我們引入了墓碑標記 (tombstome)，用以表示「這裡曾經有資料，但現在刪除了，請繼續探查後面的格子」，它是為了保證查找與插入的正確性而設計的一種「中介狀態」，並且讓刪除後空出來的位置可以被再利用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class HashMapOpenAddrssing:
    def __init__(self):
        self.size = 0
        self.capacity = 4
        self.load_thres = 2.0 / 3.0
        self.extend_ratio = 2
        self.buckets: list[Pair | None] = [None] * self.capacity
        self.TOMBSTONE = Pair(-1, "-1")         # 墓碑標記

    def hash_func(self, key: int) -> int:
        return key % self.capacity
    
    def load_factor(self) -> float:
        return self.size / self.capacity
    
    def find_bucket(self, key: int) -> int:
        index = self.hash_func(key)
        first_tombstone = -1

        while self.buckets[index] is not None:
            if self.buckets[index].key == key:
                if first_tombstone != -1:
                    self.buckets[first_tombstone] = self.buckets[index]
                    self.buckets[index] = self.TOMBSTONE
                    return first_tombstone
                return index
            if first_tombstone == -1 and self.buckets[index] is self.TOMBSTONE:
                first_tombstone = index
            
            index = (index + 1) % self.capacity
        return index if first_tombstone == -1 else first_tombstone
    
    def put(self, key: int, val: str) -> None:
        if self.load_factor() > self.load_thres:
            self.extend()
        
        index: int = self.find_bucket(key)
        if self.buckets[index] not in [None, self.TOMBSTONE]:
            self.buckets[index].val = val
            return
        self.buckets[index] = Pair(key, val)
        self.size += 1

    def remove(self, key: int) -> None:
        index: int = self.find_bucket(key)
        
        if self.buckets[index] not in [None, self.TOMBSTONE]:
            self.buckets[index] = self.TOMBSTONE
            self.size -= 1
    
    def get(self, key: int) -> str:
        index = self.find_bucket(key)
        if self.buckets[index] not in [None, self.TOMBSTONE]:
            return self.buckets[index].val
        return None
    
    def extend(self) -> None:
        buckets = self.buckets
        self.capacity *= self.extend_ratio
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for pair in buckets:
            if pair not in [None, self.TOMBSTONE]:
                self.put(pair.key, pair.val)

    def __str__(self) -> str:
        entries = []
        for pair in self.buckets:
            if pair is not None:
                entries.append(f"{pair.key} -> {pair.val}")
        return "\n".join(entries)

鏈式地址與開放定址比較

操作 鏈式法 開放定址法（線性探查）
插入 平均 $\mathcal{O}(1)$，最差 $\mathcal{O}(n)$ 平均 $\mathcal{O}(1)$，最差 $\mathcal{O}(n)$
查找 平均 $\mathcal{O}(1 + \alpha)$ 平均 $\mathcal{O}(1 + \alpha)$
刪除 較簡單（直接刪） 較麻煩（需重排）
擴容後重排 每個鍵重哈希 每個鍵重哈希