Consider a hashing scheme that uses linear probing to resolve collisions. Design
ID: 3696534 • Letter: C
Question
Consider a hashing scheme that uses linear probing to resolve collisions. Design an algorithm (no code necessary) to delete an item from the hash table. What precautions do you need to take to make it work properly? Given the following data: 25-42-96-101-102-162-197 Construct a hash table using the hash function, h(key)=key mod tablesize, where the size of the table is 11. Use the rehash function, rh(key)=(key+3) mod tablesize to resolve collisions. Construct a second hash table using the same hash function as above but use chaining to resolve collisions.Explanation / Answer
3)
a)
Deletion algorithm of linear hash function to delete an data .
Step1: Calculate the hash functin key for the given target data
Step2:Get the hash element
Step3:
If the hash element is empty, the deletion has immediately failed.
else check for a match between the target and data.
Step4: If there is a match, delete the hash element and set the flag true to indicate that the element is removed
Step5: If there is no match, probe the table until either:
Step6: An match is found between the target key and the data's key; the data can be deleted, and the deleted flag set.
b)
Precautions to delete data from linear probe:
1. Deletion of data leaves the array blank fields. The blank fields stop searching the next probing element.
2.Must set an indicator to check if the cell is Null or element is removed previously.
------------------------------------------------------------------------------------------------------------------------------------------------------
4)
Data 25, 42, 96, 101, 162, 197
Table size=11
Hashing using Linear probing
Hash function, h(key)=key mod tablesize.
Rehash if collision
rh(key)=(key+3) mod tablesize.
0
1
2
3
4
5
6
7
8
9
10
Key=25
h(25)=25%11=3
0
1
2
3
4
5
6
7
8
9
10
25
Key=42
h(25)=42%11=9
0
1
2
3
4
5
6
7
8
9
10
25
96
42
Key=96
h(25)=96%11=8
0
1
2
3
4
5
6
7
8
9
10
25
96
42
Key=101
h(25)=101%11=2
0
1
2
3
4
5
6
7
8
9
10
101
25
96
42
Key=162
h(25)=162%11=8,collision
Re-hash
h(25)=(162+3)%11=(165%11)=0
0
1
2
3
4
5
6
7
8
9
10
162
101
25
96
42
Key=197
h(25)=197%11=10
0
1
2
3
4
5
6
7
8
9
10
162
101
25
96
42
197
Hashing using Chaining
Hash function, h(key)=key mod table size.
Rehash if collision
rh(key)=(key+3) mod table size.
0
1
2
3
4
5
6
7
8
9
10
Key=25
h(25)=25%11=3
0
1
2
3
4
5
6
7
8
9
10
25
Key=42
h(25)=42%11=9
0
1
2
3
4
5
6
7
8
9
10
25
96
42
Key=96
h(25)=96%11=8
0
1
2
3
4
5
6
7
8
9
10
25
96
42
Key=101
h(25)=101%11=2
0
1
2
3
4
5
6
7
8
9
10
101
25
96
42
Key=162
h(25)=162%11=8,chaining
0
1
2
3
4
5
6
7
8
9
10
162
101
25
96
42
162
Key=197
h(25)=197%11=10
0
1
2
3
4
5
6
7
8
9
10
162
101
25
96
42
197
0
1
2
3
4
5
6
7
8
9
10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.