Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | |
Поясняю 11.12.06 00:49 Число просмотров: 5477
Автор: leo <Леонид Юрьев> Статус: Elderman
|
|
64-битная hash-функция, в случае её применения для построения ассоциативных hash-таблиц, может выиграть у 32-битной только когда размер "плоской" части таблицы приблизится или превзойдёт 2^32. В свою очередь, такой размер таблицы будет оправдан, только когда кол-во входов приблизится к 2^31. В реальной жизни таких наборов данных очень не много, для их обработки таким способом нужно как минимум несколько десятков мегабайт RAM.
|
|
<theory>
|
|
Не только количество коллизий характеризует hash-функцию... 18.09.06 12:07
Автор: thror Статус: Незарегистрированный пользователь
|
> Вот приятель сделал небольшой тест, достаточно любопытно.
Не только количество коллизий характеризует hash-функцию. Более того -- количество коллизий не самый такой значительный показатель, как может показаться сперва. Для дополнительной информации рекомендую обратиться к следующим материалам:
[1] Ахо, Сети, Ульман. Компиляторы: принципы, технологии, инструменты -- Хэш-таблицы
[2] Керниган, Пайк. Практика программирования -- Хэш-таблицы
[3] Кормен, Лейзерсон, Ривест [, Штайн]. Алгоритмы: построение и анализ -- Идеальное хэширование
---
Судя по тестам многие другие материалы вам известны.
|
|
Информация интересная. Правда, есть вопрос... 20.08.06 21:07
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 21.08.06 11:05 Количество правок: 1
|
Вот сейчас потихоньку наступают 64-битные процы. Есть ли смысл использовать 64-битные хеши (и алгоритмы), или это излишний оверхед по памяти?
Заранее всем спасибо за ответы.
|
| |
hash в 64 бита реально нужен только когда кол-во элементов в таблице будет больше чем 2^32. 21.08.06 12:03
Автор: leo <Леонид Юрьев> Статус: Elderman
|
|
Но для таких больших таблиц все равно будет много hash-коллизий, поэтому для таких случаев "огромных данных", как правило, делают вложенные 32-битные hash-таблицы с использование двух разных hash-функций.
|
| | |
При чем тут количество элементов в таблице? Не понял. 10.12.06 23:36
Автор: MadBinom Статус: Незарегистрированный пользователь
|
> Но для таких больших таблиц все равно будет много
> hash-коллизий, поэтому для таких случаев "огромных данных",
> как правило, делают вложенные 32-битные hash-таблицы с
> использование двух разных hash-функций.
При чем тут количество элементов в таблице? Не понял.
Спросили про наступление 64-разрядных процов - поэтому вложенные 32-битные таблицы давайте даже не упоминать. Ответ - да, надо использовать преимущества 64-х битных функций перед 32-х битными при использовании в 64-х разрядной архитектуре.
|
| | | |
Поясняю 11.12.06 00:49
Автор: leo <Леонид Юрьев> Статус: Elderman
|
|
64-битная hash-функция, в случае её применения для построения ассоциативных hash-таблиц, может выиграть у 32-битной только когда размер "плоской" части таблицы приблизится или превзойдёт 2^32. В свою очередь, такой размер таблицы будет оправдан, только когда кол-во входов приблизится к 2^31. В реальной жизни таких наборов данных очень не много, для их обработки таким способом нужно как минимум несколько десятков мегабайт RAM.
|
| | | | |
Сказанное понял, но вот в чем тут проблема. Мы говорим о... 11.12.06 01:15
Автор: MadBinom Статус: Незарегистрированный пользователь
|
> 64-битная hash-функция, в случае её применения для
> построения ассоциативных hash-таблиц, может выиграть у
> 32-битной только когда размер "плоской" части таблицы
> приблизится или превзойдёт 2^32. В свою очередь, такой
> размер таблицы будет оправдан, только когда кол-во входов
> приблизится к 2^31. В реальной жизни таких наборов данных
> очень не много, для их обработки таким способом нужно как
> минимум несколько десятков мегабайт RAM.
Сказанное понял, но вот в чем тут проблема. Мы говорим о хеш-функциях для построения, например, строковых пулов и прочего, требующего именно скорости(ведь говорилти о хеш для строк). Такие хэш функции обладают очень плохими показателями по поводу коллизий. Поэтому рассмотрим 2 варианта, строковой пул большой(сказано грубо конечно, но да ладно, смысл разделения на 2 ситуации прояснится в подпунктах) или маленький.
1.Пул маленький
Коллизий немного как у 32-х так и у 64-х функций.
Скорость у 32-х разрядных меньше чем у 64-х разрядных.(учитывая 64х архитектуру)
Памяти примерно в 2 раза(тк коллизий мало) больше ест 64-разрядная реализация.Но ведь пул небольшой.
2.Пул большой.
Коллизий много больше у 32-х чем у 64-х функций.
Скорость у 32-х разрядных меньше чем у 64-х разрядных.(учитывая 64х архитектуру)
Памяти много больше ест 64-разрядная реализация(много больше так как строк много), но это ПОЧТИ всегда единственный выход - так как тут у нас резкое падение производительности при использовании 32-х функций, так как много у них коллизий.
|
| | | | | |
Возражение против CRC64 15.01.07 12:38
Автор: xyz Статус: Незарегистрированный пользователь
|
>При чем тут количество элементов в таблице? Не понял.
>Спросили про наступление 64-разрядных процов - поэтому вложенные 32-битные таблицы давайте >даже не упоминать. Ответ - да, надо использовать преимущества 64-х битных функций перед 32-х >битными при использовании в 64-х разрядной архитектуре.
1) Насколько я знаю, в системе команд обычных процов нет команды типа "сдвинуть AX пользуя BX как массив битов обратных связей". Стало быть вместо регистра с обратными связями используется код с кучей логических операций плюс магические таблицы в помощь. Поэтому пофигу что вычислять crc64,
или две crc32, возможно, параллельно.
2) В последние время даже в популярных книжках стали публиковать неприводимые многочлены зверских степеней, это не проблема. Но как выбрать из них многочлен максимальной длины?
Это возможно только полным прогоном всех остатков. Перебрать 2^64-1 остатков просто нереально,
насколько я знаю, перебором можно взять где-то 40 бит. Поэтому надежней сшить или перемножить пару полиномов 32 степени.
Вот вам и 64 разряда.
|
| | | | | | |
Про систему команд. 16.01.07 01:18
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Почти все операции, кроме некоторых, таких как циклический сдвиг и сложение по модулю 2^32, не имеют отличий при вычислении HASH-функций.
Другими словами, любой нормальный компилятор для любой 32-битной HASH-функции сгенерирует 64-битный код, при необходимости усекая результаты до 2^32-1.
Использовать 64-битную хеш-функции имеет смысл только для экономии на операциях усечения, или когда действительно нужен 64-битный результат (т.е. для огромных таблиц).
P.S.
CRC32 и CRC64 хоть и основываются на делении полиномов в поле 2, реально всегда выполняются на таблицах. Полиномная арифметика нужна только при построении этих таблиц.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
