創建一個更好的散列函數

#include <iostream> 
#include <iomanip> 
#include <string> 
#include <vector> 

using namespace std; 

class Item { 
public: 
    Item(const string & v): value(v), next(0) { } 
    string value; 
    Item * next; 
}; 

int hash_function(const string & s) 
{ 
    unsigned int hashval = 0; 
    int i = s.length(); 
    while (i > 0) 
{ 
     hashval += s[--i]; 
}  
return hashval%101; 
} 

main() 
{ 
    string name; 
    int index; 
    Item * p; 

    vector<Item *> bucket(101); 

    for (index = 0; index < 101; index++) 
     bucket[index] = 0; 

    while (cin >> name) { 
     p = new Item(name); 
     index = hash_function(name); 

     // push front 
     if (bucket[index] != 0) 
      p->next = bucket[index]; 
     bucket[index] = p; 
    } 

    for (index = 0; index < 101; index++) 
     if (bucket[index] != 0) { 
      cout << setw(3) << index << ": "; 
      p = bucket[index]; 
      while (p != 0) { 
       cout << p->value << " "; 
       p = p->next; 
      } 
      cout << endl; 
     } 

    Item * temp; 
    for (index = 0; index < 101; index++) { 
     p = bucket[index]; 
     while (p != 0) { 
      temp = p; 
      p = p->next; 
      delete temp; 
     } 
    } 
}

它包含兩個非常簡單的散列函數。我正在努力研究未被評論的那個，因爲它在測試時似乎是兩者中較好的一個。我想要一組輸入的名字均勻地分佈在它自己的存儲桶中，目前看起來似乎正在工作，除了以相同字母開頭的名稱之外。例如，艾米和愛麗絲將出現在同一個桶中，依此類推。創建一個更好的散列函數

這裏是一個示例輸入/輸出：

Alice 
Amy 
Barry 
Carrie 
David 
Garret 
Edward 
Henry 
Ingrid 
Fred 
65: Amy Alice 
66: Barry 
67: Carrie 
68: David 
69: Edward 
70: Fred 
71: Garret 
72: Henry 
73: Ingrid

我可以添加到我的算法，將允許艾米和愛麗絲什麼要放置在自己的桶？

來源

2011-03-20 mikhailovich

請提供有效的代碼。你的'hash_function'不返回任何東西，'main'沒有返回類型。切換到更好的編譯器可能會有幫助。 – ybungalobill 2011-03-20 21:58:35

手動計算您記住的一個示例名稱的散列函數，並將其與您上面發佈的數據進行比較。 – 2011-03-20 22:08:02

不是盲目添加每個字母，而是給每個字母賦予一些權重，這樣cpp,pcp,ppc都可以產生不同的散列值。

這裏是小改進版本：

int hash_function(const string & s) 
{ 
    double hashval = 0; 
    int i = s.length(); 
    double weight = 1.0; 
    while (i > 0) 
    { 
     hashval += weight * s[--i]; 
     weight *= 1.5; 
    }  
    return (int) hashval; 
}

假設串s不要太長，否則會出現溢出！

來源

2011-03-20 22:14:44 Nawaz

溢出可以很容易地修復：'int exp; hashval = frexp（hashval，&exp); return int（hashval）+ exp;' - 您縮小了'hashval'並在散列值中使用其大小 – MSalters 2011-03-21 10:43:07

無法爲123和132生成唯一的散列值，散列值變爲236。 – luqmaan 2012-09-07 16:39:46

您的函數hash_function實際上並未返回值。你應該更多地關注你的編譯器的警告！

顯然它恰好具有返回字符串中第一個字符的效果。這完全是任意的。在另一個平臺上，它可能總是歸零，或導致計算機爆炸。（可能實際上不是後者。）

至於做一個更好的散列函數：一旦你修復這個bug，你將不再發現散列值只取決於第一個字符。但是，您會發現例如即「Brian」和「Brain」哈希值相同。這是你應該考慮的下一件事。

來源

2011-03-20 21:58:55

檢查這些了（由谷歌sparsehash建議）：鮑勃·詹金斯：http://burtleburtle.net/bob/hash/或保羅謝：http://www.azillionmonkeys.com/qed/hash.html

來源

2011-03-20 22:03:14 celavek

嘗試不同的加權不同的字母。在你當前的實現中（假設它的工作，如上所述），名稱ab將散列爲與ba相同的值。例如：

for (int i = 0 to str.len()) 
    hash = hash + hash + str[i]

會爲具有相同字母的兩個字符串返回不同的值，但仍然非常簡單。

來源

2011-03-20 22:03:58 yodie

創建一個更好的散列函數

回答

相關問題