哈希表
「哈希表hash table」，又稱「散列表」，其通過建立鍵key 與值value 之間的映射，實現(xiàn)高效的元素查詢。具
體而言，我們向哈希表輸入一個鍵key ，則可以在??(1) 時間內(nèi)獲取對應的值value 。
如圖6?1 所示，給定?? 個學生，每個學生都有“姓名”和“學號”兩項數(shù)據(jù)。假如我們希望實現(xiàn)“輸入一個
學號，返回對應的姓名”的查詢功能，則可以采用圖6?1 所示的哈希表來實現(xiàn)。
除哈希表外，數(shù)組和鏈表也可以實現(xiàn)查詢功能，它們的效率對比如表6?1 所示。
? 添加元素：僅需將元素添加至數(shù)組（鏈表）的尾部即可，使用??(1) 時間。
? 查詢元素：由于數(shù)組（鏈表）是亂序的，因此需要遍歷其中的所有元素，使用??(??) 時間。
? 刪除元素：需要先查詢到元素，再從數(shù)組（鏈表）中刪除，使用??(??) 時間。
表6?1 元素查詢效率對比
數(shù)組鏈表哈希表
查找元素??(??) ??(??) ??(1)
添加元素??(1) ??(1) ??(1)
刪除元素??(??) ??(??) ??(1)
觀察發(fā)現(xiàn)，在哈希表中進行增刪查改的時間復雜度都是??(1) ，非常高效。
我們先考慮最簡單的情況，僅用一個數(shù)組來實現(xiàn)哈希表。在哈希表中，我們將數(shù)組中的每個空位稱為「桶
bucket」，每個桶可存儲一個鍵值對。因此，查詢操作就是找到key 對應的桶，并在桶中獲取value 。
那么，如何基于key 來定位對應的桶呢？這是通過「哈希函數(shù)hash function」實現(xiàn)的。哈希函數(shù)的作用是將
一個較大的輸入空間映射到一個較小的輸出空間。在哈希表中，輸入空間是所有key ，輸出空間是所有桶（數(shù)
組索引）。換句話說，輸入一個key ，我們可以通過哈希函數(shù)得到該key 對應的鍵值對在數(shù)組中的存儲位置。
輸入一個key ，哈希函數(shù)的計算過程分為以下兩步。
1. 通過某種哈希算法hash() 計算得到哈希值。
2. 將哈希值對桶數(shù)量（數(shù)組長度）capacity 取模，從而獲取該key 對應的數(shù)組索引index 。
index = hash(key) % capacity
隨后，我們就可以利用index 在哈希表中訪問對應的桶，從而獲取value 。
設數(shù)組長度capacity = 100、哈希算法hash(key) = key ，易得哈希函數(shù)為key % 100 。圖6?2 以key 學號
和value 姓名為例，展示了哈希函數(shù)的工作原理。
本質(zhì)上看，哈希函數(shù)的作用是將所有key 構(gòu)成的輸入空間映射到數(shù)組所有索引構(gòu)成的輸出空間，而輸入空間
往往遠大于輸出空間。因此，理論上一定存在“多個輸入對應相同輸出”的情況。
對于上述示例中的哈希函數(shù)，當輸入的key 后兩位相同時，哈希函數(shù)的輸出結(jié)果也相同。例如，查詢學號為
12836 和20336 的兩個學生時，我們得到：
類似于數(shù)組擴容，哈希表擴容需將所有鍵值對從原哈希表遷移至新哈希表，非常耗時。并且由于哈希表容量
capacity 改變，我們需要通過哈希函數(shù)來重新計算所有鍵值對的存儲位置，這進一步提高了擴容過程的計算
開銷。為此，編程語言通常會預留足夠大的哈希表容量，防止頻繁擴容。
「負載因子load factor」是哈希表的一個重要概念，其定義為哈希表的元素數(shù)量除以桶數(shù)量，用于衡量哈希
沖突的嚴重程度，也常被作為哈希表擴容的觸發(fā)條件。例如在Java 中，當負載因子超過0.75 時，系統(tǒng)會將
哈希表容量擴展為原先的2 倍。
通常情況下哈希函數(shù)的輸入空間遠大于輸出空間，因此理論上哈希沖突是不可避免的。比如，輸
入空間為全體整數(shù)，輸出空間為數(shù)組容量大小，則必然有多個整數(shù)映射至同一桶索引。
哈希沖突會導致查詢結(jié)果錯誤，嚴重影響哈希表的可用性。為解決該問題，我們可以每當遇到哈希沖突時就
進行哈希表擴容，直至沖突消失為止。此方法簡單粗暴且有效，但效率太低，因為哈希表擴容需要進行大量
的數(shù)據(jù)搬運與哈希值計算。為了提升效率，我們可以采用以下策略。
1. 改良哈希表數(shù)據(jù)結(jié)構(gòu)，使得哈希表可以在存在哈希沖突時正常工作。
2. 僅在必要時，即當哈希沖突比較嚴重時，才執(zhí)行擴容操作。
哈希表的結(jié)構(gòu)改良方法主要包括“鏈式地址”和“開放尋址”。