Курсовая работа: Хэш поиск

В данной курсовой работе мы посмотрим открытое хэширование.

2.2.Открытое хэширование.

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

индекс	ключ	указатели
1	ai h(ai)=1	aj, h(aj)=1 at, h(at)=1 af, h(af)=1 начало конец
2	nil nil
3	as h(as)=3	nil nil
4	ak h(ak)=4	ar, h(ar)=4 начало конец
…	…
m	nil nil

Алгоритмы построения и поиска хэш таблицы.

Построение:

· Находим значение хэш функции и по этому значению входим в таблицу

· Если она пустая, то записываем в нее ключ

· Если она занятая, то сравниваем ключ с заданным ключом:

1. если ключи совпадают, то обрабатываем повторный ключ

2. иначе добавляем новый ключ в конец списка