Посоветуйте хэш-функцию для свертки не длинных массивов байт

[Гурман]

Исходные данные - массивы байт с переменной длиной от 8 Байт и до 256 КБайт. Наиболее частые имеют длину от 16 байт и до 1 КБайт. Более 1 КБайт массивы очень маловероятны. Нужна хэш-функция, которая давала бы свертку длиной 32 разряда, и с максимальной вероятностью несовпадения сверток. Может быть, достаточно будет CRC32? Или даже CRC16? Или может существуют другие хэш-функции для подобных задач?

То есть, задача не проверки "испорченности" данных, а проверки "совпадения", но именно для небольших массивов переменной длины, причем чаще всего довольно коротких.

Кто что посоветует? А то я в хэш-функциях не очень, на CRC и простых сигнатурных свертках мои познания в них заканчиваются.

[OKTA]

Используй SHA и не мучайся выбором) Правда там длина хэша 160 бит в случае с SHA1, но это мелочи.

[Гурман]

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

[xokc]

Если требования именно 32 разрядный хэш, то какие ещё разумные варианты могут быть кроме CRC32?

[OKTA]

CRC32 это ведь не хэш-функция по факту. Она разве гарантирует уникальность данных или другими словами разве она устойчива к коллизиям?

[Igors]

CRC32 это ведь не хэш-функция по факту. Она разве гарантирует уникальность данных или другими словами разве она устойчива к коллизиям?

Уникальность хеш-ключа не требуется, просто "чем уникальнее - тем лучше" (меньше коллизий). С этой точки зрения CRC32 хороший кандидат

[OKTA]

Без уникальности хэша нет смысла в самом хэше  
CRC32 уже выдает одинаковые значения на codding - gnu и exhibiters - schlager. И соответственно на всех производных от этих слов, если к ним справа что-то дописывать  
Если жестких требований к уникальности не ставится, то конечно можно использовать CRC, а в ином случае лучше использовать именно хэш-функции..

P.S. MD5 работает быстрее, чем SHA1. А если надо что-то еще быстрее, то алгоритмов миллион, просто не все стандартизованы.

[Igors]

Без уникальности хэша нет смысла в самом хэше  

Пример: пусть данные int и в данный момент хеш имеет напр 5 bin'ов (корзин). Тогда хеш-ключ вычисляется как остаток от деления на 5. Да, хранящиеся в хеше значения напр 5, 10, 15 окажутся в одной корзине и будут все перебираться (обычно по списку). Это и есть "коллизии". Требование "уникальности" было бы бессмысленным, т.к. время обращения к такому хешу неприемлемо долго.

[Old]

Требование "уникальности" было бы бессмысленным, т.к. время обращения к такому хешу неприемлемо долго.

Это почему?

[Гурман]

Без уникальности хэша нет смысла в самом хэше  
CRC32 уже выдает одинаковые значения на codding - gnu и exhibiters - schlager. И соответственно на всех производных от этих слов, если к ним справа что-то дописывать  
Если жестких требований к уникальности не ставится, то конечно можно использовать CRC, а в ином случае лучше использовать именно хэш-функции..

P.S. MD5 работает быстрее, чем SHA1. А если надо что-то еще быстрее, то алгоритмов миллион, просто не все стандартизованы.

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

[Гурман]

Если требования именно 32 разрядный хэш, то какие ещё разумные варианты могут быть кроме CRC32?

Скажем так - требование: работающий не медленнее, чем CRC32, и желательно не сильно более длинный. Может быть, 64 разряда, если выполнится требование уникальности и работать будет быстро.

[Old]

http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%94%D0%B6%D0%B5%D0%BD%D0%BA%D0%B8%D0%BD%D1%81%D0%B0
http://ru.wikipedia.org/wiki/PJW-32

[Гурман]

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

[xokc]

CRC32 уже выдает одинаковые значения на codding - gnu и exhibiters - schlager. И соответственно на всех производных от этих слов, если к ним справа что-то дописывать  

Не понял - CRC32("codding - gnu") = 0xAD7CEA44, CRC32("exhibiters - schlager") = 0x389AE08C, CRC32("codding - gnu1") = 0xF2C016D4, CRC32("exhibiters - schlager1") = 0x67EABA5C (http://www.codenet.ru/services/crc32/)

64 разряда, если выполнится требование уникальности и работать будет быстро.

И снова не понял, о какой уникальности хэша может идти речь при ограниченной длине ключа. В любом случае для 64 битного ключа количество вариантов его значений = 2^64. То есть для 2^64+1 различных вариантов входных последовательностей будут гарантированно совпадать значения хэшей даже для идеальной в смысле минимизации коллизий функции.
Для гарантированно уникальной хэш функции на неограниченно длинной последовательности нужен неограниченно длинный ключ.

[Гурман]

И снова не понял, о какой уникальности хэша может идти речь при ограниченной длине ключа. В любом случае для 64 битного ключа количество вариантов его значений = 2^64. То есть для 2^64+1 различных вариантов входных последовательностей будут гарантированно совпадать значения хэшей даже для идеальной в смысле минимизации коллизий функции.
Для гарантированно уникальной хэш функции на неограниченно длинной последовательности нужен неограниченно длинный ключ.

В условиях - входная последовательность ограничена. Более того - она короткая. Вот и интересно - существуют ли такие алгоритмы с ключом небольшой конечной длины, у которых вероятность коллизий на коротких данных 0-я, но увеличивается при увеличении длины входной последовательности? То есть, если вход до 256 КБ, то на таких данных коллизии не будет, но если бы этот же алгоритм применить для 1 МБ, то там уже возникают коллизии.

Такие алгоритмы есть? Интуитивно я догадываюсь, что должны быть, но не встречал никогда.