Комбинация хэш-функций - есть ли значительное снижение риска столкновения? - PullRequest
Новая
       45

Комбинация хэш-функций - есть ли значительное снижение риска столкновения?

2 голосов
/ 24 августа 2009

Кто-нибудь знает, есть ли реальная выгода в уменьшении вероятности столкновения путем объединения хеш-функций? Мне особенно нужно знать это относительно 32-битного хеширования, а именно, комбинируя Adler32 и CRC32. В основном, adler32 (crc32 (данные)) даст меньшую вероятность столкновения, чем crc32 (данные)? Последний комментарий здесь дает некоторые результаты испытаний в пользу объединения, но источник не упоминается. Для моей цели столкновение не является критичным (то есть задача не связана с безопасностью), но я все равно предпочел бы минимизировать вероятность, если это возможно. PS: я только начинаю в чудесном мире хэширования, много читаю об этом. Извините, если я задал глупый вопрос, я еще даже не приобрел надлежащий "диалект хеша", вероятно, мои поиски в Google по этому поводу также были плохо сформированы. Спасибо.

1 Ответ

6 голосов
/ 24 августа 2009

Не имеет смысла объединять их в такие серии. Вы хэшируете одно 32-битное пространство в другое 32-битное пространство.

В случае столкновения crc32 на первом шаге конечный результат все еще остается столкновением. Затем вы добавляете любые потенциальные коллизии на шаге adler32. Так что лучше не может быть, а может быть только таким же или хуже.

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

adler32 (данные) << 32 | crc32 (данные) </p>

Есть ли значительная выгода от этого, я не уверен.

Обратите внимание, что исходный комментарий, на который вы ссылались, хешировался независимо:

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

Конечно, это означает, что хранить в два раза много информации, которая является частью ваша оригинальная проблема. Тем не менее, есть это способ хранения обоих наборов хэша данные такие, что это требует минимального память (10 КБ или около того), давая почти такая же производительность поиска (15 микросек / поиск по сравнению с 5 microsecs) как хэши Perl.

...