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.

0	1	2	3	4	5	6
				32

2. 56 is inserted into 56 % 7 = 0 i.e. 0th bucket.

0	1	2	3	4	5	6
56				32

3. 87 is inserted into 87 % 7 = 3 i.e. third bucket.

0	1	2	3	4	5	6
56			87	32

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