问题标签 [quadratic-probing]

我当前的哈希表实现是使用线性探测，现在我想转向二次探测（后来也转向链接，也许还有双重哈希）。我已经阅读了一些文章、教程、维基百科等……但我仍然不知道我应该做什么。

基本上，线性探测的步长为 1，这很容易做到。在哈希表中搜索、插入或删除元素时，我需要计算一个哈希值，为此我这样做：

然后，在搜索、插入或删除时，我循环遍历表，直到找到一个空闲的存储桶，如下所示：

至于二次探测，我认为我需要做的是改变“索引”步长的计算方式，但这就是我不明白我应该怎么做的。我见过各种各样的代码，它们都有些不同。

此外，我还看到了一些二次探测的实现，其中散列函数被更改以适应它（但不是全部）。是否真的需要这种更改，或者我可以避免修改散列函数并仍然使用二次探测？

编辑： 阅读下面 Eli Bendersky 指出的所有内容后，我想我明白了。这是http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx的部分代码：

有两件事我没有得到......他们说二次探测通常使用c(i)=i^2. 然而，在上面的代码中，它做的更像是c(i)=(i^2-i)/2

我已准备好在我的代码上实现这一点，但我只会这样做：

...并不是：

如果有的话，我会这样做：

...因为我已经看到其他代码示例跳水了两个。虽然不明白为什么...

1）为什么要减去步骤？
2）为什么它会跳水2？

我真的需要帮助插入哈希表。我现在还没有完全明白。有人可以用外行的术语解释二次和线性探测吗？

这是我正在处理的代码。我不是要任何人去做，我只是真的需要帮助来学习整个概念

任何帮助将不胜感激。

这是一个家庭作业问题，但我认为它缺少一些东西。它问：

提供一个由m个键组成的序列来填充一个使用线性探测实现的哈希表，从而使填充它的时间最短。

进而

提供另一个m键序列，但要使填充它的时间最大。如果哈希表实现二次探测，重复这两个问题

我只能假设哈希表的大小为m，既因为它是唯一给出的数字，又因为我们在描述负载因子之前一直使用该字母来解决哈希表大小。但是如果不知道将序列散列到表中的散列函数，我想不出任何序列来做第一个。

如果它是一个糟糕的哈希函数，例如，它将每个条目哈希到同一个索引，那么填充它的最小和最大时间都将花费 O(n) 时间，而不管序列是什么样的。在平均情况下，我假设散列函数没问题，我怎么知道该散列函数填充表需要多长时间？

这些问题与散列函数的关联是否比与散列序列的关联更强？

至于第二个问题，我可以假设，不管散列函数如何，一个大小为m且具有相同键重复m次的序列将提供最大时间，因为它将导致从第二个条目开始的线性探测。我认为这需要 O(n) 时间。那是对的吗？

我最近一直在学习哈希表。有几个碰撞解决方案的例子，其中之一是二次探测。为什么有人会使用二次探测？他知道哈希表总是不到一半吗？如果是这样，他为什么一开始就使用这么大的桌子？

我在区分二次和线性探测算法时遇到问题。当我阅读概念性解释时，我看到 I^2 被反复添加到最后一次尝试的索引中。这是怎么回事？线性探测会把它变成什么？从我正在阅读的内容来看，下面的方法实现了二次探测。

对于给定的哈希值，线性探测生成的索引如下：

h, h+1, h+2,h+3等..

对于给定的哈希值，二次探测生成的索引如下：

h, h+1, h+4,h+9等..

在线性的情况下会形成簇，但在二次的情况下不会。

但是，当两个过程（方法）都需要采取相同数量的插入或搜索步骤时，为什么二次比线性更有效。谢谢！

假设我有一个包含 59 个元素的哈希表（每个元素值都是一个整数）。索引 15 是空白的，表的其余部分都是数据。根据我要插入的数字，二次探测公式永远不会达到元素 15！

假设我想插入数字 199（应该使用我在下面使用的 hashFunc() 函数散列到 22。：

在什么负载系数下，线性探测与二次探测一样好？二次方什么时候开始胜出？

我正在使用二次探针实现一个开放哈希表。我的数据库是 java String[] （我的对象仅限于 strings）。对于删除，我使用延迟删除，但我想真正有效地实现它。我确信有比持有一组全新的标志（活动/空/已删除）更优雅的解决方案。

我想在删除时分配一些已知的常量字符串（例如“”，空字符串），并在需要时将单元格内容与该字符串本身的指针进行比较（使用 == 而不是 String.equals）。这样我就知道单元格已被删除，但活动单元格可以保存任何类型的字符串（包括空字符串），因为它永远不会指向我们的常量字符串。

我的想法有问题吗？

我正在尝试创建一个使用模板的哈希图。在探测和探测的情况下，模板将接受一个哈希函数（hash (int key, int size) 的形式）和一个探测函数（probe (int i) 的形式）（int key, int size）在双重哈希的情况下。我希望你明白我在说什么。这是我的主要内容：

如您所见，我传入了两种不同的指针函数类型作为探测函数。在双重哈希的情况下，“Hash2”将作为探测函数传入。这是我的头文件中的一个片段（即我的类声明、节点声明和插入方法：

我的插入方法中的“double_hash_”条件的“else”部分标记了一个错误，因为我当然是在使用两个不同的参数号调用同一个探针、模板函数。我不是在问为什么它会抛出错误，因为我已经知道为什么。我正在寻求解决方案 - 或解决方法。谢谢。