Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Если речь идет о хеш-таблицах, то, по определению, применяемая в такой ситуации хеш-функция должна возвращать готовый индекс в таблице. Включает ли в себя способ вычисления этого индекса вычисление остатка от деления на последнем или на каком-либо промежуточном этапе — детали реализации хэш-функции, а не какое-то "дополнительное" действие.
Не должна.
И в общем случае не может быть никак завязана на размер таблицы.
Динамические хеш таблицы ( метод rehash ) например когда размер таблицы изменяется динамичиски или настраивается для каждого конкретного экземпляра.
Стандарт de-facto: хеш функции возвращают dword т.е. значения от 0-2(32).
y:dword = f(x)
Основное назначение хеш функции: отображение (и кстати необязательно необратимое!) множества значений x в y с максимально возможной энтропией y
для конкретного домена значений x.
Приведенная г. menify хеш функция вполне может быть удачной и создавть близкие к хаотическим значения для например IPv4 адресов.
а зачем нужна энтропия, хаотическое распределение для IP адресов?
IP адреса и так имеют довольно хаотический набор значений (зависит
конечно от типа сети, но последний байт — точно, во всяком случае).
Может еще для IPv6 подойдет, но для IPv4 — значения и так до 2^32-1.
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>>Если речь идет о хеш-таблицах, то, по определению, применяемая в такой ситуации хеш-функция должна возвращать готовый индекс в таблице. Включает ли в себя способ вычисления этого индекса вычисление остатка от деления на последнем или на каком-либо промежуточном этапе — детали реализации хэш-функции, а не какое-то "дополнительное" действие.
CS>Не должна.
CS>И в общем случае не может быть никак завязана на размер таблицы.
CS>Динамические хеш таблицы ( метод rehash ) например когда размер таблицы изменяется динамичиски или настраивается для каждого конкретного экземпляра.
CS>Стандарт de-facto: хеш функции возвращают dword т.е. значения от 0-2(32).
CS>y:dword = f(x)
CS>Основное назначение хеш функции: отображение (и кстати необязательно необратимое!) множества значений x в y с максимально возможной энтропией y CS>для конкретного домена значений x.
CS>Приведенная г. menify хеш функция вполне может быть удачной и создавть близкие к хаотическим значения для например IPv4 адресов.
CS>Вот.
Serge.
Hасколько проще была бы жизнь, если бы она была в исходниках.
Здравствуйте, Sergeem, Вы писали:
S>а зачем нужна энтропия, хаотическое распределение для IP адресов? S>IP адреса и так имеют довольно хаотический набор значений (зависит S>конечно от типа сети, но последний байт — точно, во всяком случае).
Насчет хаотического я бе не был столь оптимистичен...
Для наглядности: карта где цветом закодированы группы IP адресов интернета.
И насчет последнего байта я бы тоже не был столь оптимистичен...
(например зависит от policy конкретного DHCP в конкретной сетке)
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, Sergeem, Вы писали:
S>>а зачем нужна энтропия, хаотическое распределение для IP адресов? S>>IP адреса и так имеют довольно хаотический набор значений (зависит S>>конечно от типа сети, но последний байт — точно, во всяком случае).
CS>Насчет хаотического я бе не был столь оптимистичен...
CS>Для наглядности: карта где цветом закодированы группы IP адресов интернета.
[кусь-кусь]
CS>И насчет последнего байта я бы тоже не был столь оптимистичен... CS>(например зависит от policy конкретного DHCP в конкретной сетке)
Здравствуйте, DSD, Вы писали:
DSD>Если нужно поднять быстродействие, можно и хеш на 1-2 первых байта приклеить в голове дерева. DSD>Но уж точно никак не данную хеш-функцию применять....
Это универсальная хэш-функция, она не учитывает природу.
В этом ее плюс и минус.
Я не спорю, в каждом конкретном случае можно найти более лучший вариант.
Этот вариант — если ты не уверен, или лень думать.
Я сам для хэширования указателей использую — ptr >> 3
Хотя сейчас мне чаще лень думать (эта функция прописана по дефолту).
Здравствуйте, Kubyshev Andrey, Вы писали:
KA>Хаха, я понял что ты хотел сказать ! Это был антипример ! Только все равно от нее пользы никакой Место ты не сократишь а только увеличишь потому что real values надо хранить, или ты хочешь наложить лимит в 64к указателей ? Ну а если у тебя и атк не много элементов , то поиск по 16 битным значения медленне чем по 32 . Что ты этим выигрываешь кроме размера source кода ?
Извени. А ты точно понимаешь, что такое хеш-таблица и зачем она нужна?
... << RSDN@Home 1.0 beta 4 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>А "хеш-функция" 'int32' -> 'int32' ценность модет представлять не более чем юмористическую (предлагаю переместить ветку).
Во-во. Причем все это произностися в учительском тоне. Мол "Убери это сообщение и не позорься."
PS
Однозначно в юмор.
... << RSDN@Home 1.0 beta 4 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Kubyshev Andrey, Вы писали:
KA>да, есть хэши криптографичесие это сюда явно не подходит, есть математический hash которое использоется для поисков, сортировок и прочее. одно из требований к хэшу низкое количество коллизий. Но какие коллизии могут быть если от из 32 бит делает те же самые 32 бита? Ты может не посмотрел на исходник ?
Сортироваок? А можно с этого места по подробнее?
... << RSDN@Home 1.0 beta 4 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
(эта функция прописана по дефолту).
