哈希表（在許多語言中被稱為“字典”或“關聯數組”）的查詢速度，在理想情況下，應是接近“瞬時”的常數時間，然而，在特定場景下，其性能之所以會突然、無征兆地變慢，其根源，在于其底層的“數組+哈希函數”實現機制，在兩種關鍵情況下，會從高效的“直接尋址”模式，退化為低效的“遍歷查找”或“大規模數據遷移”模式。導致這種性能“斷崖”的五大核心原因涵蓋：發生了大量的“哈希沖突”、沖突鏈表或探測序列變得“過長”、觸發了“負載因子”閾值導致了“動態擴容”、底層數組正在進行“大規模”的數據遷移、以及選用了“質量不佳”的哈希函數。

其中，觸發“負載因子”閾值導致的“動態擴容”，是導致查詢（更準確地說是“插入”操作時）“突然”變慢的最主要原因。這意味著，當哈希表內部的“擁擠”程度達到一個臨界點時，系統為了維持后續的查詢效率，會進行一次“重組”，這個重組過程，需要遍歷每一個已存在的元素，并為其重新計算存儲位置，對于一個已包含數百萬個元素的哈希表而言，這個過程，可能會造成一次肉眼可見的、秒級的“卡頓”。

一、速度的“魔法”：哈希表的“理想”狀態

在探討“為何會變慢”之前，我們必須首先深刻地理解，為何哈希表，在絕大多數情況下，都能夠實現那令人驚嘆的、近乎“瞬時”的查詢速度。

1. 核心理念：直接尋址

想象一個儲物柜，它有100個柜子，編號從0到99。如果你想存取一個物品，并且，你知道它的柜子編號（例如，58號），那么，你不需要從0號柜子，一個個地找過去，而是可以直接地、一步到位地，走到58號柜子前，進行操作。這個過程，無論儲物柜里，已經存放了1個物品，還是99個物品，其花費的時間，都是一樣的。

哈希表，正是將這種“直接尋址”的思想，進行工程化實現的、一種天才的數據結構。它在底層，通常，就是一個普通的數組。而實現“直接尋址”的關鍵，就在于那個被稱為“哈希函數”的“魔法”。

2. 哈希函數：從“任意鍵”到“數組索引”的“翻譯官”

哈希函數，是一個數學函數，它的職責，就是接收一個任意格式的“鍵”（例如，一個字符串"user-id-12345"，或一個對象），然后，通過一系列的計算，將其，穩定地、確定性地，轉化為一個在底層數組索引范圍內的“整數”。

哈希函數("user-id-12345") -> 可能會得到 58

哈希函數("order-id-67890") -> 可能會得到 12

因此，當我們要存入一個“鍵值對” ("user-id-12345", 用戶對象) 時，程序會：

計算"user-id-12345"的哈希值，得到58。

然后，直接地，將“用戶對象”，存放到內部數組的第58個位置上。

當我們要查詢"user-id-12345"時，程序，會重復這個過程，再次計算出58，然后，一步到位地，取出數組第58個位置上的“用戶對象”。

3. 理想情況：常數時間的“瞬時”訪問

在最理想的情況下，每一個不同的“鍵”，經過哈希函數的計算，都能得到一個獨一無二的“數組索引”。此時，無論是存、取、還是刪除，其操作，都只需要進行“一次哈希計算”和“一次內存尋址”，其時間復雜度為常數級別。這意味著，其執行時間，與哈希表中已存儲的元素數量，完全無關。

二、性能殺手一：“哈希沖突”

然而，“理想” rarely exists in the real world. 哈希表的第一個，也是最核心的性能挑戰，就是“哈希沖突”。

1. 什么是哈希沖突？

哈希沖突，是指，兩個或多個，完全不同的“鍵”，在經過了同一個哈希函數的計算后，卻不幸地，得到了完全相同的“數組索引”。

哈希函數("apple") -> 得到了 66

哈希函數("banana") -> 得到了 88

哈希函數("grape") -> 也不幸地，得到了 66

此時，“apple”和“grape”這兩個不同的“鍵”，就“沖突”在了數組的同一個“坑”上。

2. 沖突為何是“必然”的？

依據數學中的“鴿巢原理”，只要“鴿子”（鍵）的數量，多于“鴿巢”（數組槽位）的數量，那么，至少有一個“鴿巢”里，會擠著兩只或更多的“鴿子”。在哈希表中，即便鍵的數量，少于數組的槽位數，因為哈希函數分布的隨機性，沖突，也依然是高概率會發生的事件。

3. 沖突的解決策略：從“直接入住”到“排隊入住”

為了解決沖突，哈希表的實現，必須引入額外的“沖突解決策略”。其中，最常用的一種，被稱為“拉鏈法”。

“拉鏈法”的核心思想：哈希表底層數組的每一個“槽位”，不再直接地，存儲一個“值”，而是存儲一個指向“鏈表”頭部的指針。

當沖突發生時：

存入("apple", 蘋果對象)時，計算出索引66。發現66號槽位為空，于是，創建一個新的鏈表，將“蘋果對象”，作為第一個節點，放入其中。

存入("grape", 葡萄對象)時，再次計算出索引66。發現66號槽位，已經有一個鏈表了。于是，程序，會在這個鏈表的末尾，追加一個新的節點，來存放“葡萄對象”。

4. 性能下降的原理

“拉鏈法”在解決了沖突的同時，也引入了新的“性能瓶頸”。 當我們要查詢"grape"時，程序：

計算"grape"的哈希值，得到66，一步，定位到數組的第66個槽位。

然而，在這個槽位上，它發現的，不是一個直接的值，而是一個包含了“蘋果”和“葡萄”兩個節點的鏈表。

此時，程序，別無選擇，只能從頭到尾地，對這個小小的“鏈表”，進行一次“線性遍歷”，逐一地，比較每個節點的鍵，是否等于"grape"。

當大量的哈希沖突，發生在同一個或少數幾個索引上時，就會導致，這些索引所掛載的“鏈表”，變得異常地“長”。此時，哈希表的查詢，就從原本的、高效的“一次定位”，退化為了“一次定位 + 一次漫長的鏈表遍歷”。在最極端的情況下（即，所有鍵，都沖突在了同一個索引上），哈希表的性能，將完全退化為與一個普通的、無序的鏈表，完全相同，其查詢的時間復雜度，也從常數級別，下降到了線性級別。

三、性能殺手二：“動態擴容”

如果說“哈希沖突”，是導致哈希表性能“緩慢”下降的“慢性病”，那么，“動態擴容”，則是導致其性能“突然”卡頓一下的“急性病”。

1. 負載因子：哈希表的“擁擠度”

為了避免因哈希沖突過于頻繁，而導致的性能嚴重下降，哈希表的實現中，引入了一個關鍵的監控指標——“負載因子”。

負載因子 = 已存儲的元素數量 / 底層數組的總槽位數

它度量了哈希表的“擁擠程度”。一個負載因子為0.8的哈希表，意味著其80%的槽位，都已經被占用了。

2. “擴容”的觸發

當哈希表的“負載因子”，超過了一個預設的“閾值”時（在Java的哈希映射實現中，這個閾值，默認是0.75），“動態擴容”機制，就會被觸發。系統認為，當前的“房間”，已經太擁擠了，如果不立即“擴建”，后續新來的“客人”，發生“沖突”的概率，將急劇增加。

3. “重新哈希”的昂貴過程

“動態擴容”，并非一次簡單的內存追加，而是一次極其昂貴的、全局性的“數據大遷徙”，這個過程，通常被稱為“重新哈希”。其具體步驟如下：

創建一個新的、更大的底層數組（通常，是舊數組容量的兩倍）。

遍歷舊數組中的“每一個”已存在的元素。

對于每一個元素，必須，依據“新”的、更大的數組容量，重新地，計算一次它的哈希值，以得到它在“新家”中的“新位置”。（因為，哈希值，通常，都與數組的容量，相關）。

將這個元素，插入到新數組的、那個被重新計算出的位置上。

4. “突然變慢”的時刻

這個“重新哈希”的過程，其耗時，與哈希表中已存在的元素數量，成“線性”關系。

如果一個哈希表中，已經存儲了一百萬個元素，那么，在第一百萬零一個元素，被插入的那一刻，如果恰好，觸發了“負載因子”的閾值，那么，程序，就需要暫停下來，去完整地，執行一次對這一百萬個元素的“大遷徙”。

這個過程，可能會耗時數十毫秒，甚至數秒。對于一個需要進行實時交互的應用而言，這種“突然的、無征兆的、長時間的卡頓”，其體驗，是災難性的。

而一旦這次昂貴的“擴容”完成后，哈希表的“負載因子”會大幅下降，后續的查詢和插入，又會恢復到“瞬時”的速度。

四、在實踐中“規避”與“優化”

理解了上述兩大核心原理后，我們就可以在實踐中，采取一系列的策略，來規避和優化這些性能問題。

為哈希表“預設容量”如果，你在使用一個哈希表之前，已經能夠，大致地，預估出，你將要向其中，存入多少個元素，那么，在創建它的時候，就明確地，為其，指定一個足夠大的“初始容量”，是一個極其有效的優化手段。

例如，在Java中，new HashMap<>(initialCapacity)。

通過“一步到位”地，為其，分配一個足夠大的“房子”，我們就可以，從根本上，避免在后續的使用過程中，因為“房間不夠住”，而反復地，進行那數次昂貴的“擴建”工程。

選擇合適的“鍵”與哈希函數

盡可能地，使用“不可變”的對象（如字符串、數字）作為鍵。

如果你需要，使用自定義的對象作為鍵，那么，你必須，為這個對象，精心設計一個高質量的、能夠讓哈希值，盡可能“均勻分布”的哈希函數。

在流程中管理“性能”預期 性能，是一種重要的“非功能性需求”。

在進行需求分析和技術方案設計時，就應將“預期的數據規模”，作為一個關鍵的考量因素。

在 PingCode 這樣的研發管理平臺中，可以將性能指標（例如，“在100萬用戶數據規模下，用戶信息的查詢響應時間，應在50毫秒以內”），作為明確的、可被測試的“驗收標準”，寫入相關的需求工作項中。

對于一些大型的數據處理或遷移項目，可以在 Worktile 的項目計劃中，明確地，設立專門的“性能測試與調優”任務階段。

常見問答 (FAQ)

Q1: “哈希表”和“字典”、“關聯數組”是一回事嗎？

A1: 它們，在概念上，指的是同一種，基于“鍵值對”進行存儲和訪問的抽象數據類型。而“哈希表”，則是這種抽象數據類型，最常見、最高效的“一種底層實現方式”。在Python中，它被稱為“字典”；在JavaScript中，它被稱為“對象”或“映射”；在Java中，則被稱為“哈希映射”。

Q2: 既然會變慢，為什么哈希表還是被如此廣泛地使用？

A2: 因為，在絕大多數的、平均的情況下，其接近“常數時間”的查詢效率，遠勝于其他任何一種數據結構（如列表或樹）。其“變慢”的場景（即哈希沖突嚴重或動態擴容），是可以通過良好的設計（如預設容量、使用好的哈希函數），在很大程度上，被規避或攤銷的。

Q3: 我應該如何為我的哈希表，選擇一個合適的“初始容量”？

A3: 一個常見的經驗法則是，將你的“預期元素數量”，除以“默認的負載因子”（通常是0.75），然后再向上，取一個最接近的、2的冪次的數。例如，如果你預期，要存入10000個元素，那么一個合理的初始容量，可以是 10000 / 0.75 ≈ 13333，向上取整到2的冪次，即16384。

Q4: 什么是“完美的哈希函數”？它在現實中存在嗎？

A4: “完美的哈希函數”，是指能夠，將一個已知的、固定的鍵集合，一一地，映射到一組連續的整數（即，完全沒有哈希沖突）的函數。它在現實中，是存在的，但其應用場景，非常有限，只適用于那些“鍵集合，是完全固定不變的”的特殊情況。對于常規的、動態變化的哈希表，我們追求的，是一個能夠讓哈希值“盡可能均勻分布”的、“足夠好”的哈希函數。