Безопасно ли вырезать хэш?
Я хотел бы хранить хэши для примерно 2 миллиардов строк. Для этой цели я бы хотел использовать как можно меньше памяти.
Рассмотрим идеальный алгоритм хеширования, который возвращает хеш в виде последовательности шестнадцатеричных цифр (например, хеш md5). Насколько я понимаю идею, это означает, что мне нужно, чтобы хэш был не меньше и не более 8 символов в длину. Потому что такой хэш мог бы хэшировать 4 миллиарда (16 * 16 * 16 * 16 * 16 * 16 * 16 * 16) различных строк.
Поэтому я хотел бы знать, безопасно ли сокращать хэш до определенной длины, чтобы сэкономить место? (хэши, конечно, не должны сталкиваться)
Да / Нет / Возможно - я был бы признателен за ответы с объяснениями или ссылками на соответствующие исследования.
PS - я знаю, что могу проверить, будет ли 8-символьный хеш-код в порядке хранить 2 миллиарда строк. Но мне нужно сравнить 2 миллиарда хешей с их 2 миллиардами сокращенных версий. Это не кажется тривиальным для меня, поэтому я лучше спросить, прежде чем я это сделаю.
2 ответа
Хеш - это число, а не строка шестнадцатеричных чисел (символов). В случае MD5 это 128 бит или 16 байтов, сохраненных в эффективной форме. Если ваша проблема по-прежнему имеет место, вы можете рассмотреть возможность усечения числа (путем преобразования в слово или первого сдвига битов). Хорошие алгоритмы хеширования распределяют равномерно по всем битам.
Приложение:
Обычно, когда вы работаете с хешами, вы хотите проверить, действительно ли совпадают строки. Это заботится о возможности столкновения хэшей. Чем больше вы сократите хэш, тем больше столкновений вы получите. Но хорошо спланировать это на этом этапе.
Безопасно ли хранить значения x в хеш-домене, способном представлять только 2x различных хеш-значения, полностью зависит от того, можете ли вы терпеть коллизии.
Хеш-функции - это, по сути, генераторы случайных чисел, поэтому ваши 2 миллиарда вычисленных хеш-значений будут равномерно распределены между 4 миллиардами возможных результатов. Это означает, что вы подвержены проблеме дня рождения.
В вашем случае, если вы вычислите 2^31 (2 миллиарда) хэшей, используя только 2^32 (4 миллиарда) возможных значений хеш-функции, вероятность того, что по крайней мере два будут иметь один и тот же хэш (столкновение), будет очень, очень близка к 100%. (И вероятность того, что три будут одинаковыми, также очень, очень близка к 100%. И т. Д.) Я не могу найти формулу для расчета вероятного числа столкновений на основе этих чисел, но я подозреваю, что это огромное число,
Если в вашем случае коллизии хешей не являются катастрофой (например, в реализации Java HashMap, которая имеет дело со коллизиями, превращая цель хеш-функции в список объектов, которые используют один и тот же хеш-ключ, хотя и за счет снижения производительности), то, возможно, вы можете жить с уверенностью большого количества столкновений. Но если вам нужна уникальность, то вам нужен либо намного, гораздо больший хеш-домен, либо вам нужно назначить каждой записи гарантированный уникальный серийный идентификационный номер, в зависимости от ваших целей.
Наконец, обратите внимание, что Keccak способен генерировать любую желаемую выходную длину, поэтому не имеет смысла тратить ресурсы ЦП на генерацию длинного хеш-результата только для того, чтобы впоследствии его обрезать. Вы должны быть в состоянии указать своей функции Keccak указывать только необходимое вам количество бит. (Также обратите внимание, что изменение длины вывода Keccak не влияет на начальные выходные биты, поэтому результат будет точно таким же, как если бы вы делали ручную побитовую подрезку впоследствии.)