碰撞問題及其解決方法

7.1 定義哈希表中的碰撞

哈希表中的碰撞 發生在當兩個不同的鍵映射到數組中的同一個索引時。這會導致多個元素試圖佔據哈希表中的同一個槽位。

碰撞範例：

假設我們有一個簡單的哈希函數，它返回鍵除以表大小的餘數。對於鍵 5 和 15，當表大小為 10 時，兩個鍵都會給出相同的索引：5 % 10 = 5 和 15 % 10 = 5。這是一個碰撞。

再舉一個例子：

假設你正在創建一個名字的字典，你有一個簡單的哈希函數，它返回名字的第一個字母。然而，80%的名字都以「A」開頭。這不僅僅是碰撞，這是一個問題。

7.2 解決碰撞的方法 – 鏈表

有幾種方法可以解決哈希表中的碰撞。兩種最常見的方法是鏈表 (chaining) 和開放定址法 (open addressing)。

鏈表 (Chaining)

優點：

• 實現簡單。
• 在碰撞較少的情況下效率高。
• 較不依賴於哈希表的填充密度。

缺點：

• 需要額外的記憶體來存儲鏈表的指針。
• 在碰撞較多的情況下，由於鏈條過長，性能可能下降。

鏈表方法的實現範例：

你可以只研究 insert 函數的工作方式，但我決定列出完整的代碼以便於理解。

class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# 使用範例：
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 輸出: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # 輸出: None

7.3 方法二 – 開放定址法

開放定址法 是指在碰撞發生時，尋找數組中的下一個可用槽位。存在不同的策略來尋找新槽位：線性探測、平方探測和雙重哈希。

優點：

• 不需要額外的記憶體來存儲指針。
• 更緊湊的數據表示。

缺點：

• 當表的填充密度高時，性能可能顯著下降。
• 解決碰撞需要更多的計算資源。

開放定址法的策略範例

線性探測 (Linear Probing):

• 步長為 1 的探測：index = (index + 1) % size。
• 簡單，但可能導致“叢集效應”。

平方探測 (Quadratic Probing):

• 步長按平方增加的探測：index = (index + i^2) % size。
• 減少叢集效應，但實現較困難。

雙重哈希 (Double Hashing):

• 使用第二個哈希函數計算步長：index = (index + i * hash2(key)) % size。
• 更少的叢集效應，但實現複雜。

開放定址法的實例（線性探測）：我會提供完整的代碼，你可以只研究 insert 函數的工作方式

class HashTableOpenAddressing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

# 使用範例：
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 輸出: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # 輸出: None

7.4 碰撞對哈希表的影響

碰撞對性能的影響。

平均訪問時間：

• 在理想情況下（無碰撞），哈希表中元素的平均訪問時間為 O(1)。
• 碰撞會增加訪問時間，因為需要處理鏈表或探測槽位，這增加了操作數量。

鏈長的增加：

• 在鏈表方法中，當碰撞數大時，鏈長的增加可能導致搜尋、插入和刪除操作的線性訪問時間 O(n)。
• 較長的鏈會增加查找或插入元素所需的比較次數。

空間複雜度：

• 在鏈表方法中，鏈表指針的存儲需要額外的記憶體。
• 在開放定址法中，當表的填充率超過某個水平（通常約為70-80%）時，碰撞數顯著增加，因此訪問時間也會增加。

叢集效應： 在開放定址法中（尤其是在線性探測中）可能出現叢集效應，當多個連續的槽位被佔用時，這增加了碰撞的概率並降低了性能。

碰撞對性能影響的分析示例：

這是為喜歡深入研究的朋友準備的

import time
import random

# 線性探測
class HashTableOpenAddressing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

# 大量插入數據的生成
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# 插入數據並測量時間
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"插入時間: {time.time() - start_time:.6f} 秒")

# 搜索數據並測量時間
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"搜索時間: {time.time() - start_time:.6f} 秒")