Дает очень хорошое распределение на всем интервале 32-ух битных чисел (на 64-ех — не тестировал )
Зачем оно надо?
Для хэширования IP адресов, UID-ов, указателей на память и мало ли чего еще.
Здравствуйте, Ерусов Дмитрий, Вы писали:
ЕД>Ты вообще в курсе что такое хеш ЕД>и зачем он нужен? ЕД>И какие требования предъявлются к хеш-функции?
да, есть хэши криптографичесие это сюда явно не подходит, есть математический hash которое использоется для поисков, сортировок и прочее. одно из требований к хэшу низкое количество коллизий. Но какие коллизии могут быть если от из 32 бит делает те же самые 32 бита? Ты может не посмотрел на исходник ?
Здравствуйте, Ерусов Дмитрий, Вы писали:
ЕД>Ты вообще в курсе что такое хеш ЕД>и зачем он нужен? ЕД>И какие требования предъявлются к хеш-функции?
Да вроде в курсе мы
Я еще понимаю такие хеш-функции как "string->int" и им подобные, когда нужно получить соответствие между различными по мощности множествами. На "unsigned int->int" еще можно согласиться, но "int->int" Зачем воду в ступе толочь? Или я какой глубокий смысл в этом не заметил?
Здравствуйте, Ерусов Дмитрий, Вы писали:
ЕД>Но одно из требований хеша это невозможность ЕД>обратного преоразования.
ЕД>Может быть этот исходник это и дает для инт'ов.
Лады. Если использовать в таком контексте, то с этим можно согласиться.
3:0 в вашу пользу
Здравствуйте, Ерусов Дмитрий, Вы писали:
ЕД>Зачем воду в ступе толочь?
ЕД>Именно из этого я исхожу что не заметили мы глубокий смысл в этом ЕД>Хотя может я и ошибаюсь.
ЕД>Но одно из требований хеша это невозможность ЕД>обратного преоразования.
Для криптографического хэша эта функция не пойдет по причине малой разрядности.
Простым пребором из парадокса близнецов значение data для 32 битного int найдется за sqrt(2^32) = 2^16,
для 64 — битного за sqrt(2^64) = 2^32 итераций с вероятностью 0.5.
Рассчет 2^32 итераций займмет примерно 3 минуты на p3 700Mhz.
перебором можно любой хэш "взломать"
вопрос только во времени, особенно если знаешь что это хеш инта(то есть 4 байт)
у меня речь о другом, что ты не можешь решить обратной задачи
из хэша получить число(не перебором)
хотя если честно то хрен его знает зачем шифровать 4 байтовые числа по одиночке
но автор пишет про быстрый алгоритм
то есть можно подумать что таких чисел много и они меняются очень быстро
в свете этого может быть смысл и есть.
хотя легче конечно пользоваться хэшалгоритмами типа МД5 для данных почти любой длины.
Здравствуйте, Nikeware, Вы писали:
N>Здравствуйте, Ерусов Дмитрий, Вы писали:
ЕД>>Ты вообще в курсе что такое хеш ЕД>>и зачем он нужен? ЕД>>И какие требования предъявлются к хеш-функции? N>Да вроде в курсе мы N>Я еще понимаю такие хеш-функции как "string->int" и им подобные, когда нужно получить соответствие между различными по мощности множествами. На "unsigned int->int" еще можно согласиться, но "int->int" Зачем воду в ступе толочь? Или я какой глубокий смысл в этом не заметил?
А нет ли у кого хорошего алгоритма "string->int".
А то я использую:
/* The hash algorithm used in the UNIX ELF format for object files.
The input is a pointer to a string to be hashed */
#define HASHSIZE 997
unsigned long ElfHash( const unsigned char *name)
{
unsigned long h = 0, g;
static int M = HASHSIZE;
while (*name)
{
h = ( h << 4 ) + *name++;
if (g = h & 0xF0000000L)
h ^= g >> 24;
h &= ~g;
}
return h % M;
}
но хотелось бы что-нить с бОльшим разбросом значений.
Здравствуйте, Ерусов Дмитрий, Вы писали:
ЕД>Так никто и не спорит с этим
ЕД>перебором можно любой хэш "взломать"
Речь идет об отдельно взятой функции.
И ее криптографическая стойкость не оставляет сомнений.
ЕД>вопрос только во времени, особенно если знаешь что это хеш инта(то есть 4 байт)
В классической крипографии всегда исходят из посылки то алгоритм известен атакующему,
поэтому полезность данной функции здесь равна нулю.
Как правильно заметил товарищ — в вычислительном плане она может быть заменена более простой
int hash(int data) { return data; };
ЕД>у меня речь о другом, что ты не можешь решить обратной задачи ЕД>из хэша получить число(не перебором)
А какая собственно разница как получено исходное число — перебором или не перебором,
если перебор работает достаточно быстро?
ЕД>хотя если честно то хрен его знает зачем шифровать 4 байтовые числа по одиночке
ЕД>но автор пишет про быстрый алгоритм ЕД>то есть можно подумать что таких чисел много и они меняются очень быстро ЕД>в свете этого может быть смысл и есть.
Абсолютно не вижу смысла.
ЕД>хотя легче конечно пользоваться хэшалгоритмами типа МД5 для данных почти любой длины.
Лучше понимать зачем и куда использовать хэширование, тем более такое ресурсоемкое как MD*, SHA*, RIPE* ( подставить по вкусу )
Здравствуйте, Kubyshev Andrey, Вы писали:
M>>Дает очень хорошое распределение на всем интервале 32-ух битных чисел (на 64-ех — не тестировал )
KA>Убери это сообщение и не позорься. Вот тебе оптимизированная хэш которая дает 100% распределение на всем имнтервали скольки угодно разрядных ints
KA>
KA>int hash_func_int( int data )
KA>{
KA> return data;
KA>}
KA>
Согласен полностью. Если бы тип 'int' был использован в качестве типа возврата чисто формально, а функция фактически производила бы отображение, например, 'int32' -> 'int16', то ее можно было бы воспринимать всерьез. А "хеш-функция" 'int32' -> 'int32' ценность модет представлять не более чем юмористическую (предлагаю переместить ветку).
Рассуждения о криптографических прменениях этой функции лишены всяких оснований. Во-первых, к хеш-функцим это никакого отношения не имеет. Во-вторых, шифры, основанные просто на однозначной подмене элементов шифруемого сообщения реальной криптографической ценности не представляют.
Здравствуйте, Kubyshev Andrey, Вы писали:
KA>Убери это сообщение и не позорься.
Я не кому ничего не навязываю.
KA>Вот тебе оптимизированная хэш которая дает 100% распределение на всем имнтервали скольки угодно разрядных ints
KA>
KA>int hash_func_int( int data )
KA>{
KA> return data;
KA>}
KA>
Эх... разработчики...
Давай представим, что мы хэшыруем указатели на память.
Наш распрекрасный new возвращает их выровнеными на 32 байта (зависит от реализации).
И еще к тому же из разных диапазонов адресов.
Например:
0x06000AC0
0x06000AD0
0x06000AE0
0x08000AC0
0x08000AD0
0x08000AE0
0x02000AC0
0x02000AD0
0x02000AE0
0x03100AC0
0x03100AD0
0x03100AE0
Нужно занести все эти результаты в хэш таблицу размером 1024.
Накладываем маску 0x3FF, и получаем индексы:
0x02C0
0x02D0
0x02E0
0x02C0
0x02D0
0x02E0
0x02C0
0x02D0
0x02E0
0x02C0
0x02D0
0x02E0
т.е. получается что из 1024 используются только 3 ячеки с глубиной списка 4,
а могло бы 12 с глубоной 1
При втором варианте поиск будет работать быстрее.
Аналогично можно рассуждать про IP адреса, и много чего остального.
Почему люди такие злые?
Почему нельзя просто вежливо спросить — "А за фига?"
Здравствуйте, menify, Вы писали:
M>Здравствуйте, Kubyshev Andrey, Вы писали:
KA>>Убери это сообщение и не позорься. M>Я не кому ничего не навязываю.
Ну профессиональным разработчикам такое просто невозможно навязать , а вот те кто учиться сполне подумают что так оно и делаеться.
Я говорю про тех которые тебе ставят положительные оценки.
Несмотря на то что твой пример совершенно высосан из пальца, ты все таки придумал как в него всунуть какое то подобие хэша
Прчем этот хэш (mask 3FF) НЕ ИМЕЕТ ничего общего с хэшем из первого твоего сообщения.
Я не поленился и использовал его с твоими указателями на из предыдуего примера и получил значения :
Очень хочется что бы ты придумал какой нибудь пример в этими значениями (только не надо про маску в 0x1 а потом 2 значания с глубиной 6)
Если ты в первом сообщении говорил про хороший разброс хэша, по в предыдущем примере он просто ужасен. Что и понятно потому что ты совершенно подменил "хэш"
M>Почему люди такие злые?
Зачем люди продолжают оправдывать свое невежество ?
M>Почему нельзя просто вежливо спросить — "А за фига?"
Пф, нонсенс
Здравствуйте, menify, Вы писали:
M>Давай представим, что мы хэшыруем указатели на память. M>Наш распрекрасный new возвращает их выровнеными на 32 байта (зависит от реализации). M>И еще к тому же из разных диапазонов адресов. M>Например: M>0x06000AC0 M>0x06000AD0 M>0x06000AE0 M>0x08000AC0 M>0x08000AD0 M>0x08000AE0 M>0x02000AC0 M>0x02000AD0 M>0x02000AE0 M>0x03100AC0 M>0x03100AD0 M>0x03100AE0
M>Нужно занести все эти результаты в хэш таблицу размером 1024. M>Накладываем маску 0x3FF, и получаем индексы: M>0x02C0 M>0x02D0 M>0x02E0 M>0x02C0 M>0x02D0 M>0x02E0 M>0x02C0 M>0x02D0 M>0x02E0 M>0x02C0 M>0x02D0 M>0x02E0
M>т.е. получается что из 1024 используются только 3 ячеки с глубиной списка 4, M>а могло бы 12 с глубоной 1 M>При втором варианте поиск будет работать быстрее.
Если ты собрался накладывать маску, то так и пиши в коде своей функции. Я же что-то в упор в твоем коде никакого накладывания маски не увидел. Вместе с накладыванием маски может и получится полноценная хеш-функция. А без нее то, что ты привел в своем оригинальном сообщении, никакого отношения к хеш-функциям не имеет.
Здравствуйте, menify, Вы писали:
M>Давай представим, что мы хэшыруем указатели на память. M>Наш распрекрасный new возвращает их выровнеными на 32 байта (зависит от реализации).
Хаха, я понял что ты хотел сказать ! Это был антипример ! Только все равно от нее пользы никакой Место ты не сократишь а только увеличишь потому что real values надо хранить, или ты хочешь наложить лимит в 64к указателей ? Ну а если у тебя и атк не много элементов , то поиск по 16 битным значения медленне чем по 32 . Что ты этим выигрываешь кроме размера source кода ?
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Если ты собрался накладывать маску, то так и пиши в коде своей функции. Я же что-то в упор в твоем коде никакого накладывания маски не увидел.
По моему на вход хэш функции поступают данные, а результатом является какое-то число.
Затем нам нужно вычислить индекс в хэш таблицы — обычно это простой остаток от деления на размер таблицы.
Размер таблицы вполне может менятся динамически, зачем его встраивать в функцию?
Здравствуйте, menify, Вы писали:
АТ>>Если ты собрался накладывать маску, то так и пиши в коде своей функции. Я же что-то в упор в твоем коде никакого накладывания маски не увидел.
M>По моему на вход хэш функции поступают данные, а результатом является какое-то число. M>Затем нам нужно вычислить индекс в хэш таблицы — обычно это простой остаток от деления на размер таблицы. M>Размер таблицы вполне может менятся динамически, зачем его встраивать в функцию?
Если речь идет о хеш-таблицах, то, по определению, применяемая в такой ситуации хеш-функция должна возвращать готовый индекс в таблице. Включает ли в себя способ вычисления этого индекса вычисление остатка от деления на последнем или на каком-либо промежуточном этапе — детали реализации хэш-функции, а не какое-то "дополнительное" действие.
Что ты имеешь в виду под динамическим изменением размера таблицы, я не совсем понял. Если размер таблицы меняется в процессе ее использования, то каким образом ты предлагаешь восстанавливать индексы ключей занесенных в эту таблицу до изменения ее размера?
В более общем случае хеширования (не в конкретном случае хеш-таблиц) для того, чтобы представлять какую-то практическую ценость, хеш-функция должна всегда "упаковывать" более длинные данные в более короткие ("упаковка" бует необратимая, разумеется). То, что ты предложил в своем исходном сообщении, даже если и можно назвать хеш-функцией на некотором уровне абстракции, тем не менее не обладает перечсленным тобою преимуществами над тривиальной хеш-функцией, которую предложил Kubyshev Andrey. Поэтому тебе и сделали замечание. Во многом чисто теминологическое. Предложенная тобою функция может и является хорошим началом для хеш-функции, но готовой хеш-функцией она сама по себе не является.
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Что ты имеешь в виду под динамическим изменением размера таблицы, я не совсем понял. Если размер таблицы меняется в процессе ее использования, то каким образом ты предлагаешь восстанавливать индексы ключей занесенных в эту таблицу до изменения ее размера?
Когда таблица создана, ее размер естественно не меняется.
Но хэш таблиц, разной длины может сколько угодно.
В одной мы хэшируем указатели, в другой файловые дескрипторы, но везде используется одна и та же хэш функция.
АТ>В более общем случае хеширования (не в конкретном случае хеш-таблиц) для того, чтобы представлять какую-то практическую ценость, хеш-функция должна всегда "упаковывать" более длинные данные в более короткие ("упаковка" бует необратимая, разумеется).
Это именно и относилось к эфективности использования хэш таблиц.
А еще важно, чтобы хэш функция давала хорошее распределение, ведь хэш функции бывают разные.
Можно например для строки брать первые четыре байта, восстановить не возможно, но это плохая хэш функция.
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Если речь идет о хеш-таблицах, то, по определению, применяемая в такой ситуации хеш-функция должна возвращать готовый индекс в таблице. Включает ли в себя способ вычисления этого индекса вычисление остатка от деления на последнем или на каком-либо промежуточном этапе — детали реализации хэш-функции, а не какое-то "дополнительное" действие.
Не должна.
И в общем случае не может быть никак завязана на размер таблицы.
Динамические хеш таблицы ( метод 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 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
)
Зачем воду в ступе толочь? Или я какой глубокий смысл в этом не заметил?
