哈希表:哪个是正确的线性探测数组？

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

注意问题如何没有指定插入键的顺序，所以您的答案是正确的，前提是键实际上是按顺序插入的，但是由于问题没有明确说明顺序，所以您需要更深入地研究。

然而，您所知道的是，其中一个键将首先插入，并将进入其指定的插槽，如键到哈希图所示，因为哈希表最初是空的。这将立即丢弃选项2，因为没有一个键位于指定的数组条目中，因此您需要选择1和3。

对于表1，B位于与其哈希值对应的槽1中，对于表3，F和A键位于其初始哈希值位置。

很容易证明，插入F和A后，表3上的密钥插入序列不会产生表3。同样容易证明密钥插入序列B-D-F-A-C-E-G将导致表1中的结果。

虽然这是一个基于哈希表的问题，但老实说，我并不认为它是评估线性探测知识的好方法，这更像是一个谜，@gnasher729已经提到了。