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

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

From: "Alex Mizrahi" <udodenko@users.sourceforge.net>

 AG>>> Я тоже не программер, поэтому могу пнуть в сторону вики -

 AG>>> http://en.wikipedia.org/wiki/Perfect_hash_function а там ссылок на

 AM>> Perfect hash строится по наперёд заданному контенту.

 AG> Обоснуй.  Hеочевидно.

Обосновать это очень сложно. Потому что оно выходит прямо из определения.

Ты читал вообще статью по ссылке которую привёл?

A perfect hash function _for a set S_ is a hash function that maps distinct

elements in S to distinct integers, with no collisions.

Хэш-функция ДЛЯ МHОЖЕСТВА S. Очевидно это подразумевает что множество S

известно.

Если оно не известно, то что это будет -- неизвестная хэш-функция для

какого-то неизвестного множества?

Если хэш имеет конечное количество бит, то мощность множества S

ограничена -- например, для 128-битного хэша это будет 2^128

элементов. Если считать что контентом являются произвольные 10-килобайтные

файлы, то мощность множества контента будет

как минимум 2^81920.

Т.о. нужно каким-то образом наперёд выбрать из 2^81920 элементов 2^128

элементов которые могут потенциально

встретиться. Для произвольного контента это, очевидно, невозможно.

 AG> Очевидно же то, что любой конечный контент можно по меньшей мере

 AG> _пересчитать_, и это уже будет perfect hash.

Да. Смысл perfect hash в том чтобы быстро вычислять эту функцию по контенту,

без

пересчёта всех элементов.

--- ifmail v.2.15dev5.4

 * Origin: Demos online service (2:5020/400)

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

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

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