哈希表中键值的不同插入顺序的数量

Question

长度为10的散列表使用具有散列函数h(K)=kmod10的开放寻址和线性探测。在一个空哈希表中插入8个值后，该表如下所示

0 |
1 | 91
2 | 2
3 | 13
4 | 24
5 | 12
6 | 62
7 | 77
8 | 82
9 |

使用相同的散列函数和线性探测的键值的多少个不同的插入序列将产生上面所示的散列表？

答案- 128。

我知道91,2,13,24,77的5！= 120，但我不知道其他8个组合是什么？

Answer 1

给出的答案是错误的，实际上这是一个模拟测试，来源提供的答案是错误的。真正的答案是168。

它可以通过两种方式来完成-

1) 91,2,13,24,12,62,77,82 -如果您查看并过滤掉详细信息

  _,91,_,2_,13,_,24,_,12,_,62,_,82 

在所有可用的空缺中，我们可以填补77个空缺，它总是会导致第7个位置，所以总共有77个途径-- 7个位置中的任何一个。

现在91,2,13,24可以以任何顺序出现，并且可以按照上面的方式进行安排，所以总共有4种方式！对于这四个人中的每一个！排列77可以来自这7个位置中的任何一个，所以答案是- 4!*7 = 168。

2)第二种方法是-只有3种可能的序列

一) 91,2,13,24,77,12,62,82

 Here 91,2,13,24,77 can come in any order, They will get there respective 
 slots so total 5! ways.

二) 91,2,13,24,12,77,62,82

  Here 91,2,13,24 can come in any order and we have fixed 77 after 12 so total 
  4! ways.

三) 91,2,13,24,12,62,77,82

   same here with 4! ways 91,2,13,and 24 can come and 77 is fixed after 62.

所以总共5!+4!+4!=168。