Какова лучшая хеш-функция на 32 бита для коротких строк (имена тега)?
Какова лучшая хеш-функция на 32 бита для относительно коротких строк?
Строки являются именами тега, которые состоят из английских букв, чисел, пробелов и некоторых дополнительных символов (#, $, ....). Например: Unit testing, C# 2.0.
Я ищу 'лучше всего' как в 'минимальных коллизиях', производительность не важна для моих целей.
4 ответа
Если производительность не важна, просто возьмите безопасный хэш, такой как MD5 или SHA1, и сократите его вывод до 32 бит. Это даст вам распределение хэш-кодов, неотличимое от случайного.
Я не уверен, что это лучший выбор, но вот хеш-функция для строк:
Практика программирования (HASH ТАБЛИЦЫ, стр. 57)
/* hash: compute hash value of string */
unsigned int hash(char *str)
{
unsigned int h;
unsigned char *p;
h = 0;
for (p = (unsigned char*)str; *p != '\0'; p++)
h = MULTIPLIER * h + *p;
return h; // or, h % ARRAY_SIZE;
}
Опытным путем значения 31 и 37 оказались хорошим выбором для множителя в хэш-функции для строк ASCII.
Если пользователи редко добавляют новые теги, вы можете использовать идеальный хеш ( http://en.wikipedia.org/wiki/Perfect_hash_function ) который пересчитывается каждый раз при добавлении нового тега. Конечно, если вы не знаете, какую проблему вы действительно пытаетесь решить, вам нужно только догадываться, что вы можете сделать.
Вы можете проверить murmurhash2. Он быстрый, в том числе для маленьких струн, и имеет хороший финальный шаг микширования, так что он даже хорошо микшируется для очень маленьких струн.