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

Я работал с Полом Ларсоном из 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 для написания библиотеки фильтров Блума, у нее отличная производительность.

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

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

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

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

От хеш-функций до конца:

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

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

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

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

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

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

Если ваши строки в среднем длиннее одной строки кэша, но их длина + префикс достаточно уникальны, рассмотрите возможность использования только длины + первых 8/16 символов. (Длина содержится в самом объекте std :: string, поэтому ее легко читать)