Добрый день.

Ситуация следующая: есть данные ~ 20 байт.
Им необходимо поставить в соответствие некоторый хеш-код.
Естественно хочется чтобы он был как можно меньше.

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

P.S. полагаю CRC32 использовать для такого - слишком избыточно

Сообщение отредактировал vladik - Dec 16 2010, 10:23

Вкуривать "парадокс дней рождения"

вероятность коллизии
p <= 0.5*n*(n-1)*2^-m

n - число уникальных слов
m - разрядность hash-функции

Т.е. вероятность коллизии для двух слов равна 1/2^32
А вот сколько реально у вас слов (размер входного множества) - знаете только Вы.

Если опять непонятно, то..
Если размер вашего словаря 2^160 слов, т.е. используются все комбинации из 160 бит ( 20*8), то сами подумайте насчет вероятности

Ну и уж совсем просто:
Если есть n-разрядное двоичное число и число используемых комбинаций максимально и есть хеш-функция разрядностью m, то вероятность коллизии

p <= 2^(2*n-m)

А какова конечная цель?
Оптимизировать поиск по базе данных?
Процессор какой?
Потенциальное количество записей в базе?

От этого и будут зависеть рекомендации.
Может достаточно первый байт использовать вместо хэша.

CRC - не плох, если CRC32 по-вашему слишком жирно, используйте CRC16 или CRC8 или просто нужное количество битов от любого из вышеназванных CRC. Т.к. здесь свойства CRC не важны, а важно только построить какое-нибудь отображение, то можно и более простой алгоритм использовать, например просто XOR-ить фрагменты сообщения (например по 32 бита), а потом, опять же, отрезать достаточное в вашей ситуации кол-во битов.
Ну а коллизии - конечно могут быть... правильно было сказано про парадокс дней рождения.

Минимально возможный размер хеш-кода есть 1 бит. Вам пойдет?

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