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

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

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

Tue Sep 01 2009 12:58, Alex Mizrahi wrote to Alexander Gusak:

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

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

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

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

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

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

 AM> A perfect hash function _for a set S_ is a hash function that maps

 AM> distinct  elements in S to distinct integers, with no collisions.

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

 AM> известно.

Вовсе неочевидно. Это подразумевает, что известны _некие характеристики_

множества S, достаточные для реализации. Ключевым элементом определения

является другая его часть, "with no collisions".

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

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

Ты пропустил начало. А в начале я предложил заложиться на три порядка от

ожидаемого количества файлов, с тем чтобы зафиксировать одну из характеристик

множества. Так что оно уже не совсем неизвестно. Оно уже не просто счетное,

оно конечное, причем с известными пределами.

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

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

Да, мощность должна быть ограничена.

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

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

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

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

эти предположения, достаточно взять хэш на 81921 бит, нет?

С уважением

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

--- ifmail v.2.15dev5

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

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

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

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