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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Дано 10 чисел, вводимых с клавиатуры. найти два крупнейших числа и их номера http://www.cyberforum.ru/cpp-beginners/thread367268.html
есть 10 чисел вводимых с клавиатуры. найти два крупнейших числа и их номера. int poz1, poz2, max1,max2;// using namespace std; cout<<"vvedit 10 chusel: \n"; max1=max2=0; cin >> b; if(b>max1) {max1 = b; poz1=1; poz2=2;} cin >> c; if(c>max1) {max2 = max1; max1 = c; poz2=2; poz1=1;} cin >> d;
C++ Ряд Тейлора. Нужна помощь Добрый день всем. Возникла такая проблема. Есть ряд An= (x в степени 2n+1)/(2n+1) Нужно ввести x нач. и x кон., шаг и точность. Вывести на экран таблицу значений, аргумент и кол-во слагаемых в операции Но есть еще приписка x по молулю<1 Помогите решить) http://www.cyberforum.ru/cpp-beginners/thread367265.html
C++ Подключение к базе данных Access в VS 2010 Premium
Доброго времени суток! в VS 2010 Premium не получается выбрать источник данных (хочу подключиться к базе данных Access, чтобы использовать данные таблиц в элементах экранных форм, например, в combobox). Выхожу в окно Источник данных, где должна быть возможность присоединиться к базе данных, а такая возможность отсутствует. На вкладке "Данные" главного меню так же отсутствует вариант "Добавить...
C++ Как подключить cpp файл к проекту?
есть cpp файл date где описаны класс и его методы подключаю к main с помощью #include "date.cpp" выдает следующие ошибки: Ошибка 1 error LNK2005: "public: void __thiscall Date::Read(void)" (?Read@Date@@QAEXXZ) уже определен в date.obj C:\Documents and Settings\Администратор\Мои документы\Visual Studio 2010\Projects\laba3\laba3\main.obj Ошибка 2 error LNK2005: "public: void __thiscall...
C++ Для каждого символа заданного текста указать, сколько раз он встречается в тексте http://www.cyberforum.ru/cpp-beginners/thread367253.html
Доброго времени суток , прошу помочь с решением задачи : Для каждого символа заданного текста указать, сколько раз он встречается в тексте. Сообщение об одном символе должно печататься не более одного раза. (Ввод текста с клавиатуры) Заранее благодарен за помощь.
C++ Телефонный справочник. Здравствуйте. Нужна помощь в создании программы, которая объединяла бы в себе действия: "Добавление в телефонный справочник" и "Поиск в Справочнике". Причем, надо создать меню, которое должно включать в себя: ***Телефонный Справочник*** 1)Добавление в справочник. 2)Поиск в справочнике. 3)Завершение работы. Выбор пункта должен осуществляться Вводом этого пункта (непонятно куда?) и нажатием... подробнее

Показать сообщение отдельно
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
16.10.2011, 17:52     Идеальное хеширование
Суть вопроса заключается вот в чем. В методичке по лабораторным рассказывается про идеальное хеширование.
Идеальное хеширование
Чаще всего хеширование используется из-за превосходной средней
производительности, возможна ситуация, когда реально получить
превосходную производительность хеширования в наихудшем случае. Такой
ситуацией является статическое множество ключей, т.е. после того как все
ключи сохранены в таблице, их множество никогда не изменяется. Ряд
приложений в силу своей природы работает со статическими множествами
ключей. В качестве примера можно привести множество зарезервированных
слов языка программирования или множество имен файлов на компакт-
диске. Идеальным хешированием мы называем методику, которая в
наихудшем случае выполняет поиск за 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.
Мне препод дал ряд чисел и сказал сделать на листочке идеальное хеширование. Я так понял, что надо использовать данные формулы. НО я не понимаю как тут объясняется коллизияи как понять, что ее нет. Можете привести пример, если кому не лень, а то про идеальное хеширование я как-то не въеал.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 14:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru