java - 如何计算构建哈希表所需的最大/最小探针数

Question

我目前正在学习 Robert Sedgewick 和 Kevin Wayne 合着的算法第四版，我被困在其中一个练习中。我知道有人在 GitHub 上发布了本书中许多练习的解决方案，但我想自己做这些，以便我可以理解并从中学习。

我一直在浏览这本书，了解如何计算构建哈希表所需的最大/最小探针数(练习 3.4.12)，但我找不到任何方法/函数/公式来说明如何计算处理这样的问题时才能前进。

练习:

Suppose that the keys A through G, with the hash values given below, are inserted in some order into an initially empty table of size 7 (= m) using a linear-probing (when there's a collision ew just check the next entry in the table by incrementing index) table (with no resizing for this problem)

key = "A B C D E F G"

hash = "2 0 0 4 4 4 2"

Which of the following could not possibly result from inserting these keys?

a) E F G A C B D

b) C E B G F D A

c) B D F A C E G

d) C G B A D E F

e) F G B D A C E

f) G E C A D B F

我找到了这个网站 http://orion.lcg.ufrj.br/Dr.Dobbs/books/book2/algo02e5.htm ，但我无法理解其中的大部分内容。当我试图解决这个问题时，我不知道该怎么做，首先我以为我误解了这个问题，或者我根本找不到如何解决这个练习的公式。

如何计算构建大小为 m 的表可能需要的最大和最小探测数？

Answer 1

我认为这个问题没有特定的公式。 您需要查看每个订单，并决定该订单是否有可能实现。

让我们一起看一下 (a):E F G A C B D。

如果我们用哈希值替换键，我们将得到 4 4 2 2 0 0 4。现在重要的部分 - 请注意，只有 G 位于“右”桶中，所有其他值都因线性探测而移动。那可能吗？

假设我们首先插入了 G 并将其写入索引 2。现在怎么办？如果我们插入一个散列为 0 或 4 的键，它将被放置在单元格 0 或 4 中而不进行探测，这不是我们想要的。唯一的选择是现在插入 A，它的哈希值也是 2。它会去哪里？索引 3 当然是由于线性探测。到目前为止一切顺利，我们的数组如下所示:X X G A X X X

现在怎么办？我们只剩下散列为 0 或 4 的键，一旦我们插入一个这样的键，它将被放置在单元格 0 中或 4。但是在我们被询问的模式中，所有具有散列 0 和 4 的值都不在“正确的”单元格中。因此，这种模式是不可能的。

现在让我们看看 (b)。顺序是 C E B G F D A，转换为 0 4 0 2 4 4 2。我们如何创建这种模式？

让我们插入 C:C X X X X X X 现在怎么办？让我们插入 F:C X X X F X X。现在让我们插入 D。由于线性探测，我们将以 C X X X F D X 结束。现在怎么办？我们被困住了。不管我们现在插入什么，我们都无法到达 C E B G F D A。有什么我们可以改变我们以前的插入以获得不同的结果吗？不能。因此，(b)也是不可能的。