Re: Посоветовать хэш

От Eugene Grosbein (2:5006/1) к Alex Aka Parasite

Reply-To: eugen@grosbein.pp.ru

29 авг 2009, суббота, в 22:06 KRAT, Alex Aka Parasite написал(а):

 AAP>>> PS: одной из задач сабжа как раз и является дельнейшее

 AAP>>> последующее выпиливание дубликатов с винта, заменяя их либо на

 AAP>>> симлинки, либо на что-нибудь другое в том же духе (например,

 AAP>>> автопереименование путей в базе на показывание на единственный

 AAP>>> файл). Для этого в том числе и нужна "бесколлизийность"

 EG>> Для поиска дубликатов вообще не требуется никакого хеширования.

 EG>> Вся куча линейно сортируется по контенту (логарифимическое время),

 EG>> потом за один проход обнаруживаются все дубли.

 AAP> ...и при следующем же добавленном\модифицированном файле - повторяем

 AAP> операцию?

Зачем? Быстро находим нужное новому файлу место, проверяем - занято

оно или нет, не занято - вставляем (константное время), занято -

индицируем дубликат. Вот тут хеширование поможет, ещё более ускорив поиск

места. Hо без проверки в конце не обойтись в любом случае.

Eugene

--

Как лист увядший падает на душу...

--- slrn/0.9.8.1 (FreeBSD)

 * Origin: Svyaz Service JSC (2:5006/1@fidonet)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким