Добавил:
alyonka_stepashka
ПОИТ 2016-2020
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Пустовалова 2 сем / Лекции / Лекция 9_Хэш.ppt
X
- •ХЭШ-ТАБЛИЦЫ
- •► хэш-таблица — это динамическое
- •Назначение
- •поиск в хэш
- •Хэш-функции
- •►Множество M разбивается на N непересекающихся подмножеств, занумерованных индексами от 0 до N
- •свойства хэш-функций
- •Модульное хэширование
- •// модульное хэширование
- •пример
- •Мультипликативный метод
- •пример
- •Аддитивный метод
- •Универсальное
- •мультипликативное
- •// грубый генератор
- •Адресация
- •Прямая адресация
- •►ключи
- •Недостатки
- •Коллизии
- •Разрешение коллизий
- •цепочки (chaining)
- •Сложность основных
- •Хэш-функции
- •Пример
- •Пример
- •Пример
- •Пример 2
- •Открытая адресация
- •Алгоритм Insert (T, x)
- •►последовательность просматриваемых ячеек вычисляется, т.е. зависит от ключа
- •Алгоритм Search(T, key)
- •алгоритм Delete(T,key)):
- •Способы вычисления последовательности испробованных мест при открытой адресации
- •Пример
- •недостаток - приводит к образованию кластеров
- •2. Квадратичный
- •3. Двойное хеширование
- •►пример
- •Реализация
- •//----------------найти по ключу, вернуть индекс в таблице
- •Исследование времени
- •эффективность
- •►Пример
- •Коллизия
►Пример
►ASCII -> 0x41 .. 0x7A
►A 0x41 = 65 ►Z 0x7A = 90
►F(key)=S +((key[0]-65)x262+ +((key[1] -65)x26
+(key[2]-65)) XR
S |
AAA |
|
S+R |
||
AAB |
||
|
||
S+(262x1+26x1+2)R |
BBC |
|
|
||
S+(262x25+26x25+2 |
ZZZ |
|
5)R |
R |
|
|
►S=1000
►R=15
►B=66 C=67
►F(BBC)=F(666667)=1000+( 262+26+2)x15=11560
►F-1(s)=[(s-S)/R/ 262]+65||[(((s-S)/R% 262)/26] +65||((s-S)/R)% 262%26+65
►F-1(s)=[(11560-1000)/15/ 262]+65|| [(((11560 -1000)/15% 262)/26] +65||((11560 -1000)/15)% 262%26+65=66||66||67=BBC
►h(key)=f(key)%2000 ►H(BBC)=11560
►H(EAA)=H(GYW)=11560
►H(ZZZ)=H(CIP)=24625
Коллизия
Образование цепочек
S
AAA
H(key) |
AAC
BBC |
EAA |
ZZZ |
CIP |
S+R*max(h(key)) |
|
Соседние файлы в папке Лекции