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

От Alexander Gusak (2:5020/175.2) к Alex Mizrahi

From: "Alexander Gusak" <agusak@skengstroy.ru>

Wed Sep 02 2009 01:07, Alex Mizrahi wrote to Alexander Gusak:

 AM> Если отбросить шелуху про мегасервер на перле, нужно найти такую хэш

 AM> функцию, которая будучи применена к двум файлам (определённого размера

 AM>  и т.д.) даст совпадающие значения тогда и только тогда когда эти

 AM>  файлы совпадают. Всё.

 AM> Подмножество того что лежит в базе данных, грубо говоря, соотносится

 AM> с тем сколько раз эту функцию применяют, но не к чему её применяют.

 AM> Т.о. состав базы и даже её наличие к функции отношения не имеет.

Мне не хочется сейчас укапываться в математику, я посмотрел быстренько

http://arxiv.org/pdf/cs/0702159 и решил, что наверно все же имеет значение

(кратко - там люди проверяли алгоритм minimal perfect hash, гоняя его на базе

выборки доменных имен длиной до 64 байт, от 1 миллиона до 1 миллиарда строк,

интересовала их линейность времени вставки/поиска при разных размерах выборки

и, соответственно, ключа - от 13 до 23 бит. Из чего я делаю вывод, что

существуют алгоритмы, для которых размер ключа определяется числом элементов,

а не их разрядностью. Какие - дискутировать не готов).

 AM> Hу представь что в базе хэш всего одного файла. Потом нашли какой-то

 AM> ещё файл, загнали в базу. Потом нашли ещё один, и проверяют есть

 AM> ли он в базе. И что, то что функция применена всего три раза может

 AM> как-то помочь избежать коллизии?

Ээээ. Пример. Если мы знаем точно, что функцию понадобится применить не более

трех раз, то грубо говоря любые три предмета я могу рассортировать один

направо, другой - налево, третий ну скажем в кармашек, моя прелессссть.

 AM> Если хэш-функция не является биективной функцией ДЛЯ ИСХОДHОГО МHОЖЕСТВА

 AM>  (того где 2^81920), то существует большая нуля вероятность коллизии.

Как она вообще может являться биективной, если биективность предполагает

_взаимно_ однозначное отображение, и следовательно _равномощность_ множеств?

perfect hash функция отображает на натуральный ряд, как конечное множество

может быть с ним равномощным? Здесь речь может только об инъекции идти.

 AG>> По определению, perfect hash функция должна отображать множество S на

 AG>> множество целых чисел. В определении не сказано, что это должны быть

 AG>> _маленькие_ целые числа :)

 AM> В английской википедии приводится такое определение хэш-функции:

 AM> A hash function is any well-defined procedure or mathematical function

 AM> which

 AM>  converts a large, possibly variable-sized amount of data into a small

 AM> datum,

 AM>  usually a single integer that may serve as an index into an array.

 AM> Понятное дело, это не формальное определение, но тем не менее...

Hу, в отдельном разделе perfect hash function там сказано неформально

следующее:

A perfect hash function for a set S is a hash function that maps distinct

elements in S to **distinct integers**, with no collisions.

С уважением

Александр Гусак

--- ifmail v.2.15dev5

 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)

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

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

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