Запутался в хешах

Question

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

мой вопрос: если все хеши уникальны, я не смогу сжать что-либо в строку из 40 символов?

Answer 1

Хеширование не уникально.

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

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

И: хеш не должен быть уникальным. Тот же самый вход должен быть преобразован в тот же самый хэш алгоритмом. Вы не используете хеш в качестве идентификатора!

Answer 2

Не все хеши гарантированно являются уникальными. Запись в википедии по теме довольно хорошая: http://en.wikipedia.org/wiki/Hash_function

Answer 3

Один способ думать о хэше - это как отпечаток пальца человека (хеши также иногда называют отпечатками пальцев).

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

Чтобы отменить отпечаток пальца, необходимо сравнить отпечаток с базой данных известных people->finger-prints (если неизвестный отпечаток соответствует Person1, неизвестный отпечаток принадлежит им)

С помощью хэша вы снова должны делать то же самое - у вас есть база данных со всеми отображениями строк-> хэшей (называемая радужная таблица ). Затем вы ищите строку с хешем "a1b2c3", и он показывает, что "abcdef" был хеширован, чтобы получить это. Другой более распространенный способ - просто попробовать каждую комбинацию символов, хешировать их и сравнить (атака грубой силы 1013 *)

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

У меня вопрос: если все хеши уникальны, я не смогу сжать что-либо в строку из 40 символов?

Теоретически хеширование - отличный метод сжатия, но распаковка невероятно непрактична, если не считать, скажем, 10 символов ASCII данных. Вы правы, вы можете сжать что угодно до строки из 40 символов, но вы не можете распаковать ее практически ( даже теоретически это немного натянуто ..)

Answer 4

RSA хеши не являются уникальными. Существует очень крошечный (порядка 1: 36 ^ 40) шанс, что вы создадите ложное срабатывание при хешировании двух разных битов открытого текста. Для большинства приложений вероятность считается достаточно малой, чтобы ее можно было проигнорировать, поскольку в среднем для обнаружения случайного столкновения потребовались бы миллионы лет.

Answer 5

Хеширование для распространения как можно лучше , а не для уникальности!

Конечно, достижение уникальности - это достижение 100% распространения, но это часто невозможно, независимо от того, насколько хорош ваш алгоритм хеширования.

Яркий пример:

C # например, предоставить код Int32 для каждого объекта в виде HashCode ... Так же и для Int64:

       Int64 a = Int64.MaxValue;
       Int32 myHash =  a.GetHashCode();

Вывод: есть 2 ^ 64 различных возможных экземпляров Int64, но только 2 ^ 32 хеш-кода для них !!

Итак: каждое хеш-значение для Int64 используется (в среднем)

4 294 967 295

другие Int64!

Вот тебе и уникальность: -)

Answer 6

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

Answer 7

Подумайте над этим с точки зрения принципа Pigeonhole . Если вы помещаете n предметов в меньшее количество блоков k, то обязательно будет несколько блоков с несколькими элементами. Поэтому, чтобы ответить на ваш вопрос, никакие хэши не являются уникальными.

Answer 8

Я думаю, что это отличное объяснение: http://www.cprogramming.com/tutorial/computersciencetheory/hash-table.html

Answer 9

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

Answer 10

Если вы используете правильно определенную хеш-функцию, вы можете фактически предположить, что результаты хеш-функции уникальны.

Проблема, с вашим вопросом хэш-функция является односторонней. Не существует обратной функции для получения значения и возврата к исходному BLOB-объекту. Если у вас нет огромной таблицы всех возможных исходных значений (так называемая радужная таблица ).