Java：在散列函數溢出方面需要幫助

Question

我正在做一項任務，我必須將10,000個數字散列到負載大小爲.1，.2 .3 .... ....的哈希表中。我的問題是，我的散列函數給我一些溢出或類似的東西。如果我爲36077（mod）20,000的加載因子爲0.5的表做散列，它會給我16070作爲關鍵。這隻發生在高於負載因數的數字上。這是我的散列函數的代碼。

public int linearHash(int in){ 
    int hashKey = in%hashTableArray.length; 
    while(this.hashTableArray[hashKey] != 0){ 
     hashKey += 1; 
    } 
    return hashKey; 
} 

謝謝。

Answer 1

您不檢查是否超出while循環中hashTableArray的索引範圍。你可以這樣做：

while (hashKey < hashTableArray.length && this.hashTableArray[hashKey] != 0){ 

Answer 2

Reimeus指出OutOfBound問題並給出了一個解決方案。我只是想增加一些關於處理碰撞的方法。

您的功能看起來像開放尋址方法。而不是hashKey += 1;也許你可以考慮遞增上述in

public int linearHash(int in){ 
    int hashKey = in%hashTableArray.length; 
    while(this.hashTableArray[hashKey] != 0){ 
     in ++; 
     hashKey = in%hashTableArray.length; 
    } 
    return hashKey; 
} 

的示例代碼沒有檢查哈希表溢出。自動增量不應該超過hashTableArray.length次。否則你的程序陷入死循環

並請注意，通過檢查hashTableArray[hashKey] != 0來確定插槽是否空閒是不安全的。例如，你的元素中有什麼數字0和20000。