Hash 學習影片

https://www.youtube.com/watch?v=eH5ihbNHD70
https://www.youtube.com/watch?v=O4dGJZ4J0Bk

Hash 的意義與用途

Hash（雜湊）是一種透過數學運算，將任意大小的輸入數據轉換成固定大小的輸出數據（通常是數字或字串）的技術，這樣的轉換函數稱為「雜湊函數（Hash Function）」，生成的輸出值則稱為「雜湊值（Hash Value）」。

Hash 通常用於以下幾種情境：

1. 資料驗證：將一段資料生成雜湊值並存儲，之後可以通過對比資料的雜湊值是否一致來確認資料是否被篡改。
2. 資料儲存與搜尋：利用雜湊函數將鍵值轉換成索引，可以在雜湊表（Hash Table）中快速找到對應的值。
3. 加密與安全性：常見的密碼學 Hash 函數（如 SHA-256、MD5）被用來加密、數位簽章、以及生成雜湊指紋。
4. 資料去重與分區：通過 Hash 值的唯一性和均勻性，可用來避免資料重複和對資料進行分區管理（如 MapReduce 中的資料分區）。

客製化雜湊方法

客製化雜湊方法的需求通常來自於特定應用場景，以下是客製化雜湊的步驟與注意事項：

設計適合的雜湊函數：

• 根據應用場景，選擇合適的雜湊函數（例如，用於密碼學應用時需要抗碰撞性較強的函數）。
• 設計雜湊函數時需考量到分布均勻性與計算效能。

設計輸入資料的預處理方式：

• 對於多變的輸入格式（如複雜的結構體、字串或其他資料結構），先做資料的標準化處理。

選擇適當的模數（Modulo）與表長（Table Size）：

• 表長（雜湊表大小）應選取質數以降低衝突概率。
• 避免選擇與輸入特徵相關性高的表長。

雜湊函數的優化與測試：

• 透過實驗與測試（如測量衝突率、均勻分布性），不斷調整雜湊函數，確保其效能與穩定性。

Hash Table（雜湊表）

雜湊表是一種根據雜湊函數進行數據查找的資料結構。其核心概念是透過雜湊函數將鍵（Key）映射到表中的索引位置，從而在常數時間內（O(1)）進行查找、插入和刪除操作，雜湊表在資料量巨大、查找速度要求高的情境下特別有效。

Hash Table 的基本操作：

• 插入（Insert）：將鍵值對（Key-Value Pair）根據鍵的雜湊值插入到對應的表格位置。
• 查找（Search）：通過鍵計算出雜湊值，再根據雜湊值定位並取出對應的資料。
• 刪除（Delete）：通過鍵找到對應位置，將資料刪除或標記為刪除狀態。

雜湊衝突解決方法

雜湊表可能會出現「雜湊衝突」，即不同的鍵被雜湊到相同的表格位置。為了解決這一問題，通常使用以下幾種策略：

開放定址法（Open Addressing）

• 二次探測（Quadratic Probing）：每次衝突後檢查的位置間隔按二次方遞增（即查找間隔為 1, 4, 9, ...）。
• 雙重雜湊（Double Hashing）：使用兩個雜湊函數來計算下一個位置，以減少雜湊衝突。

鏈結法（Separate Chaining）

在每個表格位置維護一個鏈結串列（Linked List），所有映射到同一位置的資料都被存入該串列中。插入資料時直接加入串列尾端，查找與刪除時遍歷該串列。

再雜湊（Rehashing）

當雜湊表負載過重（填充因子過大）時，創建更大的表格並重新將所有資料進行雜湊，減少衝突。

Hash Search（雜湊查找）

雜湊查找是一種透過雜湊函數快速定位資料的查找方式，通常具有 O(1) 的查找時間複雜度。其步驟如下：

1. 對查找鍵進行雜湊運算，得到對應的索引位置。
2. 根據索引位置取出資料並對比是否為查找目標（解決衝突情況下需要進行額外查找）。
3. 若匹配，則返回結果；若不匹配則繼續查找，直到找到或確認資料不在表中。

Set 與 Map 教學與筆記

在 Python 或 C++ 等語言中，Set 與 Map 都是基於 Hash Table 實作的資料結構：

Set（集合）：
用於存儲不重複元素的集合結構。
基本操作包括插入（Add）、刪除（Remove）、查找（Contains）。
查找時間複雜度通常為 O(1)。

my_set = set()
my_set.add(1)
my_set.add(2)
print(1 in my_set)  # True

Map（字典/映射）：
用於存儲鍵值對（Key-Value Pair），類似於雜湊表。
基本操作包括插入（Insert）、刪除（Delete）、查找（Get/Find）。
查找時間複雜度通常為 O(1)。

my_map = {}
my_map["key"] = "value"
print(my_map.get("key"))  # "value"

操作筆記：
當進行大批量資料操作時，應避免頻繁擴展表格大小以降低效能損耗。
設計良好的雜湊函數能顯著降低查找、插入、刪除等操作的時間複雜度，確保系統效能穩定。
常見的 Hash 函數與實作範例
以下是 Python 中常見的雜湊函數與自定義雜湊表的簡單範例：

class CustomHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

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

    def insert(self, key, value):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])

    def search(self, key):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

    def delete(self, key):
        index = self._hash(key)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                self.table[index].pop(i)
                return True
        return False