- •Таблица с прямым доступом (частный случай хеш- таблицы)
- •Обычно допускается коллизия (переполнение):
- •Методы устранения переполнений (разрешения конфликтов):
- •Метод открытого перемешивания
- •Занесение записи
- •Поиск записи
- •Вычисление вторичного индекса
- •Метод линейных проб с простым шагом p
- •Метод квадратичных проб
- •Метод прямого связывания (перемешивание с цепочками переполнения)
- •Достоинства хеш таблиц:
- •Недостатки хеш таблиц:
- •Внешние структуры данных
- •Основные аспекты современной человеческой деятельности:
- •Методы и средства реализации этих задач – основа для создания информационных систем, предназначенных
- •Два поколения АИС:
Таблица с прямым доступом (частный случай хеш- таблицы)
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