mirror of
https://github.com/krahets/hello-algo.git
synced 2024-12-25 02:06:28 +08:00
48 lines
4.7 KiB
Markdown
48 lines
4.7 KiB
Markdown
|
# 小結
|
|||
|
|
|||
|
### 重點回顧
|
|||
|
|
|||
|
- 輸入 `key` ,雜湊表能夠在 $O(1)$ 時間內查詢到 `value` ,效率非常高。
|
|||
|
- 常見的雜湊表操作包括查詢、新增鍵值對、刪除鍵值對和走訪雜湊表等。
|
|||
|
- 雜湊函式將 `key` 對映為陣列索引,從而訪問對應桶並獲取 `value` 。
|
|||
|
- 兩個不同的 `key` 可能在經過雜湊函式後得到相同的陣列索引,導致查詢結果出錯,這種現象被稱為雜湊衝突。
|
|||
|
- 雜湊表容量越大,雜湊衝突的機率就越低。因此可以透過擴容雜湊表來緩解雜湊衝突。與陣列擴容類似,雜湊表擴容操作的開銷很大。
|
|||
|
- 負載因子定義為雜湊表中元素數量除以桶數量,反映了雜湊衝突的嚴重程度,常用作觸發雜湊表擴容的條件。
|
|||
|
- 鏈式位址透過將單個元素轉化為鏈結串列,將所有衝突元素儲存在同一個鏈結串列中。然而,鏈結串列過長會降低查詢效率,可以透過進一步將鏈結串列轉換為紅黑樹來提高效率。
|
|||
|
- 開放定址透過多次探測來處理雜湊衝突。線性探查使用固定步長,缺點是不能刪除元素,且容易產生聚集。多次雜湊使用多個雜湊函式進行探測,相較線性探查更不易產生聚集,但多個雜湊函式增加了計算量。
|
|||
|
- 不同程式語言採取了不同的雜湊表實現。例如,Java 的 `HashMap` 使用鏈式位址,而 Python 的 `Dict` 採用開放定址。
|
|||
|
- 在雜湊表中,我們希望雜湊演算法具有確定性、高效率和均勻分佈的特點。在密碼學中,雜湊演算法還應該具備抗碰撞性和雪崩效應。
|
|||
|
- 雜湊演算法通常採用大質數作為模數,以最大化地保證雜湊值均勻分佈,減少雜湊衝突。
|
|||
|
- 常見的雜湊演算法包括 MD5、SHA-1、SHA-2 和 SHA-3 等。MD5 常用於校驗檔案完整性,SHA-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` ,在擴容後可能會被分配到多個桶中,從而實現雜湊衝突的緩解。
|