swampman 0 16 декабря, 2010 Опубликовано 16 декабря, 2010 (изменено) · Жалоба Добрый день. Ситуация следующая: есть данные ~ 20 байт. Им необходимо поставить в соответствие некоторый хеш-код. Естественно хочется чтобы он был как можно меньше. Какие есть формулы расчета, чтобы найти компромисс между размером хеша и вероятностью коллизий? Ну и если из опыта что-то подскажете (какой хеш использовали и для каких данных) тоже буду благодарен. P.S. полагаю CRC32 использовать для такого - слишком избыточно :) Изменено 16 декабря, 2010 пользователем vladik Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Гость TSerg 16 декабря, 2010 Опубликовано 16 декабря, 2010 · Жалоба Вкуривать "парадокс дней рождения" вероятность коллизии 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 23 декабря, 2010 Опубликовано 23 декабря, 2010 · Жалоба Какие есть формулы расчета, чтобы найти компромисс между размером хеша и вероятностью коллизий? Ну и если из опыта что-то подскажете (какой хеш использовали и для каких данных) тоже буду благодарен. А какова конечная цель? Оптимизировать поиск по базе данных? Процессор какой? Потенциальное количество записей в базе? От этого и будут зависеть рекомендации. Может достаточно первый байт использовать вместо хэша. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
DaddyTorque 0 21 февраля, 2011 Опубликовано 21 февраля, 2011 · Жалоба Ситуация следующая: есть данные ~ 20 байт. Им необходимо поставить в соответствие некоторый хеш-код. Естественно хочется чтобы он был как можно меньше. P.S. полагаю CRC32 использовать для такого - слишком избыточно :) CRC - не плох, если CRC32 по-вашему слишком жирно, используйте CRC16 или CRC8 или просто нужное количество битов от любого из вышеназванных CRC. Т.к. здесь свойства CRC не важны, а важно только построить какое-нибудь отображение, то можно и более простой алгоритм использовать, например просто XOR-ить фрагменты сообщения (например по 32 бита), а потом, опять же, отрезать достаточное в вашей ситуации кол-во битов. Ну а коллизии - конечно могут быть... правильно было сказано про парадокс дней рождения. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 21 февраля, 2011 Опубликовано 21 февраля, 2011 · Жалоба Им необходимо поставить в соответствие некоторый хеш-код. Естественно хочется чтобы он был как можно меньше. Минимально возможный размер хеш-кода есть 1 бит. Вам пойдет? Можно придумать довольно много удовлетворительных однобитных хеш-кодов. Попробуйте для начала просто проксорить все биты вашей записи. В некоторых случаях работать не будет, но может быть вам повезет. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться