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

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

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

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

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

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

vilfred(*) (2010-03-12 11:57:25)

Подтверждено: vilfred(*) (2010-03-12 12:44:34)

[Ответить на это сообщение]

Ответ на: сравнение скорости работы различных реализаций хэш-функций от vilfred 2010-03-12 11:57:25

Скрыть

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

А перевести?

Tux-oid(*)(2010-03-12 12:01:28)

Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.1) Gecko/20090624 Firefox/3.5

[Ответить на это сообщение]

Ответ на: сравнение скорости работы различных реализаций хэш-функций от vilfred 2010-03-12 11:57:25

Скрыть

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

რა?

anonymous(*)(2010-03-12 12:09:11)

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от Tux-oid 2010-03-12 12:01:28

Скрыть

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

в процессе

vilfred(*)(2010-03-12 12:29:27)

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.1) Gecko/2008072807 ASPLinux/3.0.1-1.0.140asp Firefox/3.0.1

[Ответить на это сообщение]

Ответ на: сравнение скорости работы различных реализаций хэш-функций от vilfred 2010-03-12 11:57:25

Скрыть

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

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

anonymous(*)(2010-03-13 05:31:35)

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от anonymous 2010-03-13 05:31:35

Скрыть

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

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

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

SystemV(*)(2010-03-13 19:37:15)

Mozilla/5.0 (X11; U; Linux; ru-RU) AppleWebKit/532.4 (KHTML, like Gecko) rekonq Safari/532.4

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от anonymous 2010-03-13 05:31:35

Скрыть

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

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

vilfred(*)(2010-03-13 19:56:22)

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.1) Gecko/2008072807 ASPLinux/3.0.1-1.0.140asp Firefox/3.0.1

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от SystemV 2010-03-13 19:37:15

Скрыть

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

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

anonymous(*)(2010-03-13 20:42:39)

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от vilfred 2010-03-13 19:56:22

Скрыть

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

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

HEBECTb_KTO(*)(2010-03-14 00:07:57)

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от anonymous 2010-03-13 20:42:39

Скрыть

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

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

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

SystemV(*)(2010-03-14 00:36:24)

Mozilla/5.0 (X11; U; Linux; ru-RU) AppleWebKit/532.4 (KHTML, like Gecko) rekonq Safari/532.4

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от SystemV 2010-03-14 00:36:24

Скрыть

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

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

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

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

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

anonymous(*)(2010-03-14 03:51:13)

Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.8) Gecko/20100312 Gentoo Firefox/3.5.8

[Ответить на это сообщение]

Ответ на: Re: сравнение скорости работы различных реализаций хэш-функций от anonymous 2010-03-14 03:51:13

Скрыть

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

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

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

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

SystemV(*)(2010-03-15 05:54:01)

Mozilla/5.0 (X11; U; Linux; ru-RU) AppleWebKit/532.4 (KHTML, like Gecko) rekonq Safari/532.4

[Ответить на это сообщение]

anonymous@RULINUX.NET~#	Last login: 2024-11-22 18:08:25
Регистрация Вход	Новости \| Разметка \| Пользователи \| Галерея \| Форум \| Статьи \| Неподтвержденное \| Трекер \| Правила форума \| F.A.Q. \| Ссылки \| Поиск

Этот тред читают 3 пользователя:
Анонимных: 3 Зарегистрированных: 0