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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
#1

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

16.10.2011, 17:52. Просмотров 1006. Ответов 0
Метки нет (Все метки)

Суть вопроса заключается вот в чем. В методичке по лабораторным рассказывается про идеальное хеширование.
Идеальное хеширование
Чаще всего хеширование используется из-за превосходной средней
производительности, возможна ситуация, когда реально получить
превосходную производительность хеширования в наихудшем случае. Такой
ситуацией является статическое множество ключей, т.е. после того как все
ключи сохранены в таблице, их множество никогда не изменяется. Ряд
приложений в силу своей природы работает со статическими множествами
ключей. В качестве примера можно привести множество зарезервированных
слов языка программирования или множество имен файлов на компакт-
диске. Идеальным хешированием мы называем методику, которая в
наихудшем случае выполняет поиск за 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++
У меня есть вариант хешировани данных для ГОСТ 28147-89. Помогите ее переделать под ГОСТ Р 34.11-94. вот...

Хеширование - C++
Вот такая проблема... Точнее их много, но если по порядку, то сейчас только такая проблема: Хеширование, методом середины квадрата,...

Хеширование - C++
1. Реализовать интерактивное приложение со следующей функциональностью, использующее вышеописанный модуль. a. Создание хеш-таблицы...

Хеширование - C++
Помогите, пожалуйста.Поиск в хеш-таблицах. Написать класс Group. В группу должны входить студенты, содержащие следующие данные: -фамилия ...

Хеширование - C++
1. Реализовать интерактивное приложение со следующей функциональностью, использующее вышеописанный модуль. a. Создание хеш-таблицы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.10.2011, 17:52
Привет! Вот еще темы с ответами:

Хеширование строки - C++
Всем привет! Знаю што на си++ можно захешыровать строку в алгоритм md5 несколькима способами, нашел код хешырования на чистом си, но...

Хеширование чисел - C++
Здравствуйте, прочел пост taras atavin И стало интересно, действительно ли такое можно сделать ? реально ли хешировать число до 70...

Хеширование пароля - C++
Проблема такая, нужно захешировать пароль пользователя, пробовал уже всё, что нашел в интернете, наверное я тугой В общем, не подскажете...

Хеширование файлов - C++
Доброго времени суток) Я в этой теме пока мало что понимаю, но может мне может кто то объяснить, как хешируются файлы (такие как .exe)....


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru