java哈希函數衝突

試圖在Java中編寫我自己的哈希函數。我知道這與java實現的一樣，但是想自己測試一下。當我輸入不同的值時我碰到碰撞，我不知道爲什麼。java哈希函數衝突

public static int hashCodeForString(String s) { 
int m = 1; 
int myhash = 0; 
    for (int i = 0; i < s.length(); i++, m++){ 
    myhash += s.charAt(i) * Math.pow(31,(s.length() - m)); 
    } 
return myhash; 
}

來源

2016-07-25 Earl Clark

'Math.pow（...）'返回一個double。這是否編譯？ –

編譯，是 –

Java String hashCode實現不使用'Math.pow'，而是使用int數學運算，並且允許int overflow作爲計算的一部分。你的計算沒有，這是一個巨大的差異。 –

請記住只是如何哈希表（任何語言...）實際上作品： 它由（通常是素數）數量的「桶」。散列函數的目的僅僅是將任何傳入的鍵值轉換爲桶編號。（最糟糕的情況是，輸入密鑰的100％總是在一個桶中結束，留下「鏈接列表」。）您只是努力設計一個「典型」產生的散列函數一個「分散的」值分佈，因此，當計算出模塊時，「大部分時間內大部分桶」將被「或多或少地相等」填充。 （但要記住：你永遠無法確定。）

「衝突」是完全可以預料的：事實上，「他們發生的事情。」

在我的愚見，你是「過度思考」的散列函數：我沒有看到任何令人信服的理由使用Math.pow()。預計您生成的任何值將通過取其桶的數量的絕對值模轉換爲散列桶編號。最好的方法來看看你是否想出了一個好的（對於你的數據...）是觀察桶尺寸的結果分佈。（您的目的是否「足夠好」？）

來源

2016-07-25 02:40:01

java哈希函數衝突

回答

相關問題