좋은 해시 함수

Question

해시 함수의 디자인을 이해하지 못했습니다. 나는 예를 겪고 있었다. 함수 주석에서 볼 수 있듯이 곱셈 할 숫자로 31을 선택해야하는 이유는 무엇입니까? 어떻게 결정합니까? 뭔가 무작위인가요, 아니면 무언가를 의미합니까?

unsigned int hash(hash_table_t *hashtable, char *str) 
{ 
    unsigned int hashval; 

    /* we start our hash out at 0 */ 
    hashval = 0; 

    /* for each character, we multiply the old hash by 31 and add the current 
    * character. Remember that shifting a number left is equivalent to 
    * multiplying it by 2 raised to the number of places shifted. So we 
    * are in effect multiplying hashval by 32 and then subtracting hashval. 
    * Why do we do this? Because shifting and subtraction are much more 
    * efficient operations than multiplication. 
    */ 
    for(; *str != '\0'; str++) hashval = *str + (hashval << 5) - hashval; 

    /* we then return the hash value mod the hashtable size so that it will 
    * fit into the necessary range 
    */ 
    return hashval % hashtable->size; 
} 

Answer 1

해시는 번스타인 해시, 토렉 해시 또는 간단히 "시간 33"해시라고합니다. 그것은 간명, 속도 및 알맞은 배급 때문에 꽤 대중적입니다 영어 문자열 데이터.

귀하의 의견은 실제적으로 31을 곱한 것이며 귀하에게 임의적 인 것으로 보입니다. 실제로는 은 임의로 약간입니다. Apache Portable Runtime has a comment in their hash algorithm source은 가능한 많은 상수가 잘 작동한다고 설명합니다 (33 가지가 가장 일반적 임). 그들은 모두 이상하고 2의 거듭 제곱에 가깝다. 즉 교대와 덧셈 또는 뺄셈으로 잘 번역된다.

일부 다른 자원

는 해싱을 이해하는 데 도움이 :

• Bob Jenkins' A Hash Function for Hash Tables
슈타인 해시, Torek 해시, 또는 단순히 "시간 33 해시"로 알려진
• Eternally Confuzzled: The Art of Hashing

Answer 2

다음은 65k 개의보기가있는 해시 함수에 대한 강의입니다. On youtube : http://www.youtube.com/watch?v=KW0UvOW0XIo

이것은 정확히 사용자가 요구하는 것이 아니지만 귀하의 질문에 해싱 지식에 한계가 있음을 알 수 있습니다. 튜토리얼을 읽거나 프리젠 테이션을 확인하는 것이 좋습니다.