rulinux.net - Новости - Документация - сравнение скорости работы различных реализаций хэш-функций

Re: сравнение скорости работы различных реализаций хэш-функций

Mon, 15 Mar 2010 01:54:01 +0300

>Если ты про хеш как тип данных, т.е. массив по нечисловому индексу - это не в тему.
Хэш как тип данных внутри это вполне себе массив с числовым индексом. Берут, например, хэш от ключа, берут его остаток от деления на размер массива - и вот есть числовой индекс.

В статье по ссылке именно об этом и говорится. "A hash function is used to map the key value (usually a string) to array index.", и даже пример с "return hash % TABLE_SIZE". Да и, собственно, сравнивают они скорость хэш-таблиц.

>Это везде так, можно сказать основные требования к любому хешу.
В общем да, но коллизии в обычном хэше, вычисляемом для получения индекса массива, не так и страшны, как в случае криптографии. Хотя наверное главное отличие - это то, что обычным хэшам не нужны никакие "лавинные эффекты" и прочие навороты, мешаюшие подбирать.

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 23:51:13 +0300

>Хэш-таблицы находят применение почти везде. Во многих языках они есть по умолчанию
Если ты про хеш как тип данных, т.е. массив по нечисловому индексу - это не в тему. Я говорил именно про механизм, когда для специфичных данных нужно вычислить ключ.

>В общем, обычные хэш-функции обычно проще криптографических.
Да, похоже так и есть.

>Тут главное - скорость работы + малое количество коллизий.
Это везде так, можно сказать основные требования к любому хешу.

>Для криптографических хэш-функций задача другая...
Это всё ясно и известно.

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 20:36:24 +0300

>Что есть обычный хеш и кому он нужен? Я что-то помню из курса ОС (или из Танненбаума, или из Робачевского...), что, например, в реализации файловых систем применяются хеш-таблицы - это тут они находят применение?
Хэш-таблицы находят применение почти везде. Во многих языках они есть по умолчанию (например питон и пхп). "Обычные" хэш-функции нужны, собственно, чтобы создавать ключи для хэш-таблиц. Тут главное - скорость работы + малое количество коллизий. Причём нужен баланс между этими двумя вещами. В общем, обычные хэш-функции обычно проще криптографических.

Для криптографических хэш-функций задача другая - необходимо создавать уникальные хэши, в идеале вообще без коллизий (хотя так не бывает). Неважно, насколько быстро создаётся/проверяется пароль - главное чтобы его сложно было подобрать:) Также такие функции находят применение в задачах сравнения одинаковых файлов итд. Плюс для криптографии хорош "лавинный эффект" - когда изменение одного символа в исходной строке серьёзно меняет вид получившегося хэша. Это позволяет неплохо увеличить сложность подбора ключа к хэшу.

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 20:07:57 +0300

> они походу об секьюрных хешах опосредованно говорят
Здорово ты ТС-нул, что сам теперь гадаешь о чём они говорят. Мне по твоему тексту показалось, что они говорят о хешах, хешах и хешах. Называя разные вещи одним и тем же словом. Хеш как структура данных (помянут первым), хеш как функция от некоего значения (криптографический хеш) и ещё какой-то хеш, который не является ни тем ни другим (наверное тоже функция, но попроще и побыстрее).

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 16:42:39 +0300

Что есть обычный хеш и кому он нужен? Я что-то помню из курса ОС (или из Танненбаума, или из Робачевского...), что, например, в реализации файловых систем применяются хеш-таблицы - это тут они находят применение?

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 15:56:22 +0300

они походу об секьюрных хешах опосредованно говорят

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 15:37:15 +0300

>Я, наверное, абсолютно тёмная личность, но почему в статье нету терминов md5, sha?
Вот поэтому:

>Обычный хэш отличается от, например, криптографического хэша скоростью своей работы, т.е. скоростю извлечения элементов, ну или скоростью сопоставления соответствий значения ключу.

Re: сравнение скорости работы различных реализаций хэш-функций

Sat, 13 Mar 2010 01:31:35 +0300

Я, наверное, абсолютно тёмная личность, но почему в статье нету терминов md5, sha?

Re: сравнение скорости работы различных реализаций хэш-функций

Fri, 12 Mar 2010 08:29:27 +0300

в процессе

Re: сравнение скорости работы различных реализаций хэш-функций

Fri, 12 Mar 2010 08:09:11 +0300

რა?

Re: сравнение скорости работы различных реализаций хэш-функций

Fri, 12 Mar 2010 08:01:28 +0300

А перевести?

сравнение скорости работы различных реализаций хэш-функций

Fri, 12 Mar 2010 07:57:25 +0300

Хэш - очень популярная структура данных, в которой, подобно массиву, доступ к элементу осуществляется по индексу, но, в отличии от массива, индекс может быть не числом, а любым значением. Обычный хэш отличается от, например, криптографического хэша скоростью своей работы, т.е. скоростю извлечения элементов, ну или скоростью сопоставления соответствий значения ключу. Существует два типа хэш-функций:

простые хеш-функции, отличающиеся быстротой, но и имеющие большое число ошибок;
хеш-функции с различными встроенными проверками, которые замедляют извлечение пары ключ-значение, но делают это более надежно.

Хеши часто характеризуются числом ошибок или согласованностью представления данных (см., например, сравнения хэшей в книжке Red Dragon). Очевидно, что при написании программы возникает вопрос: при использовании какой из функций можно увеличить скорость работы программы? Хэши второго типа требуют больше операций для проверки ключ-значение и по ссылке приведена сравнительная характеристика скорости работы хешей, например на добавление новых элементов.

>>> Подробнее