8 trang 21 lượt tải

Chaining and Linear Probing in Hashing | Môn Algorithms and Data Structures - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

41

Chaining and Linear Probing in Hashing Môn Algorithms and Data Structures. Tài liệu được sưu tầm gồm 8 trang, giúp bạn ôn tập tốt hơn. Mời các bạn đón xem. 

Môn: Algorithms and Data Structures 10 tài liệu

Trường: Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh 3.9 K tài liệu

Tác giả:

Profile

Linh Giang

2 tháng trước
Danh sách Quiz
/8
lOMoARcPSD| 58605085
M = 11. Hàm băm: h(k) = k mod M. Các khóa: 10, 22, 31, 4, 15, 28, 17, 88, 59
a) Nối kết (Chaining)
- Khóa 10: h(10) = 10 mod 11 = 10 => Chèn vào vị trí 10
Idx
Value
0
1
2
3
4
5
6
7
8
9
10
10
- Khóa 22: h(22) = 22 mod 11 = 0 => Chèn vào vị trí 0
Idx
Value
0
22
1
2
3
4
5
6
7
8
lOMoARcPSD| 58605085
9
10
10
- Khóa 31: h(31) = 31 mod 11 = 9 => Chèn vào vị trí 9
Idx
Value
0
22
1
2
3
4
5
6
7
8
9
31
10
10
- Khóa 4: h(4) = 4 mod 11 = 4 => Chèn vào vị trí 4
Idx
Value
0
22
1
2
3
4
4
5
6
7
8
9
31
10
10
lOMoARcPSD| 58605085
- Khóa 15: h(15) = 15 mod 11 = 4 => Đụng độ nên chèn vào cuối danh sách liên kết
khóa 4 ở vị trí 4
Idx
Value
0
22
1
2
3
4
4
-> 15
5
6
7
8
9
31
10
10
- Khóa 28: h(28) = 28 mod 11 = 6 => Chèn vào vị trí 6
Idx
Value
0
22
1
2
3
4
4 -> 15
5
6
28
7
8
9
31
10
10
- Khóa 17: h(17) = 17 mod 11 = 6 => Đụng độ nên chèn vào cuối danh sách liên kết
khóa 28 ở vị trí 6
Idx
Value
lOMoARcPSD| 58605085
0
22
1
2
3
4
4 -> 15
5
6
28
-> 17
7
8
9
31
10
10
- Khóa 88: h(88) = 88 mod 11 = 0 => Đụng độ nên chèn vào cuối danh sách liên kết
khóa 22 ở vị trí 0
Idx
Value
0
22
-> 0
1
2
3
4
4 -> 15
5
6
28 -> 17
7
8
9
31
10
10
- Khóa 59: h(59) = 59 mod 11 = 4 => Đụng độ nên chèn vào cuối danh sách liên kết
khóa 15 ở vị trí 4
Idx
Value
0
22 -> 0
1
lOMoARcPSD| 58605085
2
3
4
4 -> 15
-> 59
5
6
28 -> 17
7
8
9
31
10
10
b) Dò tuyến tính
- Khóa 10: h(10, 0) = (10 + 0) mod 11 = 10 => Chèn vào vị trí 10
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
10
- Khóa 22: h(22, 0) = (22 + 0) mod 11 = 0 => Chèn vào vị trí 0
-
-
- Khóa 15: h(15, 0) = (15 + 0) mod 11 = 4 => Đụng độ
Idx = (4 + 1) mod 11 = 5 => Chèn vào vị trí 5
Idx
0
1
2
3
4
5
6
7
8
9
10
Value
22
10
Khóa 31: h(31, 0) = (31 + 0) mod 11 = 9 => Chèn vào vị trí 9
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
31
10
Khóa 4: h(4, 0) = (4 + 0) mod 11 = 4 => Chèn vào vị trí 4
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
4
31
10
lOMoARcPSD| 58605085
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
4
15
31
10
- Khóa 28: h(28, 0) = (28 + 0) mod 11 = 6 => Chèn vào vị trí 6
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
4
15
28
31
10
- Khóa 17: h(17, 0) = (17 + 0) mod 11 = 6 => Đụng độ
Idx = (6 + 1) mod 11 = 7 => Chèn vào vị trí 7
-
- Khóa 59: h(59, 0) = (59 + 0) mod 11 = 4 => Đụng độ
Idx = (4 + 1) mod 11 = 5 => Đụng độ
Idx (4 + 2) mod 11 = 6 => Đụng đọ
Idx (4 + 3) mod 11 = 7 => Đụng đọ
Idx (4 + 4) mod 11 = 8 => Chèn vào vị trí 8
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
88
4
15
28
17
59
31
10
c) Dò bậc 2
- Khóa 10: h(10, 0) = (10 + 0
2
) mod 11 = 10 => Chèn vào vị trí 10
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
10
Idx
0
1
2
3
4
5
6
7
8
9
10
Value
22
4
15
28
17
31
10
Khóa 88: h(88, 0) = (88 + 0) mod 11 = 0 => Đụng độ
Idx = (0 + 1) mod 11 = 1 => Chèn vào vị trí 1
Idx
0
1
2
3
4
5
6
7
8
9
10
Value
22
88
4
15
28
17
31
10
lOMoARcPSD| 58605085
- Khóa 22: h(22, 0) = (22 + 0
2
) mod 11 = 0 => Chèn vào vị trí 0
Idx
0
1
2
3
4
5
6
7
8
9
10
Value
22
10
- Khóa 31: h(31, 0) = (31 + 0
2
) mod 11 = 9 => Chèn vào vị trí 9
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
31
10
- Khóa 4: h(4, 0) = (4 + 0
2
) mod 11 = 4 => Chèn vào vị trí 4
-
e
- Khóa 28: h(28, 0) = (28 + 0
2
) mod 11 = 6 => Chèn vào vị trí 6
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
4
15
28
31
10
- Khóa 17: h(17, 0) = (17 + 0
2
) mod 11 = 6 => Đụng độ
Idx = (6 + 1
2
) mod 11 = 7 => Chèn vào vị trí 7
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
4
31
10
Khóa 15: h(15, 0) = (15 + 0
2
) mod 11 = 4 => Đụng độ
Idx = (4 + 1
2
) mod 11 = 5 => Chèn vào vị trí 5
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
22
4
15
31
10
lOMoARcPSD| 58605085
-
- Khóa 59: h(59, 0) = (59 + 0
2
) mod 11 = 4 => Đụng độ
Idx = (4 + 1
2
) mod 11 = 5 => Đụng độ
Idx = (4 + 2
2
) mod 11 = 8 => Chèn vào vị trí 8
Idx
0
1
2
3
4
5
6
7
8
9
10
Valu
e
22
88
4
15
28
17
59
31
10
Idx
0
1
2
3
4
5
6
7
8
9
10
Value
22
4
15
28
17
31
10
Khóa 88: h(88, 0) = (88 + 0
2
) mod 11 = 0 => Đụng độ
Idx = (0 + 1
2
) mod 11 = 1 => Chèn vào vị trí 1
Idx
0
1
2
3
4
5
6
7
8
9
10
Value
22
88
4
15
28
17
31
10

Tài liệu khác của Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

Preview text:

lOMoAR cPSD| 58605085
M = 11. Hàm băm: h(k) = k mod M. Các khóa: 10, 22, 31, 4, 15, 28, 17, 88, 59
a) Nối kết (Chaining)
- Khóa 10: h(10) = 10 mod 11 = 10 => Chèn vào vị trí 10 Idx Value 0 1 2 3 4 5 6 7 8 9 10 10
- Khóa 22: h(22) = 22 mod 11 = 0 => Chèn vào vị trí 0 Idx Value 0 22 1 2 3 4 5 6 7 8 lOMoAR cPSD| 58605085 9 10 10
- Khóa 31: h(31) = 31 mod 11 = 9 => Chèn vào vị trí 9 Idx Value 0 22 1 2 3 4 5 6 7 8 9 31 10 10
- Khóa 4: h(4) = 4 mod 11 = 4 => Chèn vào vị trí 4 Idx Value 0 22 1 2 3 4 4 5 6 7 8 9 31 10 10 lOMoAR cPSD| 58605085
- Khóa 15: h(15) = 15 mod 11 = 4 => Đụng độ nên chèn vào cuối danh sách liên kết khóa 4 ở vị trí 4 Idx Value 0 22 1 2 3 4 4 -> 15 5 6 7 8 9 31 10 10
- Khóa 28: h(28) = 28 mod 11 = 6 => Chèn vào vị trí 6 Idx Value 0 22 1 2 3 4 4 -> 15 5 6 28 7 8 9 31 10 10
- Khóa 17: h(17) = 17 mod 11 = 6 => Đụng độ nên chèn vào cuối danh sách liên kết khóa 28 ở vị trí 6 Idx Value lOMoAR cPSD| 58605085 0 22 1 2 3 4 4 -> 15 5 6 28 -> 17 7 8 9 31 10 10
- Khóa 88: h(88) = 88 mod 11 = 0 => Đụng độ nên chèn vào cuối danh sách liên kết khóa 22 ở vị trí 0 Idx Value 0 22 -> 0 1 2 3 4 4 -> 15 5 6 28 -> 17 7 8 9 31 10 10
- Khóa 59: h(59) = 59 mod 11 = 4 => Đụng độ nên chèn vào cuối danh sách liên kết khóa 15 ở vị trí 4 Idx Value 0 22 -> 0 1 lOMoAR cPSD| 58605085 2 3 4 4 -> 15 -> 59 5 6 28 -> 17 7 8 9 31 10 10 b) Dò tuyến tính
- Khóa 10: h(10, 0) = (10 + 0) mod 11 = 10 => Chèn vào vị trí 10 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 10 e
- Khóa 22: h(22, 0) = (22 + 0) mod 11 = 0 => Chèn vào vị trí 0 Idx 0 1 2 3 4 5 6 7 8 9 10 Value 22 10 -
- Khóa 31: h(31, 0) = (31 + 0) mod 11 = 9 => Chèn vào vị trí 9 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 31 10 e
Khóa 4: h(4, 0) = (4 + 0) mod 11 = 4 => Chèn vào vị trí 4 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 4 31 10 e
- Khóa 15: h(15, 0) = (15 + 0) mod 11 = 4 => Đụng độ
Idx = (4 + 1) mod 11 = 5 => Chèn vào vị trí 5 lOMoAR cPSD| 58605085 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 4 15 31 10 e
- Khóa 28: h(28, 0) = (28 + 0) mod 11 = 6 => Chèn vào vị trí 6 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 4 15 28 31 10 e
- Khóa 17: h(17, 0) = (17 + 0) mod 11 = 6 => Đụng độ
Idx = (6 + 1) mod 11 = 7 => Chèn vào vị trí 7 Idx 0 1 2 3 4 5 6 7 8 9 10 Value 22 4 15 28 17 31 10 -
Khóa 88: h(88, 0) = (88 + 0) mod 11 = 0 => Đụng độ
Idx = (0 + 1) mod 11 = 1 => Chèn vào vị trí 1 Idx 0 1 2 3 4 5 6 7 8 9 10 Value 22 88 4 15 28 17 31 10
- Khóa 59: h(59, 0) = (59 + 0) mod 11 = 4 => Đụng độ
Idx = (4 + 1) mod 11 = 5 => Đụng độ
Idx (4 + 2) mod 11 = 6 => Đụng đọ
Idx (4 + 3) mod 11 = 7 => Đụng đọ
Idx (4 + 4) mod 11 = 8 => Chèn vào vị trí 8 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 88 4 15 28 17 59 31 10 e c) Dò bậc 2
- Khóa 10: h(10, 0) = (10 + 02) mod 11 = 10 => Chèn vào vị trí 10 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 10 e lOMoAR cPSD| 58605085
- Khóa 22: h(22, 0) = (22 + 02) mod 11 = 0 => Chèn vào vị trí 0 Idx 0 1 2 3 4 5 6 7 8 9 10 Value 22 10
- Khóa 31: h(31, 0) = (31 + 02) mod 11 = 9 => Chèn vào vị trí 9 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 31 10 e
- Khóa 4: h(4, 0) = (4 + 02) mod 11 = 4 => Chèn vào vị trí 4 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 4 31 10 e
- Khóa 15: h(15, 0) = (15 + 02) mod 11 = 4 => Đụng độ
Idx = (4 + 12) mod 11 = 5 => Chèn vào vị trí 5 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 4 15 31 10 e
- Khóa 28: h(28, 0) = (28 + 02) mod 11 = 6 => Chèn vào vị trí 6 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 4 15 28 31 10 e
- Khóa 17: h(17, 0) = (17 + 02) mod 11 = 6 => Đụng độ
Idx = (6 + 12) mod 11 = 7 => Chèn vào vị trí 7 lOMoAR cPSD| 58605085 Idx 0 1 2 3 4 5 6 7 8 9 10 Value 22 4 15 28 17 31 10 -
Khóa 88: h(88, 0) = (88 + 02) mod 11 = 0 => Đụng độ
Idx = (0 + 12) mod 11 = 1 => Chèn vào vị trí 1 Idx 0 1 2 3 4 5 6 7 8 9 10 Value 22 88 4 15 28 17 31 10
- Khóa 59: h(59, 0) = (59 + 02) mod 11 = 4 => Đụng độ
Idx = (4 + 12) mod 11 = 5 => Đụng độ
Idx = (4 + 22 ) mod 11 = 8 => Chèn vào vị trí 8 Idx 0 1 2 3 4 5 6 7 8 9 10 Valu 22 88 4 15 28 17 59 31 10 e

Tài liệu liên quan: