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

 重點(diǎn)回顧

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

2.   Q & A

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

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

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

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

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

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

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

最后，哈希表的時(shí)間復(fù)雜度可能發(fā)生劣化。例如在鏈?zhǔn)降刂分校覀儾扇≡阪湵砘蚣t黑樹中執(zhí)行查找操作，仍然有退化至 O(n) 時(shí)間的風(fēng)險(xiǎn)。

多次哈希有不能直接刪除元素的缺陷嗎？對(duì)于標(biāo)記已刪除的空間，這個(gè)空間還能再次使用嗎？

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

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

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

為什么哈希表擴(kuò)容能夠緩解哈希沖突？

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