더 나은 해시 함수 만들기

Question

#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; 
     } 
    } 
} 

두 개의 매우 간단한 해시 함수가 포함되어 있습니다. 내가 테스트 할 때 두 사람 중 더 나은 것 같아서, 나는 주석 처리되지 않은 것에 대해 연구하려고 노력하고있다. 나는 동일한 문자로 시작하는 이름을 제외하고는 입력 된 이름 집합이 자신의 버킷에 균등하게 배분되고 지금까지는 작동하고있는 것처럼 보이기를 원합니다. 예를 들어 Amy와 Alice는 같은 버켓에 나타납니다.

나는 에이미와 앨리스를 허용 할 내 알고리즘에 추가 할 수있는 무엇

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 

가 자신의 양동이에 배치되는 : 여기

은 샘플 입력/출력입니까?

Answer 1

각 글자를 맹목적으로 추가하는 대신 각 글자에 약간의 가중치를 주면 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 가정이 너무 오래되지 않습니다 :

여기에 약간의 개선 된 버전입니다!

Answer 2

함수 hash_function이 실제로 값을 반환하지 않습니다. 컴파일러의 경고에 더주의를 기울여야합니다!

분명히 문자열의 첫 번째 문자를 반환하는 효과가 발생합니다. 이것은 순전히 임의적입니다. 다른 플랫폼에서는 항상 0을 반환하거나 컴퓨터가 폭발 할 수 있습니다. (실제로는 후자가 아닐 것입니다.)

더 나은 해시 함수 만들기 :이 버그를 수정하면 더 이상 해시 값이 첫 번째 문자에만 의존한다는 사실을 알 수 없습니다. 그러나 예를 들어 "Brian"과 "Brain"은 같은 값으로 해시됩니다. 그것이 당신이 생각해야 할 다음 것입니다. (구글 sparsehash에 의해 제안)

Answer 3

확인이 아웃 : 밥 젠킨스 : http://burtleburtle.net/bob/hash/ 또는 폴 셰 행정 원장 : http://www.azillionmonkeys.com/qed/hash.html

Answer 4

다르게 다른 문자에 가중치를보십시오. 귀하의 현재 구현 (위에서 언급 한 것처럼 작동한다고 가정)에서 ab라는 이름은 ba와 동일한 값으로 해시됩니다. 같은 문자 :

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

같은 문자로 된 두 개의 문자열에 대해 다른 값을 반환하지만 여전히 매우 간단합니다.