|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Leo Yuriev 2:5020/400 01 Nov 2001 18:27:36
To : Vadim Goncharov
Subject : Оценка yникальности хэша
--------------------------------------------------------------------------------
Wed Oct 31 2001 18:37, Vadim Goncharov wrote to All:
VG> Как пpикинyть по алгоpитмy хэша, насколько yникальные значения бyдет
VG> давать этот хэш (сокpатить количество коллизий), то есть оценить, "этот
VG> алгоpитм плохой, а этот - хоpоший"?
Hу а как :-) ?
Либо хорошенько "обмозговать" алгоритм, либо просто испытать. Hапример
проверить сколько уникальных hash-значений будет выдано на миллион ключей.
Если говорить абстрактно, то хорошая hash-функция должна либо делать
отображение некоторого уникального (или редко повторяющего) свойства объекта
или всего объекта на целые числа(например просто выдать адрес объекта в
памяти). Либо работать как дайджест-функция (digest), в идеале ставя в
зависимость каждый бит digest-результата от каждого бита исходных данных.
В качестве эталонов (к сожалению сравнительно медленных) можно взять полиномы
(CRC32), MD5 или лучше RIPE-MD, RC6-round и т.д.
Если алгоритм плохой, можно постараться его улучшить. Hапример выяснить какие
части (группы бит) ключей наиболее уникальны и дополнительно применить к ним
упрощенную полиномную функцию.
Leo (aka OS)
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Оценка yникальности хэша 