Hash Table：哪个是正确的线性探测数组？

Question

我现在正在研究特定哈希表中的数据结构。我遇到了以下问题：

Imagine that we have placed the following keys 
in an initial empty hash table with a length of 7
with linear probing, using the following table of hash-values:

key:    A B C D E F G
hash:   3 1 4 1 5 2 5

Which of the following arrays could be the linear-probing array?

1.
0 1 2 3 4 5 6
G B D F A C E

2.
0 1 2 3 4 5 6
B G D F A C E

3.
0 1 2 3 4 5 6
E G F A B C D

当我创建线性探测阵列时，我得到了这个：

0 1 2 3 4 5 6
G B D A C E F

有人能告诉我为什么我错了，正确答案是什么？

Answer 1

请注意问题如何没有指定键的插入顺序，因此您的答案只有在假定键实际以 A-B-C-D-E-F-G 的顺序插入的情况下才是正确的，但是由于问题没有明确说明订单，你需要深入挖掘。

然而，您知道的是，其中一个键将首先插入，并且它将进入其指定的槽，如键到哈希图中所示，因为哈希 table 是最初是空的。这会立即放弃选项选项 2，因为 none 个键在它们指定的数组条目中，留下选项 1 和 3。

对于 table 1，B 在槽 1 中，对应于它的哈希值，对于 table 3，键 F 和 A处于其初始哈希值位置。

很容易证明在插入 F 和 A 之后在 table 3 上插入的键序列不会产生 table 3 作为结果。同样容易证明键插入序列 B-D-F-A-C-E-G 将导致 table 1.

尽管这是一个基于散列 table 的问题，但老实说，我认为这不是评估您的线性探测知识的好方法，这更像是一个难题，正如 @gnasher729 所提到的。

Hash Table：哪个是正确的线性探测数组？

Hash Table: Which is the right linear-probing array?

arrays

hash

hashtable