Какие вопросы вы учитываете при разработке хеш-функции?

Я не ищу ссылки на информацию по хешированию.

Я не ищу лучшую в мире хеш-функцию.

Меня интересуют мини-рассказы с описанием

  • Проблемная область, в которой вы работали
  • Характер данных, с которыми вы работали
  • Каков был ваш мыслительный процесс при разработке хеш-функции для ваших данных.
  • Как вы были довольны своим результатом.
  • Что вы узнали из опыта, что может быть полезно для других.
Что такое компоненты React? Введение в компоненты | Типы компонентов
Что такое компоненты React? Введение в компоненты | Типы компонентов
Компонент - это независимый, многократно используемый фрагмент кода, который делит пользовательский интерфейс на более мелкие части. Например, если мы...
1
0
446
6
Перейти к ответу Данный вопрос помечен как решенный

Ответы 6

Первый вопрос, который я рассматриваю, это то, соответствует ли установленный алгоритм моим требованиям.

Некоторые вопросы, которые могут помочь определить пригодность: допустимы ли столкновения? Должен ли хеш быть обратимым? Должен ли хэш быть непрерывным?

Jason Hernandez 12.11.2008 10:00

Я повторю то, что сказал Адам: не изобретайте колесо перемешивания

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

Ответ принят как подходящий

Занимаюсь разработкой хранилища данных. У нас было измерение с примерно 9000 строками. Запросы, которые разрабатывались, включали в себя действительно некрасивые запросы.

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

Промежуточный результат на Python выглядел так

{ 
    ( (col1, col2), (col3, col4) ) : [ aRow, anotherRow, row3, ... ],
    ( (col1, col2), (col3, col4) ) : [ row1, row2, row3. row4, ... ],
}

Технически это перевернутый индекс.

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

По сути, алгоритм хеширования - это встроенный в Python хеш. Однако выбор ключей не был очевидным или простым.

Первое, о чем я думаю, - это лучшее место для steal, алгоритма хеширования и его кода. Если и только если я не нахожу подходящего алгоритма, я использую его как отправную точку для создания своего собственного. Честно говоря, я работаю в этой отрасли 7 лет, и никогда создал свой собственный алгоритм хеширования еще со времен колледжа. Но если бы я действительно создал свой собственный алгоритм, минимизация коллизий должна была бы стать самой важной вещью, о которой нужно подумать. Каковы ваши вероятные ценности? Точно ли эта функция распределяет эти значения, чтобы можно было надеяться, что между результирующим значением и исходным значением существует взаимно однозначная связь. У полученных значений действительно хорошо разошлись. Значит, у всех нет общих факторов? Это может вызвать коллизии, когда вы выполняете операции с модулями, чтобы уменьшить значение и уместить его в индексированную коллекцию.

Изобрести алгоритм хеширования легко. Изобретать алгоритмы хеширования работающий, эффективный и эффективный нет.

Вы должны спросить себя:

  1. Мне вообще нужен хеш?
  2. Предполагая, что я реализую стандартный рецепт поваренной книги (например, эффективную Java), включая требования, связанные с все (например, если a.equals (b), то a.hashCode () == b.hashCode ())

Если у вас есть два экземпляра объекта, которые необходимо сравнить на равенство, вам, вероятно, потребуется предоставить реализацию для equals ().

Если у вас есть несколько экземпляров объекта, которые необходимо отсортировать, вам, вероятно, потребуется предоставить реализацию для compareTo ().

Если у вас есть настраиваемый объект, используемый в качестве ключа карты, вам, вероятно, потребуется предоставить реализацию hashCode ().

Не совсем мой опыт, но некоторые из условий, которые вы должны учитывать:

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

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

  3. Функция хеширования должна быть быстрой. Не делайте его немного медленнее / сложнее, если полученный хеш не даст существенно лучшего распределения значений. Так что хеши числовых типов всегда лучше (согласен, что большинство фреймворков имеют хэши целочисленных типов, просто говоря).

  4. Хэши должны иметь хорошее распределение, чтобы шансы коллизии были очень меньше. Следовательно, XOR - плохой выбор. Другими словами, ключ к успеху - найти хороший баланс между скоростью и распределением.. Скорее всего, будет более медленный хэш, если распределение будет лучше.

  5. Напишите функцию, зная, какого размера будет ваш результат. Если это int32, убедитесь, что переполнения не произойдет.

  6. Функция хеширования никогда не должна выдавать ошибку (кроме допустимой нулевой ссылки). Основным виновником будет целочисленное переполнение. Справиться.

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

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

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

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

Это то, что у меня с головы до ног. См. Блог Эрика дополнительно.

Другие вопросы по теме