從線性探測移動到二次探測（散列碰撞）

我目前的散列表實現是使用線性探測，現在我想要移動到二次探測（後來鏈接，也許雙哈希）。我讀過一些文章，教程，維基百科等......但我仍然不知道我應該做什麼。從線性探測移動到二次探測（散列碰撞）

線性探測，基本上，有1步，這很容易做到。在搜索時，插入或從哈希表中移除元素，我需要計算一個哈希併爲我這樣做：

index = hash_function(key) % table_size;

然後，當查找，插入或通過表中刪除我循環，直到我找到一個免費桶，這樣的：

do { 
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) { 
     // FOUND ELEMENT 

     return; 
    } else { 
     index = (index + 1) % table_size; 
    } 
while(/* LOOP UNTIL IT'S NECESSARY */);

至於二次探測，我想我需要做的是改變「指數」步長是如何計算的，但是這就是我不明白我應該怎麼做。我已經看過各種代碼，並且它們都有些不同。

此外，我已經看到一些二次探測的實現，其中散列函數被改變以適應（但不是全部）。這種改變是否真的需要，或者我可以避免修改哈希函數，並仍然使用二次探測？

編輯： 看完一切所指出的禮Bendersky下面我想給我的總體思路。下面是部分代碼在http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx：

15 for (step = 1; table->table[h] != EMPTY; step++) { 
16  if (compare (key, table->table[h]) == 0) 
17  return 1; 
18 
19  /* Move forward by quadratically, wrap if necessary */ 
20  h = (h + (step * step - step)/2) % table->size; 
21 }

有兩件事情我不明白......他們說，二次探測使用c(i)=i^2通常完成。然而，在上面的代碼，它做更多的東西一樣c(i)=(i^2-i)/2

我準備實現這個在我的代碼，但我只想做：

index = (index + (index^index)) % table_size;

...而不是：

index = (index + (index^index - index)/2) % table_size;

如果有的話，我會做：

index = (index + (index^index)/2) % table_size;

...因爲我見過的其它代碼示例跳水兩次。雖然我不明白爲什麼...

1）爲什麼它會減去這個步驟？
2）爲什麼潛水2？

來源

2010-02-27 Ricardo Amaral

記住，二次探測纔有效，如果表大小是素數，負載因子是<0.5;請參閱http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx，瞭解有關不同衝突解決策略的概述。 – Christoph 2010-02-27 17:13:23

@Cristoph：該陳述並不完全正確。如果表格大小爲素數，那麼如果負載因數<0.5，則保證正常工作;但這不是真正的，這是二次探測工作的* only *情況。例如，它也可以用2次冪的表格大小和任意的加載因子有效（請參閱我的答案）。 – 2010-02-28 02:14:55

@Mathew：'工作'和'有效工作'之間有區別。如果負載因子太高，（次級）集羣可能會再次成爲問題 – Christoph 2010-03-02 09:38:09

您不必修改二次探測的散列函數。最簡單的二次探測形式實際上只是將計算後的位置的正方形代替線性1,2,3。

有一個很好的資源here。以下是從那裏獲取的。這是二次探測最簡單的形式是使用簡單的多項式c(i) = i^2時：

alt text

在更一般的情況下，計算公式爲：

alt text

而且你可以選擇你的常量。

但請記住，二次探測僅在某些情況下才有用。由於Wikipedia entry狀態：

二次探測提供了良好的存儲緩存，因爲它保留了一些參考地方;然而，線性探測具有更大的局部性，因此，更好的緩存性能。二次探測更好地避免了可能發生線性探測的聚類問題，儘管它不是免疫。

編輯：像計算機科學許多事情，確切的常量和二次探測的多項式啓發式。是的，最簡單的形式是i^2，但您可以選擇任何其他多項式。維基百科給出的例子是h(k,i) = (h(k) + i + i^2)(mod m)。

因此，很難回答你的「爲什麼」的問題。這裏唯一的「爲什麼」是爲什麼你需要二次探測？使用其他形式的探測和獲取聚簇表時遇到問題？或者這只是一項家庭作業或自學？

請記住，到目前爲止，散列表最常見的衝突解決技術是鏈式或線性探測。二次探測是一種適用於特殊情況的啓發式選項，除非您知道自己做得非常好，否則我不會推薦使用它。

來源

2010-02-27 17:10:09

對不起，但數學公式並沒有幫助我。 :(你沒有給我比我已經讀過的更多的東西。 – 2010-02-27 17:45:03

@Nazgulled：我真的沒有看到你有什麼問題 - 而且你沒有其他答案，也許我不是唯一的答案。我認爲你應該嘗試詳細說明你的問題，並重新修改它來準確解釋你需要什麼 – 2010-02-27 18:41:38

我看看數學公式，我不理解他們，我也不知道在代碼中做什麼。我需要知道該怎麼做，而不是數學公式。 – 2010-02-27 19:57:52

還有就是要實現二次探測，如果你的表的大小是2的冪特別簡單和優雅的方式：

step = 1; 

do { 
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) { 
     // FOUND ELEMENT 

     return; 
    } else { 
     index = (index + step) % table_size; 
     step++; 
    } 
} while(/* LOOP UNTIL IT'S NECESSARY */);

而不是看着偏移0，1，2，3，4 ...從原始索引開始，這將看偏移量0,1,3,6,10 ...（探測器處於偏移量（i *（i + 1））/ 2，即它是二次的）。

這是保證打在哈希表中每個位置（所以你肯定可以找到一個空水桶，如果有一個）提供表的大小是2

這裏電源是一個證明的草圖：

給定一個大小爲n的表， 0 ... n-1。

我們可以通過矛盾來證明這一點。假設有少於n個不同的值：如果是這樣，在[0，n-1]範圍內對於i必須存在至少兩個不同的整數值，使得（i *（i + 1））/ 2（mod n ）是一樣的。調用這些p和q，其中p < q。

即（P *（P + 1））/ 2 =（Q *（Q + 1））/ 2（MOD N）

=>（P + P）/ 2 =（Q + q）/ 2（MOD N）

=>點 + p = q + q（MOD 2N）

=> q - p + q - p = 0（mod 2n）

Factorise =>（q-p）（p + q + 1）= 0（mod 2n）

（q - p）= 0是平凡的情況p = q。（p + q + 1）= 0（mod 2n）是不可能的：我們的p和q的值在[0，n-1]範圍內，並且q> p，所以（p + q + 1）必須在[2，2n-2]的範圍內。

由於我們工作模2N，我們還必須應對其中兩個因素是非零棘手的情況，但乘給予0（MOD 2N）：

觀察，這兩個因素之間的差值（（p + q + 1）是（2p + 1），這是一個奇數 - 所以其中一個因素必須是偶數，而另一個必須是奇數。（q-p）（p + q + 1）= 0（mod 2n）=>（q-p）（p + q + 1）可以被2n整除。 如果n（因此2n）是冪的2，則這要求偶數因子是2n的倍數（因爲所有2n的素因子都是2，而我們的奇數因子的素因子都不是）。（q-p）具有n-1的最大值，並且（p + q + 1）具有2n-2的最大值（如在步驟9中所見），所以兩者都不可以是2n的倍數。

所以這種情況也是不可能的。

因此，假設有少於n個不同的值（在步驟2中）必須是假的。

（如果表尺寸是不是的 2的冪，該散開在步驟10）

來源

2010-02-28 02:05:00

我正在使用質數來代替... – 2010-02-28 14:49:12

從線性探測移動到二次探測（散列碰撞）

回答

相關問題