问题标签 [linear-probing]

我正在为我的数据结构课程做作业。我们被要求研究负载系数为 0.1、.2、.3、.. 和 .9 的线性探测。测试公式为：

使用线性探测的平均探针长度大致为

成功--> (1 + 1/(1-L)**2)/2
或
失败--> (1+1(1-L))/2。

我们需要使用上面我所做的公式找到理论值（只需在公式中插入负载因子），然后我们必须计算经验值（我不太确定该怎么做）。这是其余的要求

**对于每个负载因子，10,000 个随机生成的介于 1 和 50000（含）之间的正整数将插入到“正确”大小的表中，其中“正确”严格基于您正在测试的负载因子。允许重复。确保您的随机生成整数的公式是正确的。在 java.util 中有一个名为 Random 的类。用它！在正确（基于 L）大小的表加载 10,000 个整数后，对新生成的 1 到 50000 范围内的随机整数进行 100 次搜索。计算两个公式中每一个的平均探针长度并指出使用的分母例如，在每个计算中，对于 0.5 负载的每个测试都会有一个 > > 大小约为 20,000（调整为素数）的表格，类似地，对于 .5 负载的每个测试。

程序应运行显示测试的各种负载因子、每次搜索的平均探针（用于计算平均值的两个分母将相加为 100）以及使用上述公式的理论答案。.**

我如何计算经验成功率？

到目前为止，这是我的代码：

}

在线性探测中，有一个称为特殊值的值AVAILABLE，它会在删除项目时被替换。

当您插入一个键时，您会寻找一个空单元格（这只是意味着该单元格是null？）或包含的一个，AVAILABLE我不明白的是，如果空单元格意味着null而不是具有特殊值AVAILABLE，为什么不只是制作细胞null？

与使用相比有什么优势AVAILABLE？

所以我在这里有一个 HashTable 实现，我只使用 Arrays 编写了它，并且对代码有一点帮助。不幸的是，我不太理解有人在运行“get”或“put”方法时添加的其中一行。下面的while循环到底发生了什么？这是一种线性探测的方法正确吗？另外为什么循环检查它正在检查的条件？

具体来说，

下面是整个 Java 类，以供完整参考。

谢谢你。

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

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

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

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

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

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

在过去的几天里，我很困惑在我正在阅读的教科书中找到哈希冲突管理主题中主集群和次集群之间的区别。

    我正在做数据结构实践中的一个练习题

问题
   1.Linear Probing 将（圈出一个）：
        i.随着插入更多值，性能会逐渐降低
       ii.可能在下一次插入时找不到位置
       iii.以上都不是

   2.二次探测将（圈一个）：
        i.随着插入更多值，性能逐渐降低
       ii.可能在下一次插入时找不到位置
       iii.以上都不是

根据答案键（来自链接），1 的答案是 i，2 的答案是 ii。

我同意问题 1 的答案。线性探测将探索所有可能性，并在需要时回绕到哈希表的开头。因此它将在下一次插入时找到一个位置。如果您插入一堆映射到同一个存储桶或靠近一个存储桶的值，则会导致聚类并降低性能。
我明白为什么问题 2 的答案不是 i。二次增量概率通过不同的增量来避免聚类问题。然而，有些人可以解释二次探测“可能在下一次插入时找不到位置”背后的直觉吗？
二次探测函数定义为（来自二次探测）
第 n 个探针为 ((h(k) + n ² ) mod TableSize) 直到探头达到零（未占用）

根据我在另一个问题Quadratic Probing中学到的知识，二次探针有可能击中每个桶。与线性探针一样，如果需要，二次探针也应该包含在哈希表的开头。那么为什么在这个问题中，二次探针不能在下一次插入时找到位置，而线性探针可以呢？

我正在尝试使用线性探测冲突解决方法为我的哈希表编写一个正确的删除函数。

我运行了一个测试器，它从我的哈希表中删除了几条记录。在某些时候，我的查找功能找不到要删除的元素。但是，它应该仍在桌子上。我认为我正在以错误的方式在 remove() 中进行重新散列。

类HashTable包含 member table，一个类型的结构数组Record

这也是我的查找功能，它似乎工作正常，但我可能是错的

你能帮我确定我是否以正确的方式进行线性探测吗？

我正在制作一个带有一个 String 数组一维和一个二维 int 数组的哈希表。我正在使用线性探测来进行碰撞检测，当我意识到如果检测到碰撞时，这个词的 hashCode 将不再是索引。我将如何保存该索引以供以后使用？

我正在编写只需要整数的双哈希表。

并尝试使用 SetData() 将数据插入表中

将 100 个整数项放入大小为 100 的表中后，表显示一些索引留空。我知道，这将需要 O(N) ，这是最坏的情况。我的问题是，即使需要最坏的搜索时间，项目也应该插入没有空白空间的表中，对吗？我找不到我的功能的问题。

附加问题。有众所周知的哈希算法，双重哈希的目的是尽可能减少冲突，H2（T）是H1（T）的备份。但是，如果众所周知的哈希算法（如 MD5、SHA 等，我不是在谈论安全性，只是众所周知的算法）更快且分布良好，为什么我们需要双重哈希？

谢谢！

我试图找出给定列表中的哪个索引会在将该索引分配到哈希表之前提供最大数量的探测。我有一个看起来像这样的列表：

[4, 9, 12, 3, 7, 26, 16, 20, 11]

我需要弄清楚该列表中的哪些值创建了最长的探测序列。我已经坚持了很长一段时间了，任何帮助都将不胜感激。