Re: Посоветовать хэш
От Alex Mizrahi (2:5020/400) к Alexander Gusak
В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)
From: "Alex Mizrahi" <udodenko@users.sourceforge.net>
AG>>> Мы же в задаче имеем дело с его опять же конечным, хотя и тоже
AG>>> немалым, подмножеством.
AM>> Каким ещё подмножеством?
AG> Hу как же. Всего различных по содержанию файлов размером до 10К может
AG> быть, грубо говоря, 2^81920. А в задаче может встретиться
AG> сто-двести-триста миллионов из них. Hу или сколько там на килограмм
AG> вещества помещается.
И какое это отношение имеет к хэш-функции?
Если отбросить шелуху про мегасервер на перле, нужно найти такую хэш
функцию, которая будучи применена к двум файлам (определённого размера
и т.д.) даст совпадающие значения тогда и только тогда когда эти
файлы совпадают. Всё.
Подмножество того что лежит в базе данных, грубо говоря, соотносится
с тем сколько раз эту функцию применяют, но не к чему её применяют.
Т.о. состав базы и даже её наличие к функции отношения не имеет.
Hу представь что в базе хэш всего одного файла. Потом нашли какой-то
ещё файл, загнали в базу. Потом нашли ещё один, и проверяют есть
ли он в базе. И что, то что функция применена всего три раза может
как-то помочь избежать коллизии?
Если хэш-функция не является биективной функцией ДЛЯ ИСХОДHОГО МHОЖЕСТВА
(того где 2^81920), то существует большая нуля вероятность коллизии.
AM>> Ты меня извини, но если ты в качестве хэша берёшь сам контент, то это
AM>> нифига уже не хэш, с практической точки зрения (да и под определения
AM>> не попадает).
AG> По определению, perfect hash функция должна отображать множество S на
AG> множество целых чисел. В определении не сказано, что это должны быть
AG> _маленькие_ целые числа :)
В английской википедии приводится такое определение хэш-функции:
A hash function is any well-defined procedure or mathematical function which
converts a large, possibly variable-sized amount of data into a small
datum,
usually a single integer that may serve as an index into an array.
Понятное дело, это не формальное определение, но тем не менее...
--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)
Ответы на это письмо:
From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку
From: Username
Или коротким