Хэш-код против SHA-1

Question

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

Вопрос в том, что было бы лучше всего?(компромисс между производительностью и коллизиями...).

С одной стороны, у меня есть обычная функция hashCode, основанная на значениях различных полей (согласно главе 3 книги). эффективная Java.Но я не в состоянии оценить потенциальные коллизии, которые повлечет за собой такой подход.

С другой стороны, у меня есть подход MessageDigest из стандартного дистрибутива Java с алгоритмом SHA-1.Я предполагаю, что это не будет эффективно, но у меня может быть меньше столкновений.Я прав ?Это правильное решение в моем контексте или я совершенно неправ?

Дело в том, что я не знаю, какого размера будут объекты.Также обратите внимание, что вычисленное значение не будет использоваться в HashTable.

спасибо...

Answer 1

См. следующее:

• http://www.javapractices.com/topic/TopicAction.do?Id=28
• https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--
• http://www.ibm.com/developerworks/java/library/j-jtp05273.html

Имейте в виду следующее:

• Объект может быть неравным, но иметь одинаковый хеш-код.
• Потенциал ваших столкновений зависит от того, сколько объектов вы встретите.
• Насколько полезными будут хэш-коды, зависит от того, как вы реализуете проверку.

Как правило, вы можете определить вероятность столкновения на основе количества ожидаемых объектов и количества возможных хэшей (максимальное значение хеш-функции).Видеть http://en.wikipedia.org/wiki/Birthday_paradox за подробное объяснение.

Лично?Объекты Java (экземплярные классы) <10 000?Хэш-код.Представление файлов/блобов/много данных?ША-1.Я использую хеширование SHA-1 в своей базе данных, чтобы люди не могли выполнять ETL-работу с одним и тем же файлом более одного раза.Затем я снова использую хеширование SHA-1 на втором уровне, чтобы люди не могли использовать ETL для одного и того же раздела более чем в одном файле (например, разные файлы, но один и тот же порядок отображается дважды).

Answer 2

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

Answer 3

Из-за проблема с днем ​​рождения, вероятность столкновения зависит от того, со сколькими предметами вы работаете.

160-битное пространство SHA-1 настолько велико, что я сомневаюсь, что у вас когда-либо будет достаточно элементов, чтобы увидеть столкновение.

32-битное пространство hashCode() не должно быть значительного количества коллизий, пока у вас не будет более 50 000 элементов.Однако это зависит от использования хорошего алгоритма хеширования.

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

Answer 4

Обычно для обнаружения дубликатов файлов/данных MD5 является хорошим компромиссом между скоростью и вероятностью коллизий.MD5 не подходит, если кто-то может намеренно создавать файлы, чтобы обмануть вашу программу (он немного уязвим для атак коллизий).Но если вас просто беспокоят случайные коллизии, то его 128-битной ширины в настоящее время практически всегда достаточно.

SHA-1 и SHA-256 дают некоторую защиту от преднамеренных коллизионных атак (теоретические, но практические атаки с использованием SHA-1 неизвестны;для шифрования данных редко стоит выходить за рамки ширины хеш-кода в 160 бит).SHA-1 примерно вдвое медленнее MD5.

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

Если вам действительно нужно что-то более быстрое и вы имеете дело всего с несколькими миллионами элементов данных, то вам стоит рассмотреть еще один вариант — 64-битный алгоритм хэширования, предложенный авторами Numerical Recipes.

Стандартная реализация hashCode() в Java (скажем, String), вероятно, не подходит:Помимо каких-либо проблем с качеством хеша, его 32-битная ширина означает, что коллизию можно ожидать всего после 16 000 элементов или около того.

Answer 5

Я поддерживаю высказывание Мэтта Би: «Не оптимизируйте, пока вам не понадобится оптимизировать».

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

Поскольку обычно они представляют собой односторонние функции, призванные сильно реагировать даже на очень небольшие изменения во входных данных, у вас определенно меньше шансов получить коллизии с MD5 или SHA-1.