我正在使用雙哈希解決沖突的哈希表。我怎么知道合適的尺寸是多少？我知道它必須啟動以最小化碰撞次數。
uj5u.com熱心網友回復：
不，將尺寸設定為素數是沒有意義的，這會為您增加很多額外的作業。只需將大小設為 2 的冪，并在哈希表中的物件數量達到某個閾值時將其加倍，例如大小的 50% 或 25%。
uj5u.com熱心網友回復：
實作哈希表的最簡單方法是使用 2 次冪大小的哈希表。
原因是如果 N = 2 M，那么計算H % N就像計算一樣簡單H & (N - 1)。
使用像 MurmurHash3_32 這樣的快速哈希函式，使用哈希表最慢的部分實際上是計算模數。H & (N - 1)不計算模數，而是按位 AND 計算速度更快（如果 N 是 2 的冪，它與模數相同）。
有人可以有效地聲稱 MurmurHash 遭受與種子無關的多重沖突，因此容易受到哈希沖突拒絕服務攻擊。沒錯，但您不應該使用鏈表來解決哈希沖突。您應該只使用可以通過一些比較函式（大于、等于、小于）對鍵進行排序的哈希表，然后您可以使用紅黑樹（或 AVL 樹）來解決哈希沖突。如果沒有自然比較函式（例如復數），您可以發明一個。
使用幾乎總是只有單個根元素的紅黑樹與 MurmurHash 比嘗試通過使用 SipHash 來“安全”然后愚蠢地使用鏈表來解決哈希沖突（這導致需要非常慢的 SipHash）要快得多首先）。
理論上，對于大小很少變化的非 2 次冪大小的哈希表，您可以使用“使用乘法除以不變整數的快速除法”技巧，但這比 2 次冪大小和按位 AND 慢.
主要大小僅適用于非常差的哈希函式。MurmurHash 盡管存在與種子無關的多重沖突，但如果表大小是 2 的冪，則不會與合理的（非攻擊者生成的）鍵發生沖突。
uj5u.com熱心網友回復：
如果您詢問當前大小，您可以使用該sizeof(table)/sizeof(element)函式，因為您使用的是雙散列方法。如果您詢問哈希表滿后的新大小（通過某個標準），那么最常見的是添加 10 個新插槽。這應該基于您使用桌子的目的。大多數其他語言的內置表的默認設定是如果 0.75 滿，則添加 10 個插槽。如果是關于其他的，那么請修改您的問題，使其更具描述性。編輯：我剛剛注意到我上面的答案，我認為使用 2^p 方法在指數增加的表中也很常見，并且對雙散列非常有幫助。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/485433.html