C++哈希表 小結(jié)

 重點回顧

• 輸入 ?key? ，哈希表能夠在 O(1) 時間內(nèi)查詢到 ?value? ，效率非常高。
• 常見的哈希表操作包括查詢、添加鍵值對、刪除鍵值對和遍歷哈希表等。
• 哈希函數(shù)將 ?key? 映射為數(shù)組索引，從而訪問對應(yīng)桶并獲取 ?value? 。
• 兩個不同的 ?key? 可能在經(jīng)過哈希函數(shù)后得到相同的數(shù)組索引，導(dǎo)致查詢結(jié)果出錯，這種現(xiàn)象被稱為哈希沖突。
• 哈希表容量越大，哈希沖突的概率就越低。因此可以通過擴容哈希表來緩解哈希沖突。與數(shù)組擴容類似，哈希表擴容操作的開銷很大。
• 負載因子定義為哈希表中元素數(shù)量除以桶數(shù)量，反映了哈希沖突的嚴重程度，常用作觸發(fā)哈希表擴容的條件。
• 鏈式地址通過將單個元素轉(zhuǎn)化為鏈表，將所有沖突元素存儲在同一個鏈表中。然而，鏈表過長會降低查詢效率，可以進一步將鏈表轉(zhuǎn)換為紅黑樹來提高效率。
• 開放尋址通過多次探測來處理哈希沖突。線性探測使用固定步長，缺點是不能刪除元素，且容易產(chǎn)生聚集。多次哈希使用多個哈希函數(shù)進行探測，相較線性探測更不易產(chǎn)生聚集，但多個哈希函數(shù)增加了計算量。
• 不同編程語言采取了不同的哈希表實現(xiàn)。例如，Java 的 ?HashMap? 使用鏈式地址，而 Python 的 ?Dict? 采用開放尋址。
• 在哈希表中，我們希望哈希算法具有確定性、高效率和均勻分布的特點。在密碼學(xué)中，哈希算法還應(yīng)該具備抗碰撞性和雪崩效應(yīng)。
• 哈希算法通常采用大質(zhì)數(shù)作為模數(shù)，以最大化地保證哈希值的均勻分布，減少哈希沖突。
• 常見的哈希算法包括 MD5、SHA-1、SHA-2 和 SHA3 等。MD5 常用于校驗文件完整性，SHA-2 常用于安全應(yīng)用與協(xié)議。
• 編程語言通常會為數(shù)據(jù)類型提供內(nèi)置哈希算法，用于計算哈希表中的桶索引。通常情況下，只有不可變對象是可哈希的。

2.   Q & A

哈希表的時間復(fù)雜度為什么不是 O(n) ？

當(dāng)哈希沖突比較嚴重時，哈希表的時間復(fù)雜度會退化至 O(n) 。當(dāng)哈希函數(shù)設(shè)計的比較好、容量設(shè)置比較合理、沖突比較平均時，時間復(fù)雜度是 O(1) 。我們使用編程語言內(nèi)置的哈希表時，通常認為時間復(fù)雜度是 O(1) 。

為什么不使用哈希函數(shù) f(x)=x 呢？這樣就不會有沖突了

在 f(x)=x 哈希函數(shù)下，每個元素對應(yīng)唯一的桶索引，這與數(shù)組等價。然而，輸入空間通常遠大于輸出空間（數(shù)組長度），因此哈希函數(shù)的最后一步往往是對數(shù)組長度取模。換句話說，哈希表的目標是將一個較大的狀態(tài)空間映射到一個較小的空間，并提供 O(1) 的查詢效率。

哈希表底層實現(xiàn)是數(shù)組、鏈表、二叉樹，但為什么效率可以比他們更高呢？

首先，哈希表的時間效率變高，但空間效率變低了。哈希表有相當(dāng)一部分的內(nèi)存是未使用的，

其次，只是在特定使用場景下時間效率變高了。如果一個功能能夠在相同的時間復(fù)雜度下使用數(shù)組或鏈表實現(xiàn)，那么通常比哈希表更快。這是因為哈希函數(shù)計算需要開銷，時間復(fù)雜度的常數(shù)項更大。

最后，哈希表的時間復(fù)雜度可能發(fā)生劣化。例如在鏈式地址中，我們采取在鏈表或紅黑樹中執(zhí)行查找操作，仍然有退化至 O(n) 時間的風(fēng)險。

多次哈希有不能直接刪除元素的缺陷嗎？對于標記已刪除的空間，這個空間還能再次使用嗎？

多次哈希是開放尋址的一種，開放尋址法都有不能直接刪除元素的缺陷，需要通過標記刪除。被標記為已刪除的空間是可以再次被使用的。當(dāng)將新元素插入哈希表，并且通過哈希函數(shù)找到了被標記為已刪除的位置時，該位置可以被新的元素使用。這樣做既能保持哈希表的探測序列不變，又能保證哈希表的空間使用率。

為什么在線性探測中，查找元素的時候會出現(xiàn)哈希沖突呢？

查找的時候通過哈希函數(shù)找到對應(yīng)的桶和鍵值對，發(fā)現(xiàn) ?key? 不匹配，這就代表有哈希沖突。因此，線性探測法會根據(jù)預(yù)先設(shè)定的步長依次向下查找，直至找到正確的鍵值對或無法找到跳出為止。

為什么哈希表擴容能夠緩解哈希沖突？

哈希函數(shù)的最后一步往往是對數(shù)組長度 n 取余，讓輸出值落入在數(shù)組索引范圍；在擴容后，數(shù)組長度 n 發(fā)生變化，而 ?key? 對應(yīng)的索引也可能發(fā)生變化。原先落在同一個桶的多個 ?key? ，在擴容后可能會被分配到多個桶中，從而實現(xiàn)哈希沖突的緩解。