Недостатки

►если множество ключей велико, то хранить в памяти массив T размером | U| непрактично и не возможно иногда.

►Если число реально присутствующих в таблице записей мало по сравнению с мощностью U , то много памяти

тратится зря

►требуются механизмы разрешения коллизий

Коллизии

►Ситуация, когда для различных ключей получается одно и то же хэш-значение, называется коллизией (collision).

Разрешение коллизий

►1. Способ обработки коллизий с помощью цепочек

►2. Открытая адресация

цепочки (chaining)

►элементы множества, которым соответствует одно и то же значение хэш, связываются в цепочку список

►В строке таблицы H c номером j хранится не сам элемент, а указатель на голову списка тех

элементов, у которых хэш-значение ключа равно j , если нет то NULL

Сложность основных

алгоритмов

►Insert(вставка)- имеет сложность О(1)

► Search(поиск по ключу) - сложность зависит от длины списка и равна O(a), где a = n/m –максимальное количество

элементов в цепочке близнецов

( коэффициент заполнения)

►Delete(удаление по ключу) –

временная сложность совпадает с алгоритмом Search

Хэш-функции

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

►p(key)- плотность распределения запросов ключей

►плотность распределения запросов входов таблицы g(H(key))

Пример

►множество ключей {0, 1, 4, 5, 6, 7, 8,

9, 15, 20, 30, 40}

►таблица допускает всего 4 входа.

►h(key) = key%4

key	0 1	4	5	6	7	8	9	1	2	3	40
	0 1	0	1	2	3	0	1	5	0	0	0
h(key								3	0	0
)

Пример

Номер входа	0	1	2	3
Максимальная	6	3	1	2
длина цепочки

Номер	0	1	2	3
входа	50	25	8	17
%

обращений

Пример

3x0,5+1,5x0,25+0,5x0,08+1x0,17 ≈ 2,1