Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606

Название	Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
Анкор	Методические указания алгоритмы и структуры данных
Дата	03.10.2019
Размер	429.85 Kb.
Формат файла
Имя файла	task_180930.docx
Тип	Методические указания #88422
страница	2 из 8

1 2 3 4 5 6 7 8

1. ХЕШ-ТАБЛИЦЫ

Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U очень велика по отношению к мощности множеств, с которыми нужно работать. Функция отображения преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы, m ≪ |U|. Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, имеется возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии).

Количество возможных коллизий можно уменьшить, если выполнить два условия:

1) выбрать размер хеш-таблицы с запасом. Если размер таблицы превышает мощность хранимого множества более чем вдвое, вероятность коллизии становится меньше 0,5. Если мощность множества заранее неизвестна, то выбирают некоторый начальный размер, а когда его оказывается недостаточно, таблицу перестраивают с увеличением размера (обычно вдвое);

2) подобрать функцию отображения (хеш-функцию) такую, чтобы все ячейки таблицы были востребованы по возможности с равной вероятностью, независимо от того какое распределение имеют хранящиеся в таблице ключи.

По способу разрешения коллизий различают хеш-таблицы двух типов:

1) с открытой адресацией. Конфликтующие значения ключей размещаются в свободных ячейках таблицы;

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

Подробнее о хеш-таблицах см. [1, с. 529–556], [2, с. 567–601], [3, с. 115–128], [4, с. 316–338].

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

За постоянное время будут выполняться и двуместные операции над множествами: объединение, пересечение и разность: если хеш-функции для обоих множеств одинаковы, для этого пригоден такой же алгоритм попарного сравнения соответствующих ячеек, как и для массивов битов.

В хеш-таблице можно хранить и множество с повторениями: совпадающие значения ключей не создают никаких проблем, кроме гарантированных коллизий, которые разрешаются обычным образом.

К сожалению, всегда можно подобрать такие данные, что они все попадут в одну или несколько ячеек таблицы, образовав неупорядоченные списки (упорядочивание обычно не применяется). Это худший случай, для которого справедливы оценки временной сложности для списков: O(n) — для поиска и удаления элемента; O(n²) — для двуместной операции над множествами.

Подбор подходящей хеш-функции — в общем случае достаточно сложная задача. Но если ключи представляют собой целые числа (или сводятся к таковым), хорошие результаты можно получить с хеш-функцией вида

h(x) = (a * x + b) % m,

где m – размер таблицы, а a и b — простые числа.

Обычно a выбирается близким по значению к m, а b — к 1. Так, при m = 100 можно взять a = 97, b = 11. Такой выбор обеспечивает равномерное использование всех ячеек таблицы в большинстве практических случаев.

1.1. Практикум по теме

Составить и отладить программу для вычисления пятого множества по четырём заданным, представленным в форме хеш-таблиц. Элементы множеств — целые числа из интервала [0, MAXINT] (для удобства вывода на экран и увеличения вероятности появления общих элементов в множествах рекомендуется ограничиться интервалом [0, 100] или [0, 1000]). Формула для вычислений и средняя мощность множеств выбираются из табл. 1.1 в соответствии с номером индивидуального варианта. Подходящий размер хеш-таблиц определить по мощности обрабатываемых множеств.

Хеш-таблицу закодировать как класс, а операции с ней — как функции-члены этого класса. В качестве образца можно использовать программу для работы с множествами-объектами, составленную в предыдущем семестре.

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

Таблица 1.1

Индивидуальные задания к темам «Хеш-таблицы»
и «Деревья двоичного поиска»

№ вари- анта	Мощность множества	Что надо вычислить	№ вари- анта	Мощность множества	Что надо вычислить
1	10	A ∩ B ∪ C ∪ (D ⊕ E)	26	26	A \ (B ∩ C ∩ D) ⊕ E
2	26	(A \ B \ C) ⊕ D ∪ E	27	16	(A ∪ B ⊕ C ∩ D) ∩ E
3	16	A ∩ B ⊕ C ∩ D ∩ E	28	26	A ⊕ (B ∪ C ∪ D) ∩ E
4	26	(A ⊕ B \ C) ∪ D ∩ E	29	10	(A \ B) ∪ C ⊕ D ∪ E
5	10	A ⊕ B \ (C ∪ D) \ E	30	32	A ∪ B ∩ C ∪ D ⊕ E
6	32	(A ∩ B) ⊕ C ∪ D \ E	31	16	(A ⊕ B) ∪ (C \ D) \ E
7	16	A ∪ B ∪ C ⊕ D ∩ E	32	32	(A ∪ B ∪ C) \ D ⊕ E
8	26	A \ (B ∩ C) ∪ D ⊕ E	33	10	(A ∩ B) ⊕ (C ∪ D) \ E
9	10	A ⊕ B ∩ C ∪ D ∪ E	34	26	A \ B \ (C ⊕ D) \ E
10	26	((A ∪ B) \ C) ∩ D ⊕ E	35	16	(A ∪ B) \ (C ∪ D) ⊕ E
11	16	A ∪ B ⊕ C \ D \ E	36	32	(A ⊕ B ∩ C) \ D ∩ E
12	26	A ∪ B ∪ C ⊕ D \ E	37	10	A \ (B ∩ C ∪ D) ⊕ E
13	10	A ⊕ B \ C \ D ∩ E	38	32	(A ∪ B ⊕ C) \ D ∩ E
14	32	A \ B ⊕ (C \ D \ E)	39	16	A ∩ B ∪ C ∩ D ⊕ E
15	16	(A ∪ B) \ C \ (D ∪ E)	40	52	(A \ B) ∪ C ⊕ D ∩ E
16	32	(A ⊕ B ∩ C) \ D ∩ E	41	10	A ⊕ B ∪ C ∩ D ∪ E
17	10	A \ (B ∩ C) \ D ⊕ E	42	66	(A ∩ B) \ (C ∩ D) ⊕ E
18	32	A ∪ (B ⊕ C) \ D ∩ E	43	16	A \ (B ⊕ C ∩ D) ∪ E
19	16	A ∩ B ⊕ C ∩ D ∪ E	44	52	(A ∪ B) ⊕ (C ∩ D) \ E
20	26	(A \ B) ∪ C ∩ D ⊕ E	45	10	A ∩ B ∩ C ⊕ D ∩ E
21	10	A ⊕ B ∪ C ∩ D ∪ E	46	26	A \ (B ∩ C ∩ D) ⊕ E
22	32	(A ∩ B) \ (C ∩ D) ⊕ E	47	16	A ∪ B ⊕ C ∩ D ∩ E
23	16	A ⊕ B \ C ∩ D \ E	48	26	A ∩ (B ∪ C ∪ D) ⊕ E
24	32	A ∪ B ⊕ (C ∩ D \ E)	49	10	(A \ B) ⊕ C ∪ D ∪ E
25	10	A ∩ B ⊕ C ∩ D ∩ E	50	40	A ∪ B ∩ C ∪ D ⊕ E

1.2. Требования к отчёту

Отчёт по теме составляется по стандартной форме. В него следует поместить обоснование по выбору размера хеш-таблицы и коэффициентов хеш-функции, а также оценку временной сложности алгоритма обработки множеств — в худшем случае и в среднем. В выводах постарайтесь дать ответ на контрольные вопросы.

1.3. Контрольные вопросы

1. Какой объём памяти нужно выделять под хеш-таблицу для хранения множеств со средней мощностью 50?

2. Хеш-таблица какого типа расходует больше памяти для хранения множества — с открытой адресацией или с цепочками переполнения?

3. Каким требованиям должна удовлетворять «хорошая» хеш-функция?

4. Можно ли построить хеш-таблицу, в которой не будет коллизий?

5. Каков оптимальный алгоритм выполнения двуместной операции над множествами в хеш-таблице? Какова его временная сложность?

6. Можно ли хранить в хеш-таблице множество с повторениями?

7. Какова временная сложность операций вставки и удаления элемента для хеш-таблицы?

8. Почему для операций с хеш-таблицей дают две оценки временной сложности — сложность в худшем случае и сложность в среднем?

9. Что такое вырождение хеш-таблицы и как его избежать?

10. Что нужно делать, если хеш-таблица переполнилась?