Форум программистов, компьютерный форум CyberForum.ru

Идеальное хеширование - C++

Восстановить пароль Регистрация
 
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
16.10.2011, 17:52     Идеальное хеширование #1
Суть вопроса заключается вот в чем. В методичке по лабораторным рассказывается про идеальное хеширование.
Идеальное хеширование
Чаще всего хеширование используется из-за превосходной средней
производительности, возможна ситуация, когда реально получить
превосходную производительность хеширования в наихудшем случае. Такой
ситуацией является статическое множество ключей, т.е. после того как все
ключи сохранены в таблице, их множество никогда не изменяется. Ряд
приложений в силу своей природы работает со статическими множествами
ключей. В качестве примера можно привести множество зарезервированных
слов языка программирования или множество имен файлов на компакт-
диске. Идеальным хешированием мы называем методику, которая в
наихудшем случае выполняет поиск за O(1) обращений к памяти.
Рассмотрим детальнее пример приведенный на рисунке, где показано
сохранение статического множества ключей К = {10, 22, 37, 40, 60, 70, 75} в
хеш-таблице с использованием технологии идеального хеширования.
Внешняя хеш-функция имеет вид h(k) = ((аk + b) mod p) mod m, где а = 3,
b = 42, р = 101 и m = 9. Например, h(75) = 2, так что ключ 75 хешируется в
ячейку 2. Вторичная хеш-таблица Sj хранит все ключи, хешированные в
ячейку j. Размер каждой таблицы Sj равен mj, и с ней связана хеш-функция
hj(b) = ((ajk + bi) mod p) mod mi. Поскольк hj(75) = 1, ключ 75 хранится в
ячейке 1 вторичной хеш-таблицы. Ни в одной из вторичных таблиц нет ни
одной коллизии, так что время поиска в худшем случае равно константе.
Для того чтобы гарантировать отсутствие коллизий на втором уровне,
требуется, чтобы размер m хеш-таблицы Sj был равен квадрату числа nj
ключей, хешированных в ячейку j.
Мне препод дал ряд чисел и сказал сделать на листочке идеальное хеширование. Я так понял, что надо использовать данные формулы. НО я не понимаю как тут объясняется коллизияи как понять, что ее нет. Можете привести пример, если кому не лень, а то про идеальное хеширование я как-то не въеал.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.10.2011, 17:52     Идеальное хеширование
Посмотрите здесь:

идеальное хеширование C++
C++ Хеширование
C++ Хеширование
Хеширование C++
Хеширование C++
C++ Хеширование пароля
C++ Хеширование
C++ Хеширование чисел

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 10:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru