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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

• Пол Се имеет достойную статью: http://www.azillionmonkeys.com/qed/hash.html

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

Ответ 3

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

Ответ 4

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

Сначала возникают две разные проблемы:

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

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

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

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

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

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

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

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

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

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

Удачи;)

Ответ 5

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

Ниже приведена реализация "GNU Classpath". (Лицензия: 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;
  }

Ответ 6

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

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

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

Ответ 7

Мне нравится Stackoverflow! Чтение этого вопроса заставило меня заглянуть в хеш-функции немного больше, и я нашел Cuckoo Hash.

Из статьи:

Поиск требует проверки только двух местоположения в хеш-таблице, которые берет постоянное время в худшем случае (см. примечание Big O). Это в контрастирует со многими другими хеш-таблицами алгоритмов, которые могут не иметь постоянная наихудшая оценка времени для поиска.

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

Ответ 8

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

Вот фрагмент сообщения:

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