哈希表（在許多語言中被稱為“字典”或“關聯數組”）的查詢速度，在理想情況下，應是接近“瞬時”的常數時間，然而，在特定場景下，其性能之所以會突然、無徵兆地變慢，其根源，在於其底層的“數組+哈希函數”實現機制，在兩種關鍵情況下，會從高效的“直接尋址”模式，退化為低效的“遍歷查找”或“大規模數據遷移”模式。導致這種性能“斷崖”的五大核心原因涵蓋：發生了大量的“哈希衝突”、衝突鏈表或探測序列變得“過長”、觸發了“負載因子”閾值導致了“動態擴容”、底層數組正在進行“大規模”的數據遷移、以及選用了“質量不佳”的哈希函數。
其中，觸發“負載因子”閾值導致的“動態擴容”，是導致查詢（更準確地説是“插入”操作時）“突然”變慢的最主要原因。這意味着，當哈希表內部的“擁擠”程度達到一個臨界點時，系統為了維持後續的查詢效率，會進行一次“重組”，這個重組過程，需要遍歷每一個已存在的元素，併為其重新計算存儲位置，對於一個已包含數百萬個元素的哈希表而言，這個過程，可能會造成一次肉眼可見的、秒級的“卡頓”。
一、速度的“魔法”：哈希表的“理想”狀態
在探討“為何會變慢”之前，我們必須首先深刻地理解，為何哈希表，在絕大多數情況下，都能夠實現那令人驚歎的、近乎“瞬時”的查詢速度。
- 核心理念：直接尋址
想象一個儲物櫃，它有100個櫃子，編號從0到99。如果你想存取一個物品，並且，你知道它的櫃子編號（例如，58號），那麼，你不需要從0號櫃子，一個個地找過去，而是可以直接地、一步到位地，走到58號櫃子前，進行操作。這個過程，無論儲物櫃裏，已經存放了1個物品，還是99個物品，其花費的時間，都是一樣的。
哈希表，正是將這種“直接尋址”的思想，進行工程化實現的、一種天才的數據結構。它在底層，通常，就是一個普通的數組。而實現“直接尋址”的關鍵，就在於那個被稱為“哈希函數”的“魔法”。
- 哈希函數：從“任意鍵”到“數組索引”的“翻譯官”
哈希函數，是一個數學函數，它的職責，就是接收一個任意格式的“鍵”（例如，一個字符串"user-id-12345"，或一個對象），然後，通過一系列的計算，將其，穩定地、確定性地，轉化為一個在底層數組索引範圍內的“整數”。
哈希函數("user-id-12345") -> 可能會得到 58
哈希函數("order-id-67890") -> 可能會得到 12
因此，當我們要存入一個“鍵值對” ("user-id-12345", 用户對象) 時，程序會：
計算"user-id-12345"的哈希值，得到58。
然後，直接地，將“用户對象”，存放到內部數組的第58個位置上。
當我們要查詢"user-id-12345"時，程序，會重複這個過程，再次計算出58，然後，一步到位地，取出數組第58個位置上的“用户對象”。
- 理想情況：常數時間的“瞬時”訪問
在最理想的情況下，每一個不同的“鍵”，經過哈希函數的計算，都能得到一個獨一無二的“數組索引”。此時，無論是存、取、還是刪除，其操作，都只需要進行“一次哈希計算”和“一次內存尋址”，其時間複雜度為常數級別。這意味着，其執行時間，與哈希表中已存儲的元素數量，完全無關。
二、性能殺手一：“哈希衝突”
然而，“理想” rarely exists in the real world. 哈希表的第一個，也是最核心的性能挑戰，就是“哈希衝突”。
- 什麼是哈希衝突？
哈希衝突，是指，兩個或多個，完全不同的“鍵”，在經過了同一個哈希函數的計算後，卻不幸地，得到了完全相同的“數組索引”。
哈希函數("apple") -> 得到了 66
哈希函數("banana") -> 得到了 88
哈希函數("grape") -> 也不幸地，得到了 66
此時，“apple”和“grape”這兩個不同的“鍵”，就“衝突”在了數組的同一個“坑”上。
- 衝突為何是“必然”的？
依據數學中的“鴿巢原理”，只要“鴿子”（鍵）的數量，多於“鴿巢”（數組槽位）的數量，那麼，至少有一個“鴿巢”裏，會擠着兩隻或更多的“鴿子”。在哈希表中，即便鍵的數量，少於數組的槽位數，因為哈希函數分佈的隨機性，衝突，也依然是高概率會發生的事件。
- 衝突的解決策略：從“直接入住”到“排隊入住”
為了解決衝突，哈希表的實現，必須引入額外的“衝突解決策略”。其中，最常用的一種，被稱為“拉鍊法”。
“拉鍊法”的核心思想：哈希表底層數組的每一個“槽位”，不再直接地，存儲一個“值”，而是存儲一個指向“鏈表”頭部的指針。
當衝突發生時：
存入("apple", 蘋果對象)時，計算出索引66。發現66號槽位為空，於是，創建一個新的鏈表，將“蘋果對象”，作為第一個節點，放入其中。
存入("grape", 葡萄對象)時，再次計算出索引66。發現66號槽位，已經有一個鏈表了。於是，程序，會在這個鏈表的末尾，追加一個新的節點，來存放“葡萄對象”。
- 性能下降的原理
“拉鍊法”在解決了衝突的同時，也引入了新的“性能瓶頸”。 當我們要查詢"grape"時，程序：
計算"grape"的哈希值，得到66，一步，定位到數組的第66個槽位。
然而，在這個槽位上，它發現的，不是一個直接的值，而是一個包含了“蘋果”和“葡萄”兩個節點的鏈表。
此時，程序，別無選擇，只能從頭到尾地，對這個小小的“鏈表”，進行一次“線性遍歷”，逐一地，比較每個節點的鍵，是否等於"grape"。
當大量的哈希衝突，發生在同一個或少數幾個索引上時，就會導致，這些索引所掛載的“鏈表”，變得異常地“長”。此時，哈希表的查詢，就從原本的、高效的“一次定位”，退化為了“一次定位 + 一次漫長的鏈表遍歷”。在最極端的情況下（即，所有鍵，都衝突在了同一個索引上），哈希表的性能，將完全退化為與一個普通的、無序的鏈表，完全相同，其查詢的時間複雜度，也從常數級別，下降到了線性級別。
三、性能殺手二：“動態擴容”
如果説“哈希衝突”，是導致哈希表性能“緩慢”下降的“慢性病”，那麼，“動態擴容”，則是導致其性能“突然”卡頓一下的“急性病”。
- 負載因子：哈希表的“擁擠度”
為了避免因哈希衝突過於頻繁，而導致的性能嚴重下降，哈希表的實現中，引入了一個關鍵的監控指標——“負載因子”。
負載因子 = 已存儲的元素數量 / 底層數組的總槽位數
它度量了哈希表的“擁擠程度”。一個負載因子為0.8的哈希表，意味着其80%的槽位，都已經被佔用了。
- “擴容”的觸發
當哈希表的“負載因子”，超過了一個預設的“閾值”時（在Java的哈希映射實現中，這個閾值，默認是0.75），“動態擴容”機制，就會被觸發。系統認為，當前的“房間”，已經太擁擠了，如果不立即“擴建”，後續新來的“客人”，發生“衝突”的概率，將急劇增加。
- “重新哈希”的昂貴過程
“動態擴容”，並非一次簡單的內存追加，而是一次極其昂貴的、全局性的“數據大遷徙”，這個過程，通常被稱為“重新哈希”。其具體步驟如下：
創建一個新的、更大的底層數組（通常，是舊數組容量的兩倍）。
遍歷舊數組中的“每一個”已存在的元素。
對於每一個元素，必須，依據“新”的、更大的數組容量，重新地，計算一次它的哈希值，以得到它在“新家”中的“新位置”。（因為，哈希值，通常，都與數組的容量，相關）。
將這個元素，插入到新數組的、那個被重新計算出的位置上。
- “突然變慢”的時刻
這個“重新哈希”的過程，其耗時，與哈希表中已存在的元素數量，成“線性”關係。
如果一個哈希表中，已經存儲了一百萬個元素，那麼，在第一百萬零一個元素，被插入的那一刻，如果恰好，觸發了“負載因子”的閾值，那麼，程序，就需要暫停下來，去完整地，執行一次對這一百萬個元素的“大遷徙”。
這個過程，可能會耗時數十毫秒，甚至數秒。對於一個需要進行實時交互的應用而言，這種“突然的、無徵兆的、長時間的卡頓”，其體驗，是災難性的。
而一旦這次昂貴的“擴容”完成後，哈希表的“負載因子”會大幅下降，後續的查詢和插入，又會恢復到“瞬時”的速度。
四、在實踐中“規避”與“優化”
理解了上述兩大核心原理後，我們就可以在實踐中，採取一系列的策略，來規避和優化這些性能問題。
為哈希表“預設容量”如果，你在使用一個哈希表之前，已經能夠，大致地，預估出，你將要向其中，存入多少個元素，那麼，在創建它的時候，就明確地，為其，指定一個足夠大的“初始容量”，是一個極其有效的優化手段。
例如，在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: “完美的哈希函數”，是指能夠，將一個已知的、固定的鍵集合，一一地，映射到一組連續的整數（即，完全沒有哈希衝突）的函數。它在現實中，是存在的，但其應用場景，非常有限，只適用於那些“鍵集合，是完全固定不變的”的特殊情況。對於常規的、動態變化的哈希表，我們追求的，是一個能夠讓哈希值“儘可能均勻分佈”的、“足夠好”的哈希函數。
