Linear hashing

Март 10, 2021

Содержание

2. 13 29 45 8 24 32 17 2 26 43 000 001 010 011 100 38
3. 13 29 45 32 17 2 26 43 0000 001 010 011 100 38 101 110
4. 13 29 45 32 17 2 26 43 0000 001 010 011 100 38 101 110
5. 13 29 45 32 17 9 2 26 18 43 0000 001 010 011 100 38
6. 10 9 1001 13 29 45 32 17 2 26 18 43 0000 0001 010 011
7. 10 9 1001 12 28 20 13 29 45 32 17 33 2 26 18 43
8. 9 1001 12 28 20 13 29 45 32 17 33 2 18 43 27 11
9. 9 1001 12 28 20 13 29 45 32 17 33 2 18 43 27 11
10. 9 1001 12 28 20 13 29 45 32 17 33 2 18 43 27 11
12. Скачать презентацию

Слайд 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,

13 29 45 8 24 32 17 2 26 43 000 001

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

13 29 45 32 17 2 26 43 0000 001 010 011

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

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

13 29 45 32 17 2 26 43 0000 001 010 011

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)

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,

13 29 45 32 17 9 2 26 18 43 0000 001

10, 16, 7, 15, 12,
28, 33, 14, 30, 27, 31, 11, 20, 36

Linear Hashing (5)

Слайд 6

10
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 9 1001 13 29 45 32 17 2 26 18 43

10, 16, 7, 15, 12,
28, 33, 14, 30, 27, 31, 11, 20, 36

Linear Hashing (6)

Слайд 7

10
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 9 1001 12 28 20 13 29 45 32 17 33

10, 16, 7, 15, 12,
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)

9 1001 12 28 20 13 29 45 32 17 33 2

Слайд 9

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
Suchen von:
14 = 001110
26

9 1001 12 28 20 13 29 45 32 17 33 2

= 011010
19 = 010011

Aktuelle hd(x) = h3(x), dh
14 = 001110

Linear Hashing (9)

Слайд 10

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) = hd+1(x)

9 1001 12 28 20 13 29 45 32 17 33 2

= h4(x),
(da hd(x) < NextToSplit) dh
26 = 011010

Suchen von:
14 = 001110
26 = 011010
19 = 010011

Linear Hashing (10)