Hash Functions 及其應用

10.1 Hash Functions 和 Hash Tables 的介紹

讓我們回顧並深入了解 hash function 和 tables。 Hash Function 是一種算法，將任意長度的輸入數據轉換為固定長度的字符串。hash function 的主要特性有：

• 確定性：相同的輸入數據總是產生相同的結果。
• 快速計算：hash 必須足夠快地計算出來。
• 不可逆性（對於加密 hash function）：從 hash 無法（或極難）恢復原始數據。
• 均勻分佈：輸入數據的微小變化導致 hash 的顯著變化。

簡單來說，相同物件的這個函數一定會相同，但如果兩個物件的 hash function 相同，這些物件不一定相等。 在數學中，這被稱為必要但不充分條件。

Hash Table 是一種數據結構，利用 hash function 來高效地存儲和查找信息。由以下組成：

• 儲存數據的“桶”陣列。
• 指示數據放入哪個桶的 hash function。

hash tables 提供快速的數據訪問，通常在平均情況下複雜度為 O(1)。

Hash Functions 在現實生活中的應用

例子：Blockchain 技術

在 blockchain 中使用 hash functions 來為區塊創建唯一識別符並確保數據完整性。每個區塊包含前一個區塊的 hash，這樣形成鏈條，使系統抵禦變更。

import hashlib
import time

class Block:
    def __init__(self, data, previous_hash):
        self.timestamp = time.time()
        self.data = data
        self.previous_hash = previous_hash
        self.hash = self.calculate_hash()

    def calculate_hash(self):
        hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
        return hashlib.sha256(hash_string.encode()).hexdigest()

# 使用範例
block1 = Block("交易 1", "0")
block2 = Block("交易 2", block1.hash)
print(f"區塊 1 的 hash: {block1.hash}")
print(f"區塊 2 的 hash: {block2.hash}")

性能比較

我們來看看在數組中搜尋重複項的問題。比較使用 hash table 和不使用 hash table 的解決方案：

import time

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

def find_duplicates_without_hash(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# 性能測試
arr = list(range(10000)) + list(range(5000))  # 含有重複項的數組

start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"使用 hash table 的執行時間: {end - start} 秒")

start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"不使用 hash table 的執行時間: {end - start} 秒")

運行程序並檢查 hash table 在加速搜尋重複項方面的效果。尤其是在大型數據集上。

10.2 Hash Functions 在實際問題中的應用示例

1. 密碼的 hash 化

hash functions 用於安全存儲密碼。系統不直接存儲明文密碼，而是存儲其 hash。當用戶輸入密碼時，系統會將其 hash 並與數據庫中的 hash 比較。

實現示例：

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

# 使用範例:
password = "securepassword"
hashed_password = hash_password(password)
print(f"密碼的 hash: {hashed_password}")

2. 數據完整性控制

hash functions 用於檢查文件和數據的完整性。例如，檢查文件在傳輸過程中是否被修改或損壞。

實現示例：

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

# 使用範例:
file_hash = get_file_hash('example.txt')
print(f"文件的 SHA-256 hash: {file_hash}")

3. 搜尋引擎和索引

搜尋引擎利用 hash functions 創建索引和快速搜尋信息。每個文檔根據關鍵詞建立索引，hash functions 幫助快速找到包含指定詞語的文檔。

實現示例：

def create_index(text):
    index = {}
    words = text.split()
    for word in words:
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

# 使用範例:
text = "This is an example text for indexing"
index = create_index(text)
print(f"索引: {index}")

10.3 使用 hash functions 的搜尋優化

1. 使用 hash tables 搜尋重複項

hash tables 允許通過比較元素的 hash 值快速找到數組中的重複項。

實現示例：

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]

2. 優化配對和的搜尋

hash tables 可有效找到數組中和為指定值的數對。

實現示例：

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# 使用範例:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 輸出: [(4, 2), (3, 3), (8, -2)]

10.4 Hash Functions 在各種算法中的應用示例

1. 計算文中單詞數量

使用 hash table 來計算文本中每個單詞出現的次數。

實現示例：

def count_words(text):
    word_count = {}
    words = text.split()

    for word in words:
        if word in word_count:
            word_count[word] += 1
        else:
            word_count[word] = 1

    return word_count

# 使用範例:
text = "this is a test this is only a test"
print(count_words(text))  # 輸出: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}

2. 檢查兩個數組的交集

檢查兩個數組是否有交集（是否至少有一個共同元素）。

實現示例：

def has_intersection(arr1, arr2):
    set1 = set(arr1)
    for item in arr2:
        if item in set1:
            return True
    return False

# 使用範例:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2))  # 輸出: True
print(has_intersection(arr1, arr3))  # 輸出: False

3. 檢查數組中元素的唯一性

檢查數組中是否僅包含唯一的元素。

實現示例：

def all_unique(arr):
    seen = set()
    for item in arr:
        if item in seen:
            return False
        seen.add(item)
    return True

# 使用範例:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1))  # 輸出: True
print(all_unique(arr2))  # 輸出: False