计算可能导致哈希表状态相同的输入序列的数量

Question

我在准备测试时遇到了这个问题。长度为10的散列表使用具有散列函数h(k)=k mod 10的开放寻址和线性探测。在一个空哈希表中插入6个值后，该表如下所示

0 |
1 |
2 | 42
3 | 23
4 | 34
5 | 52
6 | 46
7 | 33
8 |
9 |

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

(A) 10 (B) 20 (C) 30 (D) 40

解决方案中给出的答案:C

有没有人能解释一下这个答案是如何计算的？提亚

Answer 1

因为，33 mod 10 = 3并且它存储在7位置，我们知道它一定在23,34, 52 ,46之后，因此52在33之前，所以42 (相同的散列值)也是如此。我们已经确定33在序列中排在最后。

对于其余的数字，有两种情况：

(1)考虑到52在42,23,34之后(因为它们是根据它们的哈希值存储的)，可以在3中重新排列！方式。这意味着52人排在第4位，46人排在第5位。

(2)考虑到52在42,23,34,46之后，可以在4中重新排列！方式。这意味着52人排在的第5位。

因此，插入序列的总数= 4！+ 3！= 30

Answer 2

在有效的插入序列中，元素42、23和34应出现在52和33之前，46必须出现在33之前。这里不同序列的数量= 3！在上面的表达式中，x5= 30，3！表示元素42、23和34，因为它们可以以任何顺序出现，而5表示元素46，因为它可以出现在5个不同的位置。