Data Structures
- Hashing
A hash table implementation uses function of (% 7) and linear probing
to resolve collision. What is the ratio of numbers in the following
series with out collision and with collision if 7 buckets are used:
32, 56, 87, 23, 65, 26, 93
Options
1. 2,5
2. 3,4
3. 4,3
4. 5,2
Ans: 3
Explanation:
Since we're using mod 7 hash function, we've a hash table with
7 buckets numbered from 0 to 6. Any number x will be mapped
to x % 7 bucket.
Lets look at the insertion of sequence into hash table:
1. 32 is inserted into 32 % 7 = 4 i.e. 4th bucket.
2. 56 is inserted into 56 % 7 = 0 i.e. 0th bucket.
3. 87 is inserted into 87 % 7 = 3 i.e. third bucket.
3A
4. 23 is inserted into 23 % 7 = 2
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
|
23
|
87 |
32 |
|
|
5. 65 is inserted 65 % 7 = 2. Since bucket 3 also contains
23, its a collision. We'll put 65 into the next empty bucket i.e.
5
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
|
23
|
87 |
32 |
65
|
|
6. 26 is inserted into 26 % 7 = 5. However, since bucket
5 is also full, its a collision and 26 is inserted into the next empty
bucket i.e. 6.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
|
23 |
87 |
32 |
65
|
26
|
7. 93 is inserted into 93 % 7 = 2. However, since bucket
2 is also full, its a collision and 93 is inserted into the next empty
bucket i.e. 1.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
93
|
23
|
87 |
32 |
65 |
26 |
Final position of buckets will be:
| Bucket # |
Element |
Remark |
| 0 |
56 |
|
| 1 |
93 |
|
| 2 |
23 - 65 - 93 |
|
|
65 ( move to next empty - 5) |
Collision |
|
93 ( move to next empty - 1) |
Collision |
| 3 |
87 |
|
| 4 |
32 |
|
| 5 |
65 - 26 |
|
|
26 (move to next empty - 6) |
Collision |
| 6 |
26 |
|
|