6.4   小結

1.   重點回顧

• 輸入 key ，雜湊表能夠在 \(O(1)\) 時間內查詢到 value ，效率非常高。
• 常見的雜湊表操作包括查詢、新增鍵值對、刪除鍵值對和走訪雜湊表等。
• 雜湊函式將 key 對映為陣列索引，從而訪問對應桶並獲取 value 。
• 兩個不同的 key 可能在經過雜湊函式後得到相同的陣列索引，導致查詢結果出錯，這種現象被稱為雜湊衝突。
• 雜湊表容量越大，雜湊衝突的機率就越低。因此可以透過擴容雜湊表來緩解雜湊衝突。與陣列擴容類似，雜湊表擴容操作的開銷很大。
• 負載因子定義為雜湊表中元素數量除以桶數量，反映了雜湊衝突的嚴重程度，常用作觸發雜湊表擴容的條件。
• 鏈式位址透過將單個元素轉化為鏈結串列，將所有衝突元素儲存在同一個鏈結串列中。然而，鏈結串列過長會降低查詢效率，可以透過進一步將鏈結串列轉換為紅黑樹來提高效率。
• 開放定址透過多次探測來處理雜湊衝突。線性探查使用固定步長，缺點是不能刪除元素，且容易產生聚集。多次雜湊使用多個雜湊函式進行探測，相較線性探查更不易產生聚集，但多個雜湊函式增加了計算量。
• 不同程式語言採取了不同的雜湊表實現。例如，Java 的 HashMap 使用鏈式位址，而 Python 的 Dict 採用開放定址。
• 在雜湊表中，我們希望雜湊演算法具有確定性、高效率和均勻分佈的特點。在密碼學中，雜湊演算法還應該具備抗碰撞性和雪崩效應。
• 雜湊演算法通常採用大質數作為模數，以最大化地保證雜湊值均勻分佈，減少雜湊衝突。
• 常見的雜湊演算法包括 MD5、SHA-1、SHA-2 和 SHA-3 等。MD5 常用於校驗檔案完整性，SHA-2 常用於安全應用與協議。
• 程式語言通常會為資料型別提供內建雜湊演算法，用於計算雜湊表中的桶索引。通常情況下，只有不可變物件是可雜湊的。

2.   Q & A

Q：雜湊表的時間複雜度在什麼情況下是 \(O(n)\) ？

當雜湊衝突比較嚴重時，雜湊表的時間複雜度會退化至 \(O(n)\) 。當雜湊函式設計得比較好、容量設定比較合理、衝突比較平均時，時間複雜度是 \(O(1)\) 。我們使用程式語言內建的雜湊表時，通常認為時間複雜度是 \(O(1)\) 。

Q：為什麼不使用雜湊函式 \(f(x) = x\) 呢？這樣就不會有衝突了。

在 \(f(x) = x\) 雜湊函式下，每個元素對應唯一的桶索引，這與陣列等價。然而，輸入空間通常遠大於輸出空間（陣列長度），因此雜湊函式的最後一步往往是對陣列長度取模。換句話說，雜湊表的目標是將一個較大的狀態空間對映到一個較小的空間，並提供 \(O(1)\) 的查詢效率。

Q：雜湊表底層實現是陣列、鏈結串列、二元樹，但為什麼效率可以比它們更高呢？

首先，雜湊表的時間效率變高，但空間效率變低了。雜湊表有相當一部分記憶體未使用。

其次，只是在特定使用場景下時間效率變高了。如果一個功能能夠在相同的時間複雜度下使用陣列或鏈結串列實現，那麼通常比雜湊表更快。這是因為雜湊函式計算需要開銷，時間複雜度的常數項更大。

最後，雜湊表的時間複雜度可能發生劣化。例如在鏈式位址中，我們採取在鏈結串列或紅黑樹中執行查詢操作，仍然有退化至 \(O(n)\) 時間的風險。

Q：多次雜湊有不能直接刪除元素的缺陷嗎？標記為已刪除的空間還能再次使用嗎？

多次雜湊是開放定址的一種，開放定址法都有不能直接刪除元素的缺陷，需要透過標記刪除。標記為已刪除的空間可以再次使用。當將新元素插入雜湊表，並且透過雜湊函式找到標記為已刪除的位置時，該位置可以被新元素使用。這樣做既能保持雜湊表的探測序列不變，又能保證雜湊表的空間使用率。

Q：為什麼線上性探查中，查詢元素的時候會出現雜湊衝突呢？

查詢的時候透過雜湊函式找到對應的桶和鍵值對，發現 key 不匹配，這就代表有雜湊衝突。因此，線性探查法會根據預先設定的步長依次向下查詢，直至找到正確的鍵值對或無法找到跳出為止。

Q：為什麼雜湊表擴容能夠緩解雜湊衝突？

雜湊函式的最後一步往往是對陣列長度 \(n\) 取模（取餘），讓輸出值落在陣列索引範圍內；在擴容後，陣列長度 \(n\) 發生變化，而 key 對應的索引也可能發生變化。原先落在同一個桶的多個 key ，在擴容後可能會被分配到多個桶中，從而實現雜湊衝突的緩解。