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

Question

Какой был бы лучший алгоритм хеширования, если бы у нас были следующие приоритеты (в таком порядке):

1. Минимальные коллизии хешей
2. Performance

Это не обязательно должно быть безопасно. В основном я пытаюсь создать индекс, основанный на комбинации свойств некоторых объектов. Все свойства являются строками .

Будем благодарны за любые ссылки на реализации c #.

Answer 1

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

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

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

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

Answer 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 году в журнале «Доктор Добб» (в обновленной статье): http://burtleburtle.net/bob/hash/doobs.html

Answer 3

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

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

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

Две проблемы умеренно связаны между собой. Они не идеально соотнесены.

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

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

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

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

Разница огромна. между ними разница в 2389 нулей. Будут коллизии (коллизия - это особый случай, когда два РАЗНЫХ входных файла будут иметь одинаковый хэш), так как мы уменьшаем 10 ^ 2466 случаев до 10 ^ 77 случаев.

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

---

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

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

Удачи;)

Answer 4

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

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

Answer 6

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

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

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

Answer 7

"Murmurhash" довольно хорош как по производительности, так и по коллизиям.

Упомянутый поток на "softwareengineering.stackexchange" имеет несколько тестов, и Murmur выигрывает.

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

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

Answer 8

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

Вот фрагмент из поста:

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

Answer 9

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

Из статьи:

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

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