Gate 0 26 марта, 2015 Опубликовано 26 марта, 2015 · Жалоба Подскажите pls hash-функцию, которая занимала бы мало места и была бы достаточно быстрой. Задача выглядит следующим образом: есть пакеты данных, которые идентифицируются короткими (4-32 символа длиной) строками ascii. Всего строк может быть несколько тысяч. Хочется сделать такую схему: строка -> hash покороче -> CAM-память -> ... Хэш нужен покороче, чтобы не увеличивать САМ-память, 24 бита было бы хорошо. Первое, что пришло в голову, это сделать хэш вида {5-бит длина строки, 16-бит CRC} или просто вычислять CRC от строки с добавленным в конце байтом длины. Но у меня есть подозрение, что у разных строк CRC будет иногда совпадать, не для хэша он заточен. Может ли уважаемый all порекомендовать что-либо? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Alex77 4 26 марта, 2015 Опубликовано 26 марта, 2015 · Жалоба Подскажите pls hash-функцию, которая занимала бы мало места и была бы достаточно быстрой. Задача выглядит следующим образом: есть пакеты данных, которые идентифицируются короткими (4-32 символа длиной) строками ascii. Всего строк может быть несколько тысяч. Хочется сделать такую схему: строка -> hash покороче -> CAM-память -> ... Хэш нужен покороче, чтобы не увеличивать САМ-память, 24 бита было бы хорошо. Первое, что пришло в голову, это сделать хэш вида {5-бит длина строки, 16-бит CRC} или просто вычислять CRC от строки с добавленным в конце байтом длины. Но у меня есть подозрение, что у разных строк CRC будет иногда совпадать, не для хэша он заточен. Может ли уважаемый all порекомендовать что-либо? В общем случае если разрядность входного сообщения > разрядности хэша - то "CRC будет иногда совпадать" полюбому. Вот "алгоритм архиватора" однозначно "отображается", но длина "хэша" зависит от входного сообщения. Как то вот так... PS: Сорри если что... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
yes 5 26 марта, 2015 Опубликовано 26 марта, 2015 · Жалоба нужен алгоритм, который из регулярных данных генерит шум - так ведь? тогда хэш будет равномерно заполнять свое пространство с минимумом совпадений проверенные алгоритмы такого типа - это криптование, тот же DES или кусок от него. ну и классические хэш функции - от биткоинов, например, тоже Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Gate 0 26 марта, 2015 Опубликовано 26 марта, 2015 · Жалоба тот же DES или кусок от него. ну и классические хэш функции - от биткоинов, например, тоже Не подходит - велик в реализации, большая разрядность результата. У биткойна, насколько я помню, используется sha256(sha256(data)). Чего-нибудь бы попроще... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Mc_off 0 26 марта, 2015 Опубликовано 26 марта, 2015 · Жалоба Делайте CRC с полиномом нужной Вам длины... правило выбора полинома (эвристические) можно найти на просторах интернета... Совпадать для разных строк может и хеш. Причем, если символы в строках появляются с равномерным законом распределения, то не важно как вычисляется хеш... При вычислении CRC, кстати вполне неплохая перемешиваемость получается. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
