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

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

  1. Минимальные столкновения с хешем
  2. Представление

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Я использовал 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

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

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

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

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

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

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

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

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

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

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

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


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

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

Удачи 😉

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

Ниже приведена реализация «GNU Classpath». (Лицензия: GPL)

  /** * Computes the hashcode for this String. This is done with int arithmetic, * where ** represents exponentiation, by this formula:
*
s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]. * * @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; }

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

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

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

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

Из статьи:

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

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

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

Вот fragment сообщения:

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

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

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

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

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

  • Как определить, является ли мой расчет pi точным?
  • Написание собственной функции квадратного корня
  • Сложность выполнения таблицы hash-таблицы (вставка, поиск и удаление)
  • Быстрые и простые комбинации hash-кодов
  • Как создавать платы судоку с уникальными решениями
  • Как я могу наилучшим образом угадать кодировку, когда спецификация (знак байтового заказа) отсутствует?
  • Эффективно находите двоичные строки с низким расстоянием Хэмминга в большом наборе
  • Словарь в Swift с Mutable Array как значение работает очень медленно? Как оптимизировать или построить правильно?
  • Простые числа Eratoshenes быстрее последовательны, чем одновременно?
  • Самый быстрый алгоритм проверки прочности
  • Как найти расстояние от широты и долготы двух мест?
  • Давайте будем гением компьютера.