3,255 views
10 votes
10 votes

Consider an initially empty hash table of length 10. Following are the keys in hash table inserted using mod function h(k)=k mod 10.

Slot Number Value
0  
1 91
2  
3 33
4 44
5 23
6 64
7 77
8  
9  

How many different insertion sequences of keys would result in the above hash table?

My answer comes to be 56, is it correct?

1 Answer

5 votes
5 votes

Total number of elements = 6

1) In the given table, 23 should be stored at 23mod10 which is equal to 3.

But because of 3 being occupied, it goes to the next value which is 4. Again because of being occupied it is stored at 5.

Therefore, 23 must be in the sequence after 33 and 44.

2) Similarly considering 64, it should be in the sequence after 44 and 23.

3) 91 and 77 can be anywhere in the sequence. Therefore, the total possible positions of 91 and 77 are (6C2)*2! = 30

4) The remaining 4 positions should be in the following order:

33 44 23 64 or

44 33 23 64

2 combinations are possible.

5) Therefore the number of different sequences that would give the resulting table = 30*2 = 60

Answer:

Related questions

1 votes
1 votes
0 answers
1
ankitgupta.1729 asked Nov 9, 2017
1,000 views
5 votes
5 votes
3 answers
2
mcjoshi asked Aug 30, 2016
5,504 views
Keys $9,19,29,39,49,59,69$ are inserted into a hash Table of size $10$ $(0-9)$ using the hash function $H = k mod 10$ and Quadratic Probing is used for collision resoluti...
0 votes
0 votes
1 answer
3
tishhaagrawal asked Dec 16, 2023
309 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...