问题标签 [quadratic-probing]

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

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

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

除了使用迭代器之外，我创建了一个模仿 stl 映射的哈希映射类。所以，现在我的问题是遍历哈希映射，不使用迭代器，并打印出与某个键关联的值。类本身是模板化的，但 main.cpp 中使用的 Value 是字符串向量。我将如何制作一个打印功能来打印与键关联的项目（值）？我尝试编写一个 printElements() 函数，但它只打印密钥。先感谢您。

这是我的哈希映射类：

};

这是主要使用的代码：

}

在我检查负载因子是否指示要调整大小的后备阵列之后，我实际上如何通过二次探测来调整大小？

这是代码。这只是课堂的一部分。另外，你能检查一下我是否正确地实现了 add 方法吗？

我正在学习哈希表和特别是二次探测。我已经读过，如果负载因子 <= 0.5 并且表的大小是素数，则二次探测将始终找到一个空槽，并且不会多次访问任何键。然后继续说，为了确保有效插入，我应该始终保持负载因子 <= 0.5。这是什么意思？当然，如果我们继续添加项目，无论我们是否愿意，负载因子都会增加直到等于 1。那么当我的教科书说我应该保持一个小的负载因子时，这意味着什么？

需要一个例子

我需要给出表格的大小和我尝试插入的元素，在表格超过半满后由于碰撞而无法插入。

我在表大小上尝试了一些不同的输入，函数为： h of i (x) = (hash(x) + f(i)) mod table size

f(i)= i^2

我会很感激任何帮助谢谢。

我的 AP 计算机科学课程最近了解了哈希表以及线性探测如何导致聚类问题，结果证明并不是真正的恒定时间插入/搜索。我们的讲师告诉我们，由于显而易见的原因，二次探测将是减少聚类的好方法。我想知道是否有可能如果只剩下一个元素，那么二次探测需要一段时间才能找到它。我写了一个快速程序（如果你愿意，我可以插入源代码，但我认为无论如何都不会有人阅读它）测试是否发生这种情况。

首先，我证明了如果没有永远不会登陆的数组索引，那么如果你总是尝试添加到任何一个索引，它就会被找到。这是因为通过这样做，它最终会命中数组中的每个索引，或者不会。如果二次探测命中每个索引，那么您可以在任何点选择任何索引并且它总是会结束，因此长度数组总是有效的。如果它不能击中每一个实例，你就会发现你不能这样做。

然后，我创建了一个我感兴趣的任何长度的布尔数组，如果索引 0 不为真，则将其设置为真，否则将索引 1%length 设置为真，否则将索引 4%length 设置为如果不是，则为 true ...否则将 index n%length 设置为 true，如果不是...

我没有检查 1 个前锋和 1 个后退，但正如您将看到的那样，这首先无关紧要。

因此，在四个元素的数组中，二次探测将找到索引 0 和 1，但（在大约 46000^2 % 长度内）从未到达索引 2 或 3。如果我也向后走，它会找到索引 3 (((0-1)%4+4)%4==3)，但仍然不是索引 2。

经过一番思考，我发现我正在寻找是否存在任何一对数字 x 和 n，其中 x 和 n 都是整数，其中以下等式的计算结果为真：

也就是说，任何整数的 4 倍以上是平方数。

如果对于所有整数 x 和 n 都可以证明没有任何对会导致该结果为真，则意味着二次探测永远不会到达长度为 4 的数组中的索引 2。

我认为这与说抛物线是一回事：

不包含 (x, y) 对，其中 x 和 y 都是整数，但我不完全确定。

我刚刚花了两个小时来解决这个问题，这就是我能够弄清楚的全部。

我知道有时二次探测找不到位置。那不是我感兴趣的。我将如何证明这将永远行不通，或者如果我使用足够大的数字，这将最终终止。此外，如果您可以将数学保留在您在 BC 微积分中学习的内容中，那就太好了。

非常感谢！

你好，由于某些原因，我无法在插入时让我的哈希表填充项目和键。通过驱动程序运行时似乎正在添加它，但没有存储任何内容，并且绝对没有错误消息。我想创建一个利用二次探测的哈希表。我想计算不能> 20的横向数量。

这是代码：

}

这是驱动程序：

}

我需要建议如何完成这项任务。autor创建了函数find_next_free_dataset_num(node)并在分布式哈希表中搜索空闲槽。这个 DHT 使用类似字典的接口来覆盖__setitem__、__getitem__和__contains__。哪个是好的设计。但是这个函数现在使用线性探测来搜索新的未使用的插槽以获取可预测的密钥。所以问题是指数num = num*num + 1是否解决了它以及如何对 0 和使用的插槽 num 之间的新 num 值实现二进制搜索？

使用二次探测将键插入列表时，我正在尝试计算探测数（或必须传递的索引数）

我有

我认为这只会在每次索引更改时计算在内，但不计算它跨越的索引数。如何计算密钥通过的每个索引？