如果你喜歡的我文章，希望你可以到我的 github 給我一個 star ⭐️ Blog Repo

1. 基本介紹

Hash Table 的日常應用
Hash Table（哈希表）是一種高效的數據結構，用於在平均時間複雜度 O(1) 的情況下進行查找、插入和刪除操作。這使得 Hash Table 在許多日常應用中得到了廣泛使用，最長薦的就是密碼的存儲在安全應用中，Hash Table 可以用來存儲密碼的哈希值，從而保護用戶密碼的安全。其他狀況還有：

緩存（Cache）：在網頁瀏覽器或數據庫中，Hash Table 用於實現緩存機制，快速檢索和存儲最近使用或最常用的數據。
數據庫索引：許多數據庫使用 Hash Table 來實現索引結構，以提高查詢速度。

Hash 的重要基本特性

不可逆（Irreversible）：這是密碼學中的一個重要特性，Hash 函數是一種單向函數，無法通過哈希值反推原始密碼，儲存在資料庫的密碼通常是已經hash過後，使得沒有人知道原本的密碼長什麼樣子，除非用暴力破解，找到一組字串經過hash得到與原始密碼hash過後相同的值，通常是發生碰撞或是真的猜到密碼，才會得到相同的值。
固定長度（Fixed Length）：無論輸入數據的長度是多少，哈希函數總是生成固定長度的哈希值。例如，SHA-256 哈希函數無論輸入是短字符串還是大型文件，都會生成 256 位長度的哈希值。這種特性有助於在不同數據類型之間保持一致性。這裡的固定長度，不是只字串長度，而是儲存的位元數。
相同輸入產生相同輸出（Deterministic）：對於相同的輸入，哈希函數總是會產生相同的哈希值。這種確定性確保了哈希函數在各種應用中的一致性，例如數據校驗和數據庫索引。

2. Hash Table 的實現

Collision散裂碰撞
好的Hash Function可以減少Collision的機率，但是無法完全避免，因此需要有解決Collision的方法。舉例來說下面的程式碼：

畢竟buckets不是無限大的，python和c++經過hash後的散列值雖然不同，但是對self.length取模後是相同的，這導致他們兩個被放到了同一個桶裡。

class PyHashTable():
    def __init__(self, datas=None):
        if datas is None:
            self.length = 8
        else:
            self.length = len(datas)
        # 建立一個空的buckets
        self.buckets = [[] for i in range(self.length)]
        # 初始化buckets 把datas放進去
        self.init_buckets(datas)

    # 把datas放進去
    def init_buckets(self, datas):
        if datas is None:
            return
        for key, value in datas:
            self.__setitem__(key, value)

    # 使用hash function找到index，並且找到key對應的value
    def __getitem__(self, search_key):
        hash_value = abs(hash(search_key))
        index = hash_value % self.length
        for key, value in self.buckets[index]:
            if search_key == key:
                return value

    # 把key, value放進去 buckets list中，並且使用hash function找到index
    def __setitem__(self, key, value):
        hash_value = abs(hash(key))
        index = hash_value % self.length
        self.buckets[index].append((key, value)) # 可能會發生Collision，不同的key會被放到同一個bucket中

datas = [('python', 90), ('java', 98), ('php', 85), ('c', 100)]
hashtable = PyHashTable(datas)
print(hashtable['c'])   # 像使用字典一样 印出 100

hashtable['c++'] = 92       
print(hashtable['c++']) # 印出 92
 
print(hashtable.buckets) 
    # [
        # [], 
        # [('python', 90), ('c++', 92)], 
        # [('java', 98), ('c', 100)], 
        # [('php', 85)]
    # ]

3. 解決衝突

hashtable解決衝突的方法常見的有兩種：

開放尋址: 簡單來說就是當有衝突時，就往後找下一個空的bucket，直到找到為止。
- 比較常見的做法是開放尋址法，也就是當發生衝突時，就往後找下一個空的bucket，直到找到為止。
- 這樣的好處是，不需要額外的空間來存放衝突的元素，但是缺點是，當buckets裝滿時，找不到空bucket時，就會導致無限循環。
- 因此要做好擴容的準備，當buckets裝滿時，就要擴容，增加buckets的數量，這樣就可以減少衝突的發生。
鏈結位址法: 簡單來說就是在衝突的 bucket 中，這個bucket裡面放一個linked list，當有衝突時，就把新的元素放在這個linked list的最後面。
- 上面的程式碼，其實就是鏈結位址法的一種實現。
- append的時候，就不是單單一個value，而是一多個value
- 但是這導致在尋找的過程中，要多一次迴圈，來找到對應的key。
- 也比較浪費空間，因為每個bucket都要放一個linked list，但是linked list裡面的元素可能只有一個。

接下來我來好好說明一下開放定址法的實現，因為鏈結位址法的實現，其實就是上面的程式碼，所以就不再贅述。

3.1 開放定址法

開放定址法（Open Addressing）是處理哈希表中衝突的一種方法。在開放定址法中，當一個鍵值對應的槽已被佔用時，將會根據某種探查序列找到下一個空閒的槽。

優點

空間利用率高：開放定址法不需要為處理衝突而額外分配空間。當發生衝突時，只需依照探查序列尋找下一個空槽即可。這樣的設計使得整個哈希表的空間利用率更高。

缺點

歷經k次比較導致效能下降：如果大量的鍵（keys）發生衝突，原本應該存放在 n 號位置的鍵，可能會被放置在 n+k 號位置，這意味著在插入或查找時，需要進行 k 次比較。
- 每次比較需要將當前槽的鍵與目標鍵進行比對，如果不相同則繼續往後找下個槽，這樣的操作會導致效能下降。
- 當衝突增多時，探查序列會變長，導致插入和查找操作的時間複雜度增大，從而降低哈希表的整體性能。
無限循環風險：開放定址法可以有效避免空間浪費，但當所有的槽都被佔用時，將無法找到空閒的槽存放新鍵，這時候就會出現無限循環的情況，導致插入操作失敗。
- 當哈希表接近滿載時，探查序列變得很長，這不僅增加了操作時間，也增加了無限循環的風險。因此，哈希表需要保持適當的負載因子（load factor），通常在負載因子超過某個臨界值時進行擴容，以防止這種情況的發生。

但是這兩個缺點可以透過擴容的方式來解決。因為以下兩個因素而減少比較次數和衝突的發生：

增加buckets的數量：例如，從原來的 M 個桶增加到 2M 個或更多。這樣已使用的桶數佔總桶數的比例降低，減少衝突的機率。
重新哈希：也因為擴容了，所以需要重新計算hash值，這時候原本發生衝突的key，因為重新計算hash值，原先衝突的值在新table中可能不再衝突，減少連續探測的次數（使得k比較次數減少）。
因此，透過減少衝突和比較次數，提高了insert和search的效能。python 實現的 hash table 有 2/3 被佔用時就會擴容，並且重新哈希。

但是以下程式沒有實現自動擴容，只是實現了開放定址法的基本核心概念。

初始空間擴大兩倍，避免發生高碰撞
在__setitem__和__getitem__時，如果發生碰撞，就往後找下一個bucket index = (index + 1) % self.length

class PyHashTable():
    def __init__(self, datas=None):
        if datas is None:
            self.length = 8
        else:
            self.length = len(datas) * 2 # 擴容，如果有資料就是資料的兩倍 避免發生高碰撞

        self.buckets = [None for i in range(self.length)]
        self.init_buckets(datas)

    def init_buckets(self, datas):
        if datas is None:
            return
        for key, value in datas:
            self.__setitem__(key, value)

    def __getitem__(self, search_key):
        hash_value = abs(hash(search_key))
        index = hash_value % self.length
        while self.buckets[index] is not None:
            if self.buckets[index][0] == search_key:
                return self.buckets[index][1]
            index = (index + 1) % self.length # 如果發生碰撞，就往後找下一個bucket

        return None

    def __setitem__(self, key, value):
        hash_value = abs(hash(key))
        index = hash_value % self.length
        while self.buckets[index] is not None:
            index = (index + 1) % self.length # 如果發生碰撞，就往後找下一個bucket

        self.buckets[index] = (key, value)

而需要注意的是，在開放定址法中進行刪除時，要有特別處理：

因為如果直接刪除(原本有資料因刪除改None)，會導致後面的元素無法找到(本來發生碰撞的資料要找下一筆，檢查時發現是None以為沒有資料)
所以要進行標記刪除，而不是真的刪除。

class HasDeleted():
    def __getitem__(self, item):
        return None

class PyHashTable():

    def __delitem__(self, del_key):
        hash_value = abs(hash(del_key))
        index = hash_value % self.length
        while self.buckets[index] is not None:
            if self.buckets[index][0] == del_key:
                self.buckets[index] = HasDeleted() # 給他一個刪除的標記物件
                return True

            index = (index + 1) % self.length

        return False

增加了__delitem__，邏輯刪除一個key，那麼__setitem__方法也要做出修改，這個執行了邏輯刪除的桶，應當被視為一個空的桶。

def __setitem__(self, key, value):
        hash_value = abs(hash(key))
        index = hash_value % self.length
        while not isinstance(self.buckets[index], (type(None), HasDeleted)): # 檢查是否為None或是HasDeleted物件
            index = (index + 1) % self.length

        self.buckets[index] = (key, value)

時間複雜度

Access 訪問
- Best Case O(1) 在理想情況下，我們能夠直接根據鍵（key）計算出其哈希值，並在常數時間內訪問到對應的值。
- Worst Case O(n) 所有的鍵都被映射到相同的哈希槽中（發生嚴重的碰撞）。這種情況下，哈希表會退化成一個鏈表，訪問操作需要遍歷整個鏈表。
Search 搜尋
- Best Case O(1) 哈希函數將鍵均勻分佈在哈希表的不同槽中，查找操作可以在常數時間內完成。
- Worst Case O(n) 所有鍵都被映射到相同的哈希槽中（發生嚴重的碰撞），導致哈希表退化成鏈表，需要遍歷整個鏈表才能找到目標鍵。
Insertion 插入
- Best Case O(1) 在沒有發生碰撞的情況下，可以在常數時間內將新鍵插入到哈希表中。
- Worst Case O(n) 在最壞情況下，如果發生大量碰撞，需要遍歷整個鏈表才能找到合適的插入位置。此外，如果哈希表需要擴容，重新哈希整個表的成本也是 O(n)。
Deletion 刪除
- Best Case O(1) 在沒有碰撞的情況下，可以在常數時間內刪除目標鍵。
- Worst Case O(n) 如果發生大量碰撞，需要遍歷整個鏈表才能找到目應刪除的鍵。此外，如果哈希表需要擴容，重新哈希整個表的成本也是 O(n)。

總結
最佳情況（Best Case）
在沒有發生碰撞的情況下，Hash Table 的所有基本操作（訪問、查找、插入、刪除）都可以在 O(1) 的時間內完成。
這依賴於哈希函數能夠將鍵均勻分佈在哈希表的不同槽中。

最壞情況（Worst Case）
當所有鍵都被映射到相同的哈希槽中，發生嚴重的碰撞，哈希表會退化成鏈表，基本操作（訪問、查找、插入、刪除）的時間複雜度會變成 O(n)。
這通常是由於哈希函數設計不當或哈希表負載因子過高導致的。

進階：稀疏+密集數據結構

在 Python 3.6 之前，Python 字典（dictionary）使用一個哈希表來存儲 key-value 對。從 Python 3.6 開始，Python 字典引入了密集數組和稀疏數組的結合來實現更高效的存儲和查找。以下是這兩種實現的詳細說明，以及它們的差異和優點。

舊字典（Python 3.6 之前）

在 Python 3.6 之前:

字典使用一個簡單的哈希表來存儲 key-value 對。
哈希表由一個數組組成，其中每個槽（slot）包含一個鍵（key）、值（value）和哈希值（hash）。
當插入一個新元素時，使用鍵的哈希值來決定它應該存儲在數組中的哪個槽中。
如果發生碰撞（即兩個不同的鍵有相同的哈希值），則使用鏈接法或開放地址法來處理。

簡單來說就是我們上述的程式碼。

新字典（Python 3.6 及以後）

從 Python 3.6 開始，字典的實現引入了密集數組和稀疏數組的結合：

密集數組（Compact Array）：密集數組用來存儲實際的 key-value 對。這是一個連續的數組，存儲所有的鍵和值，保證了數據在內存中的連續性。
稀疏數組（Sparse Array）：稀疏數組存儲指向密集數組的索引。每個哈希槽中存儲的是指向密集數組中元素的索引，而不是直接存儲 key-value 對。
這種新的實現方式保留了插入順序，即鍵值對是按照插入順序存儲的，這在某些應用中非常有用。

差異

內存使用：
- 舊的實現：每個槽（slot）中都需要存儲鍵、值和哈希值，內存使用較多。
- 新的實現：密集數組將鍵和值連續存儲，稀疏數組存儲索引，內存使用更加緊湊和高效。
性能：
- 舊的實現：查找、插入和刪除操作的時間複雜度平均為 O(1)，但由於內存分佈不連續，會導致更多的緩存未命中，影響性能。
- 新的實現：密集數組的連續存儲方式提高了緩存命中率，進一步提高了查找和插入操作的性能。
- 所謂的緩存命中率指的是在計算機系統中，CPU 速度遠快於主內存的訪問速度，為了彌補這一差距，現代處理器設計了多級緩存（cache）。當 CPU 需要讀取數據時，它首先會查看數據是否在緩存中。如果數據在緩存中，則稱為“緩存命中”，這樣可以非常快速地訪問數據；如果數據不在緩存中，則稱為“緩存未命中”，這樣 CPU 就需要從較慢的主內存中讀取數據。
插入順序：
- 舊的實現：不保證插入順序。
- 新的實現：保證鍵值對按照插入順序存儲，這在需要按順序處理元素的應用中非常有用。
內存碎片：
- 舊的實現：由於鏈接法或開放地址法可能導致內存碎片，進而影響性能。
- 新的實現：密集數組減少了內存碎片問題，提高了內存使用效率。