хорошая хэш-функция

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». Это довольно популярно благодаря своей простоте, скорости и приличному распределению с English строковые данные.

Ваш комментарий замечает, что он фактически умножается на 31, что показалось вам произвольным, и фактически - немного произвольно. Apache Portable Runtime has a comment in their hash algorithm source, который отмечает, что многие возможные константы хорошо работают (33 являются наиболее распространенными). Все они нечетны и близки к мощности 2, что означает, что они хорошо переносятся на смены и сложение или вычитание.

Некоторые другие ресурсы, чтобы помочь понять хэширования:

• Bob Jenkins' A Hash Function for Hash Tables
• Eternally Confuzzled: The Art of Hashing

Answer 2

Здесь представлена ​​лекция о хэш-функциях с представлениями 65 тыс. Точек. На youtube: http://www.youtube.com/watch?v=KW0UvOW0XIo

Это не то, о чем вы просите, однако ваши вопросы показывают, что ваши знания в хешировании ограничены. Лучше прочитать учебник или проверить презентацию.