Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Data_Structure / лекц09.ppt
Скачиваний:
35
Добавлен:
03.03.2016
Размер:
99.84 Кб
Скачать

Таблица с прямым доступом (частный случай хеш- таблицы)

K1 K2, f(K1) f(K2)

1

Обычно допускается коллизия (переполнение):

K1 K2, f(K1) = f(K2)

то есть несколько записей могут претендовать

на одну позицию в отображающем векторе

2

Методы устранения переполнений (разрешения конфликтов):

метод открытого перемешивания,

метод прямого связывания.

3

Метод открытого перемешивания

Переполняющие записи размещаются в свободных позициях отображающего вектора (в позициях вторичных индексов)

4

Занесение записи

 

 

начало

 

R – новая добавляемая

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Новая

 

запись

 

запись

 

 

 

 

 

 

 

 

 

R

 

T – отображающий вектор

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F – функция расстановки

 

 

I=f(R.key)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

I -- первичный индекс

 

 

 

 

 

 

 

 

 

 

 

 

 

T[I] занята

 

 

 

 

 

 

 

 

 

 

+ T[I]:=R

I:=Івт

конец

5

Поиск записи

 

 

 

 

начало

 

 

 

 

 

 

 

R – найденная запись

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Искомый

 

 

 

 

 

 

 

T – отображающий вектор

 

 

 

 

ключ К

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F – функция расстановки

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I=f(К)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I -- первичный индекс

 

 

 

 

 

 

 

 

 

 

 

 

-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

T[I].key<>K

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R:=T[I]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I:=Івт

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

конец

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6

Вычисление вторичного индекса

Метод линейных проб с единичным шагом

iвт = (iперв+1) mod n – первое значение iвт;

iвт = (iвт + 1) mod n – последующие значения.

7

Метод линейных проб с простым шагом p

iвт = (iперв + p) mod n – первое значение iвт;

iвт = (iвт + p) mod n – последующие значения;

p – простое число, ближайшее к n (p < n).

8

Метод квадратичных проб

i = (i

перв

+j2) mod n,

j=1,2,3…

вт

 

 

9

Метод прямого связывания (перемешивание с цепочками переполнения)

ключ

........

указатель

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

а

 

 

 

 

 

a1

 

 

 

 

a2

 

 

 

 

a3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

........

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

........

........

........

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h

........

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h1

 

 

 

 

h2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10

Соседние файлы в папке Data_Structure