如何計算這個散列函數中的衝突？

這是一個前綴散列函數。我想計算這種方法中的碰撞次數，但我不知道如何去做。看起來這可能很簡單，但我只是想不出一個偉大的方式做到這一點....如何計算這個散列函數中的衝突？

int HashTable_qp::preHash(string & key, int tableSize) 
{ 
    string pad = "AA"; 
    //some words in the input are less than 3 letters 
    //I choose to pad the string with A because all padded characters 
    //have same ascii val, which is low, and will hopefully alter the results less 
    if (key.length() < 3) 
    { 
     key.append(pad); 
    } 
    return (key[0] + 27 * key[1] + 729 * key[2]) % tableSize; 
}

來源

2011-12-05 user977154

創建一個直方圖unsigned [tablesize]，生成一些（所有）可能的字符串並計算它們的hashval，並相應地更新直方圖histogram [hashval] + = 1; – wildplasser

@wildplasser，這將是最簡單的方法。我的答案會更快。如果這不是性能問題，我會選擇** wild的**想法。（您應該將其作爲答案發布，以幫助其他人在找到該頁面時找到它。） – FakeRainBrigand

您可以創建一個整數數組，每個代表一個哈希值。當你完成哈希循環通過嵌套循環中的數組。如果你有以下的陣列，

[0] -> 13 
[1] -> 5 
[2] -> 12 
[3] -> 7 
[4] -> 5

對於每個項目我在0到n，檢查是否匹配項我+ 1..N。用英文表示：檢查每個元素是否等於之後的任何元素它。

來源

2011-12-05 23:49:00 FakeRainBrigand

如果它是一個數組作爲基礎數據結構做： int hash = preHash(&key, array.length); if(array[hash] != null) this.count++; 如果是鏈表的數組做：

if(array[hash] != null && *(array[hash]) != null) 
this.count++

如果你只能訪問到STL庫我相信只是測試這個元素在調用散列函數之前，添加它之前就足夠了。

來源

2011-12-05 23:53:38

我正在使用stl，你能告訴我它是如何考慮stl的。 – user977154

最簡單的方法是繼承它並覆蓋它調用：HashTable_qt :: PreHash在派生類中，但實例化派生類併爲其分配一個值併爲派生類提供一個名爲CollisionCount的字段變量，並在添加新值之前初始化它爲0，在調用它之後，如果大於1，它應該具有新值。該函數用新密鑰調用 –

int Prehash（string＆key，int tableSize） { HashMap_qt :: Prehash（key，tablesize）; CollisionCount ++; } in main HashTable_qt2 * map = new HashMap_qt2（） map.CollisionCount = 0; map.Add（...）; cout << map.CollisionCount; –

創建直方圖：

unsigned histogram[tablesize] = {0};

產生一些（全部）可能的串並計算其hashval，並更新相應的直方圖：

for(iter=0; iter < somevalue; iter++) { 
hashval = hashfunc(string.iterate(iter)); // I don't know c++ 
histogram[hashval] +=1; 
}

現在你要分析腫塊的哈希表/集羣。經驗法則是，對於(tablesize==iter)，您預計約有30％的細胞count = 1，約30％爲空;其餘的有兩個或更多。

如果你總結所有的(count*(count+1))/2，除以表格大小，你應該預期在1.5左右。一個糟糕的散列函數會給出更高的值，一個完美的散列只會包含count = 1（因此：ratio = 1）的單元格。對於線性探測，您當然不應該使用tablesize = niter，但要使表格大一些，儘管如此，您可以使用相同的指標（探測器數量/條目數量）來分析其性能。

更新：散列函數及其性能的很好介紹可在http://www.strchr.com/hash_functions找到。

來源

2011-12-06 00:17:18 wildplasser

如何計算這個散列函數中的衝突？

回答

相關問題