Я обнаружил, что стандартная функция хэширования на VS2005 очень медленна, когда вы пытаетесь добиться высокой производительности. Каковы некоторые хорошие примеры быстрых и эффективных алгоритмов хеширования, которые должны лишить большинство столкновений?
Я работал с Paul Larson из Microsoft Research по некоторым реализациям хэш-таблицы. Он исследовал ряд функций хеширования строк на множестве наборов данных и обнаружил, что простое умножение на 101 и цикл добавления работает на удивление хорошо.
unsigned int
hash(
const char* s,
unsigned int seed = 0)
{
unsigned int hash = seed;
while (*s)
{
hash = hash * 101 + *s++;
}
return hash;
}
Из моего старого кода:
/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;
/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
size_t hash = InitialFNV;
for(size_t i = 0; i < s.length(); i++)
{
hash = hash ^ (s[i]); /* xor the low 8 bits */
hash = hash * FNVMultiple; /* multiply by the magic number */
}
return hash;
}
Быстро. На самом деле очень быстро.
Boost имеет библиотеку boost:: hash, которая может предоставлять некоторые основные хеш-функции для большинства распространенных типов.
Это всегда зависит от вашего набора данных.
Я для одного имел удивительно хорошие результаты, используя CRC32 строки. Работает очень хорошо с широким спектром различных наборов ввода.
Множество хороших реализаций CRC32 легко найти в сети.
Изменить: Почти забыл: на этой странице есть хорошая хеш-функция с номерами производительности и тестовыми данными:
http://smallcode.weblogs.us/ < - далее вниз по странице.
Я использую хэш Jenkins для записи библиотеки фильтров Bloom, у нее отличная производительность.
Подробности и код можно найти здесь: http://burtleburtle.net/bob/c/lookup3.c
Это то, что Perl использует для своей операции хэширования, fwiw.
Если вы хешируете фиксированный набор слов, лучшая хэш-функция часто является идеальной хэш-функцией. Однако они обычно требуют, чтобы набор слов, которые вы пытаетесь использовать хэш, известен во время компиляции. Обнаружение ключевых слов в lexer (и перевод ключевых слов в токены) - это общее использование совершенных хеш-функций, созданных с помощью таких инструментов, как gperf. Идеальный хэш также позволяет вам заменить hash_map на простой массив или vector.
Если вы не хешируете фиксированный набор слов, то, очевидно, это не применяется.
Одно классическое предложение для хеш-строки состоит в том, чтобы переходить через буквы один за другим, добавляя их значения ascii/unicode в аккумулятор, каждый раз умножая аккумулятор на простое число. (разрешая переполнение хэш-значения)
template <> struct myhash{};
template <> struct myhash<string>
{
size_t operator()(string &to_hash) const
{
const char * in = to_hash.c_str();
size_t out=0;
while(NULL != *in)
{
out*= 53; //just a prime number
out+= *in;
++in;
}
return out;
}
};
hash_map<string, int, myhash<string> > my_hash_map;
Трудно получить быстрее, чем это, не выкидывая данные. Если вы знаете, что ваши строки могут быть дифференцированы только несколькими символами, а не всем их содержимым, вы можете делать быстрее.
Вы можете попытаться кэшировать хэш-значение лучше, создав новый подкласс basic_string, который помнит свое значение хэша, если значение слишком часто вычисляется. Однако hash_map должен делать это внутренне.
Я немного искал, и забавно, что появился маленький алгоритм Пола Ларсона http://www.strchr.com/hash_functions как имеющие наименьшие столкновения любого тестируемого в ряде условий, и это очень быстро для одного, которое оно развернуто или управляется таблицей.
Larson является простым умножением на 101 и добавляет цикл выше.
Python 3.4 включает новый алгоритм хеширования, основанный на SipHash. PEP 456 очень информативен.
Если ваши строки в среднем длиннее одной строки кэша, но их длина + префикс достаточно уникальны, подумайте о том, чтобы иметь длину + первые 8/16 символов. (Длина содержится в самом объекте std::string и поэтому дешева для чтения)
MurmurHash получил довольно популярную, по крайней мере, в кругах разработчиков игр, как "общую хэш-функцию".
Его прекрасный выбор, но давайте посмотрим позже, если мы можем в целом добиться большего. Еще один прекрасный выбор, особенно если вы знаете больше о своих данных, чем "его будет неизвестное количество байтов", это сворачивать ваши собственные (например, см. Ответы Won Chuns или Runes modified xxHash/Murmur, которые специализированы для 4-байтных ключей и т.д.). Если вы знаете свои данные, всегда старайтесь выяснить, можно ли использовать эти знания для хорошего эффекта!
Без дополнительной информации я бы рекомендовал MurmurHash в качестве общего назначения некриптографическая хэш-функция. Для небольших строк (размера среднего идентификатора в программах) очень простой и известный djb2 и FNV очень хороши.
Здесь (размеры данных < 10 байт) мы видим, что интеллектуальность ILP других алгоритмов не проявляет себя, и супер-простота FNV или djb2 выигрывает в производительности.
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
hash = FNV_offset_basis
for each byte_of_data to be hashed
hash = hash × FNV_prime
hash = hash XOR byte_of_data
return hash
hash = FNV_offset_basis
for each byte_of_data to be hashed
hash = hash XOR byte_of_data
hash = hash × FNV_prime
return hash
Функции хэширования могут сделать ваш код уязвимым для атак типа "отказ в обслуживании". Если злоумышленник может заставить ваш сервер обрабатывать слишком много коллизий, ваш сервер может не справиться с запросами.
Некоторые хеш-функции, такие как MurmurHash принимают семя, которое вы можете предоставить, чтобы резко уменьшить способность злоумышленников предсказывать хеши, которые генерирует ваше серверное программное обеспечение. Помните об этом.