Дает очень хорошое распределение на всем интервале 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. Поэтому тебе и сделали замечание. Во многом чисто теминологическое. Предложенная тобою функция может и является хорошим началом для хеш-функции, но готовой хеш-функцией она сама по себе не является.
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Что ты имеешь в виду под динамическим изменением размера таблицы, я не совсем понял. Если размер таблицы меняется в процессе ее использования, то каким образом ты предлагаешь восстанавливать индексы ключей занесенных в эту таблицу до изменения ее размера?
Когда таблица создана, ее размер естественно не меняется.
Но хэш таблиц, разной длины может сколько угодно.
В одной мы хэшируем указатели, в другой файловые дескрипторы, но везде используется одна и та же хэш функция.
АТ>В более общем случае хеширования (не в конкретном случае хеш-таблиц) для того, чтобы представлять какую-то практическую ценость, хеш-функция должна всегда "упаковывать" более длинные данные в более короткие ("упаковка" бует необратимая, разумеется).
Это именно и относилось к эфективности использования хэш таблиц.
А еще важно, чтобы хэш функция давала хорошее распределение, ведь хэш функции бывают разные.
Можно например для строки брать первые четыре байта, восстановить не возможно, но это плохая хэш функция.
)
Зачем воду в ступе толочь? Или я какой глубокий смысл в этом не заметил?
