[swampman 0]

Добрый день.

 

Ситуация следующая: есть данные ~ 20 байт.

Им необходимо поставить в соответствие некоторый хеш-код.

Естественно хочется чтобы он был как можно меньше.

 

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

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

 

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

Изменено 16 декабря, 2010 пользователем vladik

[Гость TSerg]

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

 

вероятность коллизии

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)

[Petr_I 0]

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

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

 

А какова конечная цель?

Оптимизировать поиск по базе данных?

Процессор какой?

Потенциальное количество записей в базе?

 

От этого и будут зависеть рекомендации.

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

 

[DaddyTorque 0]

Ситуация следующая: есть данные ~ 20 байт.

Им необходимо поставить в соответствие некоторый хеш-код.

Естественно хочется чтобы он был как можно меньше.

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

 

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

Ну а коллизии - конечно могут быть... правильно было сказано про парадокс дней рождения.

[Oldring 0]

Им необходимо поставить в соответствие некоторый хеш-код.

Естественно хочется чтобы он был как можно меньше.

 

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

 

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