Re^2: Посоветовать алгор итм хэширования
От Alex Aka Parasite (2:5049/164.100) к Serguei E. Leontiev
В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)
Hello Serguei!
18 Aug 09 01:33, Serguei E. Leontiev -> Alex Aka Parasite:
SL> Таким образом, если мы оценим "очень критично" вероятностью 10^-9, то:
SL> - надо, либо проверять, что содержимое файлов уникально, либо
SL> добавлять уникальный идентификатор (например, имя файла);
Имя файла может быть одинаковым (они хранятся в структуре папок (где папки - система заранее вычисляемых числовых параметров, по коим контент и адресуется), имена в разных папках и сами папки на разных уровнях вложенности могут дублироваться, и это не запрещено условиями). Структура папок\имена оных\вообще все дерево контента тоже может меняться (с соответствующим изменением кодинга и ДБ, разумеется). Имхо, привязаться к этому нет возможности.
Hе меняется лишь содержимое файлов (и соответственно их размер). Будучи однажды сгенерированными - они остаются такими навечно до момента удаления. В предыдущей мессаге я предлагал привязаться именно к размеру файла как второму параметру (где первый - хэш).
Хэши нужны для однозначной идентификации контента в файлах во всей структуре папок - без необходимости рекурсивного перебора всего дерева папок через ФС (как оно работает щас - жутко тормозя, скрипя винтами и попердывая от натуги), и соответственно построения нужных репортов на базе найденных соответствий.
Если совсем упростить - задача выглядит так: юзер ввел запрос, он прохэшировался, и система выдала уже имеющиеся точные соответствия файлов с именно этим контентом по папкам (где имена папок и их комбинации как таковые и есть отклик на запрос юзера, и далее и обрабатываются отдельно). Hе спрашивай меня, почему и зачем сделано именно так - это УЖЕ есть, УЖЕ работает, и делано задолго до меня, и сейчас надо лишь проапгрейдить через сабж. Проект за это время весьма и весьма вырос, особенно в плане контента - кой и лопатится скриптами по ФС каждый божий день, скоро дырки на винтах прошлифует уже, прости Господи....:(
SL> - т.к. требований на необратимость не предъявлялось, то подойдёт
SL> любая
SL> достаточно "случайная" функция с результатом размера больше
SL> 254-бит:
SL> * CRC 256;
SL> * ГОСТ Р 34.11-94;
SL> * SHA-256;
SL> * и т.п.
В соседней ветке однозначно предложили SHA512. Что скажешь?
SL> Для перечисленных алгоритмов добавлять длину не требуется, т.к. CRC не
SL> требует выравнивания, а в ГОСТ и SHA она и так добавляется. Hо, при
SL> выборе других алгоритмов, надо проверить нужна ли она.
"Добавлять длину" - имелось ввиду добавочное поле "длина_файла" при хранении хэша, как дополнительная мера предотвращения коллизий. Hапример, в ДБ хранить не строку <hash>, а строку <hash.filesize> через разделитель или без оного.
AAP>> 3. Желательно посоветовать быстрые, "нетяжелые" алгоритмы -
AAP>> работа с контентом идет довольно плотная, в мультиюзер-моде, а
AAP>> перл сам по себе не самый проворный.
SL> Вызов внешних библиотек в perl вроде ещё никто не отменял, так что
SL> рекомендую использовать готовые реализации, у хороших реализаций
SL> производительность будет лучше, чем 50 тактов на байт.
Это понятно, и зависит от конкретной реализации. Я же имел ввиду процесс "в общем и целом" - например, CRC32 весьма и весьма шустрее того же MD5 в данном контексте, среднестатистически. Понятно, что хреновой реализацией можно убить какой угодно алгоритм и процессор, но давай пока такие варианты не рассматривать. :)
bye, Alex.
... Супеp-акция компании "Кока-кола" для экстpемалов: "После каждой седьмой бутылоч
--- GoldED+/W32 1.1.5-041013
* Origin: Обьявление:Внедpю двоемыслие в Вашу голову.Бесплатн (2:5049/164.100)
Ответы на это письмо:
From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку
From: Username
Или коротким