Лучший алгоритм хеширования с точки зрения хеш-коллизий и производительности для строк

Не существует единого оптимального алгоритма хеширования. Если у вас есть известный входной домен, вы можете использовать генератор идеального хеширования, такой как gperf, для генерации алгоритма хеширования, который получит 100% скорость для этого конкретного входного набора. В противном случае на этот вопрос нет «правильного» ответа.

Вы можете получить и то, и другое, используя хеш-функцию Knuth описано здесь.

Это очень быстро, если предположить, что размер хэш-таблицы равен степени двойки - всего одно умножение, один сдвиг и одно битовое и. Что еще более важно (для вас), он отлично справляется с минимизацией столкновений (см. этот анализ).

Некоторые другие хорошие алгоритмы описаны здесь.

Простой hashCode, используемый Java-классом String, может показать подходящий алгоритм.

Ниже представлена ​​реализация «пути к классам GNU». (Лицензия: GPL)

  /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

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

Тем не менее, вот несколько указателей:

• Поскольку элементы, которые вы используете в качестве входных данных для хэша, представляют собой просто набор строк, вы можете просто комбинировать хэш-коды для каждой из этих отдельных строк. Я видел следующий псевдокод, предложенный для этого, но не знаю ни о каком конкретном анализе:

  int hashCode = 0;
  
  foreach (string s in propertiesToHash) {
      hashCode = 31*hashCode + s.GetHashCode();
  }
  

  Согласно эта статья, System.Web имеет внутренний метод, который объединяет хэш-коды, используя

  combinedHash = ((combinedHash << 5) + combinedHash) ^ nextObj.GetHashCode();
  

  Я также видел код, который просто объединяет хэш-коды вместе, но мне это кажется плохой идеей (хотя у меня снова нет анализа, подтверждающего это). По крайней мере, вы столкнетесь с конфликтом, если одни и те же строки хешируются в другом порядке.

• Я использовал FNV для хорошего эффекта: http://www.isthe.com/chongo/tech/comp/fnv/

• У Пола Хси есть достойная статья: http://www.azillionmonkeys.com/qed/hash.html

• Еще одна интересная статья Боба Дженкинса, которая была первоначально опубликована в 1997 году в журнале Doctor Dobb's Journal (в связанной статье есть обновления): http://burtleburtle.net/bob/hash/doobs.html

Вот Кукушка Хэш.

Lookup requires inspection of just two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant worst-case bound on the time to do a lookup.

Думаю, это соответствует вашим критериям коллизий и производительности. Похоже, что компромисс заключается в том, что этот тип хеш-таблицы может быть заполнен только на 49%.

Я собираюсь быть здесь неубедительным и дам более теоретический ответ, а не точный ответ, но, пожалуйста, примите в нем ценность.

Во-первых, есть две отдельные проблемы:

а. Вероятность столкновения б. Производительность хеширования (т.е. время, количество циклов процессора и т. д.)

Две проблемы мягко связаны. Они не совсем коррелированы.

Проблема a связана с разницей между хеши и полученными хеш-пространствами. Когда вы хешируете файл размером 1 КБ (1024 байта) и хэш имеет 32 байта, будет:

1,0907481356194159294629842447338e + 2466 (т.е. число с 2466 нулями) возможные комбинации входных файлов

и хеш-пространство будет иметь

1,1579208923731619542357098500869e + 77 (т.е. число с 77 нулями)

Разница ОГРОМНАЯ. разница между ними составляет 2389 нулей. БУДУТ КОЛЛИЗИИ (коллизия - это особый случай, когда два РАЗНЫХ входных файла будут иметь одинаковый хэш), поскольку мы сокращаем 10 ^ 2466 случаев до 10 ^ 77 случаев.

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

Вторая проблема - производительность. Это касается только алгоритма хеширования. Конечно, более длинный хэш, скорее всего, потребует большего количества циклов процессора, но более умный алгоритм может и не сделать. У меня нет четкого ответа на этот вопрос. Это слишком сложно.

Однако вы можете тестировать / измерять различные реализации хеширования и делать из этого предварительные выводы.

Удачи ;)

Забудьте про термин «лучший». Независимо от того, какой алгоритм хеширования может придумать кто-либо, если у вас нет очень ограниченного набора данных, которые необходимо хешировать, каждый алгоритм, который в среднем работает очень хорошо, может стать совершенно бесполезным, если его использовать только правильно (или с вашей точки зрения). "неправильные данные.

Вместо того, чтобы тратить слишком много времени на размышления о том, как сделать хэш более свободным от коллизий, не используя слишком много времени процессора, я бы предпочел начать думать о том, «Как сделать коллизии менее проблематичными». Например. если каждое ведро хеширования на самом деле является таблицей и все строки в этой таблице (которые имели коллизию) отсортированы в алфавитном порядке, вы можете выполнять поиск в таблице корзин, используя двоичный поиск (что составляет всего лишь O (log n)), а это означает, что даже когда каждое второе ведро хеширования имеет 4 коллизии, ваш код по-прежнему будет иметь приличную производительность (он будет немного медленнее по сравнению с таблицей без коллизий, но не настолько). Одним из больших преимуществ здесь является то, что если ваша таблица достаточно велика, а ваш хеш не слишком прост, две строки, приводящие к одному и тому же хеш-значению, обычно будут выглядеть совершенно по-разному (следовательно, двоичный поиск может перестать сравнивать строки после, может быть, одного или двух символов в среднем. ; делая каждое сравнение очень быстрым).

На самом деле у меня раньше была ситуация, когда поиск непосредственно в отсортированной таблице с использованием двоичного поиска оказался быстрее, чем хеширование! Несмотря на то, что мой алгоритм хеширования был прост, на хеширование значений ушло довольно много времени. Тестирование производительности показало, что только если я получаю более 700-800 записей, хеширование действительно быстрее, чем бинарный поиск. Однако, поскольку таблица никогда не могла вырасти больше 256 записей, а средняя таблица была меньше 10 записей, бенчмаркинг ясно показал, что на каждой системе, на каждом процессоре двоичный поиск был быстрее. Здесь тот факт, что обычно уже сравнения первого байта данных было достаточно, чтобы привести к следующей итерации bsearch (поскольку данные уже сильно различались в первом или двух байтах), оказался большим преимуществом.

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

Вот простой способ реализовать это самостоятельно: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Вот отрывок из сообщения:

если, скажем, у нас есть набор символов заглавных английских букв, то длина набора символов равна 26, где A может быть представлено числом 0, B числом 1, C числом 2 и так далее до Z числом 25. Теперь, когда мы хотим сопоставить строку этого набора символов с уникальным числом, мы выполняем то же преобразование, что и в случае двоичного формата.

«Мурмурхаш» хорош как по производительности, так и по коллизиям.

В упомянутой ветке на «softwareengineering.stackexchange» есть несколько тестов, и Мурмур побеждает.

Я написал свой собственный порт MurmurHash 2 с C# на .NET и протестировал его на списке из 466 тыс. Английских слов, обнаружив 22 коллизии.

Результаты и реализация здесь: https://github.com/jitbit/MurmurHash.net (отказ от ответственности, я участвую в этом проекте с открытым исходным кодом!)