哈希表的工作原理

6.1 哈希表的定義及其結構

哈希表是一種數據結構，它具有快速查找、插入和刪除元素的能力，通過哈希函數計算陣列或列表中的索引。哈希表通常用於實現關聯陣列，也稱為字典。

哈希表的重要方面

陣列是哈希表的主要組成部分，它儲存指向元素或元素列表的指針。

哈希函數： 將字典的鍵轉換為陣列索引的函數。

碰撞：當兩個不同的鍵具有相同的哈希值時的情況。解決碰撞的方法有鏈接法（chaining）或開放定址法（open addressing）。

字典範例：

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

哈希表結構範例：

6.2 哈希表的基本操作

哈希表的基本操作：插入、查找、刪除

1. 插入 (Insertion)： 將新元素（鍵值對）添加到哈希表的過程。

插入步驟：

1. 使用哈希函數計算鍵的哈希值。
2. 根據哈希值找到陣列中的索引。
3. 如果該索引處已有元素（碰撞），則將元素添加到列表中（在鏈接法中）或找到下個可用的索引（在開放定址法中）。

使用鏈接法插入到哈希表的範例：

class HashTable:
    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))

# 使用範例：
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. 查找 (Search)： 在哈希表中按給定鍵查找值的過程。

查找步驟：

1. 使用哈希函數計算鍵的哈希值。
2. 根據哈希值找到陣列中的索引。
3. 檢查鍵是否在元素列表中（在鏈接法中）或在索引處（在開放定址法中）。

使用鏈接法查找哈希表中的範例：

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

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

    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

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

3. 刪除 (Deletion)： 從哈希表中刪除元素（鍵值對）的過程。

刪除步驟：

1. 使用哈希函數計算鍵的哈希值。
2. 根據哈希值找到陣列中的索引。
3. 從列表中刪除元素（在鏈接法中）或將索引處的值設置為None（在開放定址法中）。

使用鏈接法從哈希表中刪除的範例：

class HashTable:
    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 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 = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # 輸出: None

6.3 哈希表的時間複雜度

哈希表操作的時間複雜度

插入 (Insertion)：

• 平均情況：O(1)
• 最壞情況：O(n)（當有大量碰撞或所有元素都進入同一個位置）

查找 (Search)：

• 平均情況：O(1)
• 最壞情況：O(n)（當有大量碰撞或所有元素都進入同一個位置）

刪除 (Deletion)：

• 平均情況：O(1)
• 最壞情況：O(n)（當有大量碰撞或所有元素都進入同一個位置）

解釋：

平均情況： 在平均情況下，哈希函數將元素均勻分佈在表中，每個元素都在自己獨特的單元中，提供恆定時間訪問 O(1)。

最壞情況： 在最壞情況下，由於不良哈希函數或大量碰撞，所有元素都進入一個單元。此時，哈希表變成鏈表，操作的時間複雜度變為 O(n)。

6.4 哈希表的應用範例

1. 字典（關聯陣列）的實現

哈希表常用於實現字典，它們允許存儲鍵值對並通過鍵提供快速訪問。

例子：

# 創建字典
dictionary = {}

# 插入元素
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# 查找元素
print(dictionary["banana"])  # 輸出: 2

# 刪除元素
del dictionary["cherry"]

# 檢查鍵是否存在
if "apple" in dictionary:
    print("鍵 'apple' 存在於字典中")  # 輸出: 鍵 'apple' 存在於字典中

現在你已經對 Python 的字典及其運作方式有了更多的了解。

2. 緩存計算結果

哈希表用於緩存昂貴計算的結果，以加速後續請求。

例子：

# 用於存儲結果的緩存
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # 一個昂貴計算的例子
    cache[x] = result
    return result

# 使用緩存
print(expensive_computation(10))  # 輸出: 100（計算並緩存）
print(expensive_computation(10))  # 輸出: 100（來自緩存）

3. 計算文本中詞的頻率

哈希表用於計算文本中每個詞的出現次數。

例子：

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# 輸出結果
for word, count in word_count.items():
    print(f"詞 '{word}' 出現 {count} 次")

4. 尋找列表中的重複項

哈希表用於有效地尋找列表中的重複項。

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用範例
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 輸出: [2, 4]