时间戳

首页 > 解决方案 > 哈希表中不同Key值插入序列的数量

hash - 哈希表中不同Key值插入序列的数量

问题描述

长度为 10 的散列表使用散列函数 h(k)=k mod 10 和线性探测的开放寻址。将8个值插入一个空的hash表后，表如下图

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 种组合是什么？

标签： hashhashtablepermutationinsertionlinear-probing

解决方案

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

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

1) 91,2,13,24,12,62,77,82 - 如果您看到并过滤掉详细信息，请点击此处

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

在我们可以填补 77 的所有可用空白中，它总是会导致第 7 个插槽，因此 77 可以出现的方式总数 - 7 个位置中的任何一个，即 7 个​​。

现在 91,2,13,24 可以按任何顺序排列，并且可以按上述方式排列，总共有 4 种！并且对于 4 中的每一个！安排 77 可以出现在 7 个地方中的任何一个，所以答案是 - 4!*7 = 168。

2）第二种方式是 - 只有3个可能的序列

i) 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.

ii) 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.

iii) 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。

推荐阅读