Какой наилучший алгоритм хеширования использовать для строки stl при использовании hash_map?

Question

Я обнаружил, что стандартная функция хеширования на VS2005 мучительно медленна при попытке добиться высокой производительности. Каковы хорошие примеры быстрых и эффективных алгоритмов хеширования, которые должны устранять большинство коллизий?

Answer 1

Я работал с Полом Ларсоном из 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;
}

Answer 2

Из моего старого кода:

/* 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;
}

Это быстро. Действительно чертовски быстро.

Answer 3

Boost имеет библиотеку boost :: hash , которая может предоставить некоторые базовые хэш-функции для большинства распространенных типов.

Answer 4

Это всегда зависит от вашего набора данных.

Я, например, получил удивительно хорошие результаты, используя CRC32 строки. Очень хорошо работает с широким спектром различных входных наборов.

Множество хороших реализаций CRC32 легко найти в сети.

Редактировать: Почти забыл: на этой странице есть хороший список хэш-функций с номерами производительности и тестовыми данными:

http://smallcode.weblogs.us/ <- далее вниз по странице. </p>

Answer 5

Если вы хэшируете фиксированный набор слов, лучшей хеш-функцией часто является совершенная хеш-функция . Однако они обычно требуют, чтобы набор слов, которые вы пытаетесь хэшировать, был известен во время компиляции. Обнаружение ключевых слов в лексере (и перевод ключевых слов в токены) - это обычное использование совершенных хеш-функций, созданных с помощью таких инструментов, как gperf . Идеальный хэш также позволяет заменить hash_map на простой массив или vector.

Если вы не хэшируете фиксированный набор слов, то, очевидно, это не относится.

Answer 6

Я использовал хеш Дженкинса для написания библиотеки фильтров Bloom, у нее отличная производительность.

Подробности и код доступны здесь: http://burtleburtle.net/bob/c/lookup3.c

Это то, что Perl использует для своей операции хеширования, fwiw.

Answer 7

Python 3.4 включает новый алгоритм хэширования, основанный на SipHash . PEP 456 очень информативно.

Answer 8

Я немного искал, и забавно, здесь появился маленький алгоритм Пола Ларсона http://www.strchr.com/hash_functions как имеющий наименьшее количество столкновений из всех протестированных в ряде условий, и очень быстро для тех, которые развернуты или управляются таблицами.

Ларсон - это просто умножить на 101 и добавить цикл выше.

Answer 9

Одно из классических предложений для строкового хэша состоит в том, чтобы последовательно пролистывать буквы, добавляя их значения 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 должен делать это внутренне, хотя.

Answer 10

С Функции хеширования до конца :

MurmurHash стал довольно популярным, по крайней мере в кругах разработчиков игр, как «общая хэш-функция».

Это хороший выбор, но давайте посмотрим позже, сможем ли мы в целом добиться большего успеха. Другой хороший выбор, особенно если вы знаете больше о своих данных, чем «это будет неизвестное количество байтов», - это бросить свои собственные (например, см. Ответы Вон Чуна или модифицированный xxHash / Murmur Руны, который специализируется на 4-байтовых ключах). так далее.). Если вы знаете свои данные, всегда пытайтесь понять, можно ли использовать эти знания для достижения хорошего эффекта!

Без дополнительной информации я бы порекомендовал MurmurHash в качестве общего назначения некриптографическая хеш-функция . Для небольших строк (размером среднего идентификатора в программах) очень хороши очень простые и известные djb2 и FNV .

Здесь (размеры данных <10 байтов) мы можем видеть, что интеллектуальность ILP других алгоритмов не дает себя проявить, и супер-простота FNV или djb2 выигрывает в производительности. </p>

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

ФНП-1

hash = FNV_offset_basis
for each byte_of_data to be hashed
     hash = hash × FNV_prime
     hash = hash XOR byte_of_data
return hash

FNV-1A

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 , принимают начальное число, которое вы можете предоставить, чтобы значительно снизить способность злоумышленников прогнозировать хэши, которые генерирует ваше серверное программное обеспечение. Имейте это в виду.