29 = 011101
32 = 100000
26 = 011010
38 = 100110
43 = 101011
45 = 101101
53 = 110101
?
Was passiert nun, wenn Bereich überläuft?
b = 3, NextToSplit = 0, d = 3
Linear Hashing (1)
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Linear hashing презентация
Содержание
Слайд 1
13
29
45
8
24
32
17
2
26
43
000
001
010
011
100
38
101
110
111
Einfügen mittels h3(x):
2 = 000010
8 = 001000
13 = 001101
17 = 010001
24
= 011000
29 = 011101
32 = 100000
26 = 011010
38 = 100110
43 = 101011
45 = 101101
53 = 110101
29 = 011101
32 = 100000
26 = 011010
38 = 100110
43 = 101011
45 = 101101
53 = 110101
Слайд 2
13
29
45
8
24
32
17
2
26
43
000
001
010
011
100
38
101
110
111
53
Überlaufbereich wird durch Anhängen eines
weiteren Blockes mittels einer linearen Liste
gebildet.
b =
3, NextToSplit = 0, d = 3
Linear Hashing (2)
Слайд 3
13
29
45
32
17
2
26
43
0000
001
010
011
100
38
101
110
111
b = 3, NextToSplit = 1, d = 3
53
Vergrößern des
Primärbereichs durch Hin-
zufügen eines weiteren Blockes am Ende
der Hashtabelle (Index NextToSplit wird
um 1 erhöht)
Erfordert, daß Elemente im gesplitteten Block reorganisiert werden
Erfordert, daß Elemente im gesplitteten Block reorganisiert werden
8
24
1000
Linear Hashing (3)
Слайд 4
13
29
45
32
17
2
26
43
0000
001
010
011
100
38
101
110
111
b = 3, NextToSplit = 1, d = 3
8
24
53
1000
d wird erhöht,
wenn Splitting für ur-
sprünglichen Primärbereich einmal
durchgeführt wurde, dh es gilt:
if (NextToSplit == 2d) {d++; NextToSplit = 0;}
Einfügen von Elementen mittels der Funktion hd(x), außer die Funktion führt auf einen Block, der bereits gesplittet wurde, dann hd+1(x)
if (NextToSplit == 2d) {d++; NextToSplit = 0;}
Einfügen von Elementen mittels der Funktion hd(x), außer die Funktion führt auf einen Block, der bereits gesplittet wurde, dann hd+1(x)
Linear Hashing (4)
Слайд 5
13
29
45
32
17
9
2
26
18
43
0000
001
010
011
100
38
101
110
111
b = 3, NextToSplit = 1, d = 3
8
24
1000
53
10
Einfügen von: 9,
18, 10, 16, 7, 15, 12,
28, 33, 14, 30, 27, 31, 11, 20, 36
28, 33, 14, 30, 27, 31, 11, 20, 36
Linear Hashing (5)
Слайд 610
9
1001
13
29
45
32
17
2
26
18
43
0000
0001
010
011
100
38
101
110
111
b = 3, NextToSplit = 2, d = 3
8
24
1000
53
Einfügen von: 9,
18, 10, 16, 7, 15, 12,
28, 33, 14, 30, 27, 31, 11, 20, 36
28, 33, 14, 30, 27, 31, 11, 20, 36
Linear Hashing (6)
Слайд 710
9
1001
12
28
20
13
29
45
32
17
33
2
26
18
43
27
11
0000
0001
010
011
100
7
15
31
38
14
30
101
110
111
b = 3, NextToSplit = 2, d = 3
8
24
16
1000
53
Einfügen von: 9,
18, 10, 16, 7, 15, 12,
28, 33, 14, 30, 27, 31, 11, 20, 36
28, 33, 14, 30, 27, 31, 11, 20, 36
36
Linear Hashing (7)
Слайд 8
9
1001
12
28
20
13
29
45
32
17
33
2
18
43
27
11
0000
0001
0010
011
100
7
15
31
38
14
30
101
110
111
b = 3, NextToSplit = 3, d = 3
8
24
16
1000
53
36
26
10
1010
Linear Hashing (8)
Слайд 99
1001
12
28
20
13
29
45
32
17
33
2
18
43
27
11
0000
0001
0010
011
100
7
15
31
38
14
30
101
110
111
b = 3, NextToSplit = 3, d = 3
8
24
16
1000
53
36
26
10
1010
Suchen von:
14 =
001110
26 = 011010
19 = 010011
26 = 011010
19 = 010011
Aktuelle hd(x) = h3(x), dh
14 = 001110
Linear Hashing (9)
Слайд 109
1001
12
28
20
13
29
45
32
17
33
2
18
43
27
11
0000
0001
0010
011
100
7
15
31
38
14
30
101
110
111
b = 3, NextToSplit = 3, d = 3
8
24
16
1000
53
36
26
10
1010
Aktuelle hd(x) =
hd+1(x) = h4(x),
(da hd(x) < NextToSplit) dh
26 = 011010
(da hd(x) < NextToSplit) dh
26 = 011010
Suchen von:
14 = 001110
26 = 011010
19 = 010011
Linear Hashing (10)
Слайд 11
9
1001
12
28
20
13
29
45
32
17
33
2
18
43
27
11
0000
0001
0010
011
100
7
15
31
38
14
30
101
110
111
b = 3, NextToSplit = 3, d = 3
8
24
16
1000
53
36
26
10
1010
Aktuelle hd(x) =
h3(x), dh
19 = 010011
19 = 010011
Suchen von:
14 = 001110
26 = 011010
19 = 010011
! ERFOLGLOS !
Linear Hashing (11)
