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

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

有人可以解释一下如何计算答案吗？TIA

Answer 1

因为,33 mod 10 = 3并且它存储在第7位,我们知道它必须在23,34,52,46之后,而52之前是33,因此42(相同的哈希值)也是如此.我们已经建立了33来最后的序列.

对于其余的数字,有2种情况:

(1)考虑52来自42,23,34(因为它们根据它们的哈希值存储),可以重新排列为3!方法.这意味着52位排名第4位,46位排名第5位.

(2)考虑到52来自42,23,34,46,可以重新排列为4!方法.这意味着52名排在第5位.

因此,插入序列的总数= 4!+ 3!= 30