Алгоритмы и Структуры Данных

Таблица смоделированных вероятностей возникновения коллизии в таблице размером 32 и вычисленных по уравнению (2)Мощность множества.

Измеренная вероятность возникновения коллизии, %Вычисленная вероятность возникновения коллизии, %27.

583.

13 534.

628.

1 081.

679.

215 100.

098.

0Выводы1) Реализованы хэш-таблицы размером 32, на которых был реализован заданный алгоритм (уравнение (1))с множествами мощностью 16, содержащими числа от 0 до 100.

2) Было показано, что временная сложность алгоритма бинарных операций с использованием реальных хэш-таблиц может отличаться от O (1), так как необходимо учитывать образование новой таблицы с выделением памяти под новые элементы. Поскольку сложность вставки нового элемента в таблицу O (1), то сложность заполнения новой таблицы множествомс мощностью N -O (N).3) Было показано, что при равномерном заполнении хэш-таблицы множеством мощностью 0.5 от размера таблицы возникновение коллизии практически неизбежно.

4) Для хранения множеств со средней мощностью 50 нужно выделять примерно в два раза больший объем памяти под хэш-таблицу, то есть равный 100 ячейкам таблицы.

5) Больше памяти расходует хэш-таблица с открытой адресацией, поскольку в этом случае размер таблицы должен минимизировать вероятность возникновения переполнений.

6) Хорошая хэш-функция должна, примерно, равномерно распределять ключи по номерам хэш-индексов.

7) Если размер таблицы равен размеру универсума, а каждому значению ключа соответствует только одно значение хэш-индекса, то в такой хэш-таблице гарантировано не будет коллизий.

8) Оптимальный алгоритм выполнения двухместной операции над множествами в хэш-таблицах заключается в параллельном переборе элементов двух хэш-таблиц. Поскольку размер хэш-таблиц задан и постоянен, то временная сложность такого алгоритма не будет зависеть от размеров множеств и будет равна O (1).9) В хэш-таблице можно хранить несколько одинаковых ключей, однако, это приведет к гарантированной коллизии.

10) Временная сложность вставки и удалениянового элемента из таблицы равна O (1).11) Для хэш-таблицы обычно приводят двеоценки сложности операций — сложность в среднем и сложность в худшем случае, так как при вырождении хэш-таблицы в список преимущества от ее использования теряются и сложность операций в хэш-таблице становится равной сложности операций над списками.

12) Для таблицы с цепочками переполнения с увеличением числа коллизий таблица вырождается в mпоследовательных списков, чтобы этого избежать необходимо выбирать таблицу по возможности большего размера.

13) Если переполняется таблица с открытой адресацией, то необходимо увеличить ее размер. Как правило, размер таблицы после переполнения увеличивают на постоянный множитель, обычно, в двое.

Список литературы

1) Колинько П. Г. Алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию. Часть 1. Выпуск 1601.

СПбГЭТУ «ЛЭТИ». 2016. 64 С.2) Страуструп Б. Язык программирования С++. 2е доп. изд. — М.: Бином-пресс, 2001. — 1098 С.3) Колинько П. Г. Алгоритмы и структуры данных.

Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию. Часть 2. Выпуск 1606. СПбГЭТУ «ЛЭТИ». 2016. 51 С.4).

https://en.wikipedia.org/wiki/Birthday_problemПриложение. Структура проекта HashTableФайл.

СодержаниеHashTable.vcxproj, HashTable.vcxproj.filters, HashTable. slnСлужебныефайлыпроектаMicrosoft Visual StudioHashTable. h, HashTable. cppИсходный код реализации хэш-таблицHashTableEntry.h, HashTableEntry. cppИсходный код реализации элемента хэш-таблицыmain.cppВходная точка консольного приложения, основной файл программы.