Hashing with Linear probing

Question

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?

Comments

@shubham6596 we will first see which insertions in the hash table are depending upon the other insertions and then insert. Those who do not depend can come at any time. Check my ans for solution and correct me if I am wrong.

---

@anjali007  I got it now, Thanks 

---

See first of all (33,34) they must appear before (23,64) in any order either (33,34) or (34,33) → 2 ways.

23 must appear before 64 so sequence can be 33,34,23,64 or 34,33,23,64.→ 1 ways.

for 77 or 97 there are 5 places → first, last and between digits total 5 places. → 5 ways.

after insertion one of 77 or 97, for the second number we 6 places first, last and between digits total 6 places.→ 6ways.

Result = 2*1*5*6 = 60.

Answer 1

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