Probing
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Probing as PDF for free.
More details
- Words: 344
- Pages: 5
Linear Probing – Get And Insert • divisor = b (number of buckets) = 17. • Home bucket = key % 17. 0 34 0 45
4 6
8 23 7
12 16 28 12 29 11 30 33
• Insert pairs whose keys are 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45
Linear Probing – Delete 0 34 0 45
4 6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 16 28 12 29 11 30 33
• Delete(0) 0 34
4 45
• Search cluster for pair (if any) to fill vacated bucket. 0 34 45
4 6
8 23 7
12 16 28 12 29 11 30 33
Linear Probing – Delete(34) 0 34 0 45
4
0
4 0 45
6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 16 28 12 29 11 30 33
• Search cluster for pair (if any) to fill vacated bucket. 0 0 0 0 45
4 45
6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 16 28 12 29 11 30 33
4
Linear Probing – Delete(29) 0 34 0 45
4
0 34 0 45
4
6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 28 12
16 11 30 33
• Search cluster for pair (if any) to fill vacated bucket. 0 34 0 45 0 34 0 45
4
0 34 0
4
6
8 23 7 8 23 7
12 16 28 12 11 30 33 12 16 28 12 11 30 33
6
8 23 7
12 16 28 12 11 30 45 33
6 4
0
34
6 7
23
[12]
11 12 30
28 29
[16]
33
[0]
Sorted Chains • Put in pairs whose keys are 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45 • Home bucket = key % 17.
[4]
[8] 45
4 6
8 23 7
12 16 28 12 29 11 30 33
• Insert pairs whose keys are 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45
Linear Probing – Delete 0 34 0 45
4 6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 16 28 12 29 11 30 33
• Delete(0) 0 34
4 45
• Search cluster for pair (if any) to fill vacated bucket. 0 34 45
4 6
8 23 7
12 16 28 12 29 11 30 33
Linear Probing – Delete(34) 0 34 0 45
4
0
4 0 45
6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 16 28 12 29 11 30 33
• Search cluster for pair (if any) to fill vacated bucket. 0 0 0 0 45
4 45
6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 16 28 12 29 11 30 33
4
Linear Probing – Delete(29) 0 34 0 45
4
0 34 0 45
4
6
8 23 7
12 16 28 12 29 11 30 33
6
8 23 7
12 28 12
16 11 30 33
• Search cluster for pair (if any) to fill vacated bucket. 0 34 0 45 0 34 0 45
4
0 34 0
4
6
8 23 7 8 23 7
12 16 28 12 11 30 33 12 16 28 12 11 30 33
6
8 23 7
12 16 28 12 11 30 45 33
6 4
0
34
6 7
23
[12]
11 12 30
28 29
[16]
33
[0]
Sorted Chains • Put in pairs whose keys are 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45 • Home bucket = key % 17.
[4]
[8] 45
Related Documents
Probing
November 2019 4
Probing With Haarp
June 2020 9
Hts- Ca Probing
June 2020 2
Scan Probing In Revelations
October 2019 14
