Hash Table (Closed Hasing/Open addressing)

1. The keys 12,18,13,2,3,23,5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h (k) =k mod 10 and linear probing. What is the resultant hash table? (2009)

(A) (B) (C) (D)

0
1
2 / 12
3 / 13
4
5 / 5
6
7
8 / 18
9
0
1
2 / 12,2
3 / 13,3,23
4
5 / 5,15
6
7
8 / 18
9
0
1
2 / 12
3 / 13
4 / 2
5 / 3
6 / 23
7 / 5
8 / 18
9 / 15
0
1
2 / 2
3 / 23
4
5 / 15
6
7
8 / 18
9

Explanation:

1.  h(12)=12mod10=2 so 12 is in 2nd position

2.  h(18)=18mod10=8 so 18 is in 8th position

3.  h(13)=13mod10=3 so 13 is in 3rd position

4.  h(2)=2mod10=2 so 2 is in 2nd position but 2nd and 3rd positions are full so it will goes to 4th position.

5.  h(3)=3mod10=3 so 3 is in 3rd position but 3rd and 4th positions are full so it will goes to 5th position.

6.  h(23)=23mod10=3 so 23 is in 3rd position but 3rd ,4th and 5th positions are full so it will goes to 6th position.

7.  h(5)=5mod10=5 so 5 is in 5th position but 5th and 6th positions are full so it will goes to 7th position.

8.  h(15)=15mod10=5 so 15 is in 5th position but 5th, 6th ,7th and 8th positions are full so it will goes to 9th position.

From the above steps 2nd to 9th positions are full it is same as the answer (C)

2. Consider a hash table of size seven, with starting index zero, and a hash function (3X+4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table with the sequence 1, 3,8,10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table. (2007)

(A) 8,_,_,_,_,_,10 (B) 1,8,10,_,_,_,3 (C) 1,_,_,_,_,_,3 (D) 1,10,8,_,_,_,3

Explanation:

H(x) = (3x+4) mod7

1.  If x=1 , 7 mod 7=0 so it is in 0th position

2.  If x=3 , 3 mod 7=6 so it is in 6th position

3.  If x=8 , 28 mod 7=0 so it is in 0th position but it is already full so it will goes to the 1st position

4.  If x=10 ,34 mod 7=6 so it is in 6th position but it is already full so it will goes to the 0th ,1st position but it is also full so it goes to 2nd place.

From the above steps (B) is the correct answer.

3. Hash table size=13 how many collisions are occur for the key 10,100,32,45,58,126,

3,29,200,400,0.

Explanation:

Table size is 13 then it is mod 13 values so

10 100 32 45 58 126 3 29 200 400 0

10 9 6 6 6 9 3 3 5 10 0

1 2 3 4 5 collisions

From the above explanation there are 5 collisions occur for the given key.

4. Which of the following is the correct Hash Function to have range from 1 to 23?

(A)  x mod 23 (B) x+1 mod 23 (C) x mod 23+1 (D) x(mod 23)+1

Explanation:

1.  For (A) H(x)=0 to 22

2.  For (B) H(x)=0 to 22

3.  For (C) H(x)=0 to 23

4.  For (D) H(x)=1 to 23

So from the above steps (D) is the correct answer.