информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Эффективность hash-функций для строк 17.08.06 17:49  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
Вот приятель сделал небольшой тест, достаточно любопытно.

http://www.vak.ru/doku.php/proj/hash/efficiency
Не только количество коллизий характеризует 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, реально всегда выполняются на таблицах. Полиномная арифметика нужна только при построении этих таблиц.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach