哈希表和Java中的二次探測幫助

Question

我真的需要幫助插入哈希表。我現在不完全明白。有人可以用外行的話來解釋二次和線性探測嗎？

public void insert(String key) 
{ 
    int homeLocation = 0; 
    int location = 0; 
    int count = 0; 

    if (find(key).getLocation() == -1) // make sure key is not already in the table 
    { 
     //****** ADD YOUR CODE HERE FOR QUADRATIC PROBING ******** 
    } 
} 

這是我正在處理的代碼。我不是要求任何人這樣做，我真的需要幫助學習整個概念

任何幫助將不勝感激。

Answer 1

首先我們說的是開放地址（或封閉散列）的方法。如果前一個已被另一個使用，則需要處理計算新哈希碼的衝突，這是因爲hashamap的每個桶最多可以包含1個元素。

所以，你有兩個參數的散列函數：

• v，用於計算哈希碼的對象的值。
• t，這是i*f其中i，稱爲步長，就是你如果碰撞發生，f是迄今達成的碰撞次數增加，每次有什麼對你的哈希函數。

以此爲出發點，你有兩種可能的功能：

H(v, t) = (H(v) + t) % n 
H(v, t) = (H(v) + c*t + d*t*t) % n 

第一個是線性函數，而第二個是二次一個（這裏談到這個tecnique的名稱）。在哪裏你應該知道什麼% n是，c和d被選爲常量來具有更好的散列函數。

實事求是地講爲線性探測：

• 你caculate H(x, 0)
• • 如果電池是自由的地方元素有
• • 如果電池被佔用計算H(x, i)
• • • 如果電池是自由的地方，在新的地址元素
• • • 如果電池佔據然後計算H(x, i+i)
• • • • 繼續下去，直到你找到一個空單元格

爲二次探測你做的是一樣的，你從開始H(x,0)，然後H(x,i)然後H(x,i+i)，所涉及的散列函數有所不同，這將給步長賦予不同的權重。