哈希表中二次探测的运行时是什么？
这是一个类似于线性探测运行时的问题，但它涉及二次探测。
对我来说，“理论上最坏的情况是O（n）”对于线性探测是有意义的，因为在最坏的情况下，你可能需要遍历每个桶（n个桶）
二次探测的运行时是什么？我知道二次探测-1, 4, 9, 16，......我最初的想法是这是对数n（指数）的一些变化，但没有一致的基数。
共有1个答案
如果哈希表中有n-1占用的存储桶，那么无论您检查空存储桶的顺序如何，您都不能排除在找到空存储桶之前需要测试n个存储桶的可能性。因此，二次探测的最坏情况不会比O（n）更好。
然而，情况可能会更糟：我并不清楚二次探测是否能很好地避免多次测试同一个桶。（如果您选择的步长相对于桶数来说相对最佳，线性探测就不是问题。）我想二次探测不会重访相同的桶足够多的时间，使最坏的情况比O（n）更糟，但我无法证明这一点。
-
我在做一个程序，比较哈希表中线性探测、二次探测和单独链接所需的平均访问量和最大访问量。 我已经做了三个案例的元素插入部分。当从哈希表中找到元素时，我需要有一个结束搜索的限制。在单独链接的情况下，当下一个指针为空时，我可以停止。对于线性探测，当探测到整个表时，我可以停止（即表的大小）。在二次探测中，我应该用什么作为限制？表大小可以吗？ 我的二次探测函数是这样的 其中i从0到无穷大。请帮帮我...
-
我正在用一个字符串数组单维和一个2维int数组制作哈希表。我正在使用线性探测进行冲突检测，当我意识到如果检测到冲突，单词的hashCode将不再是索引时，我真的很兴奋地完成了这个程序。我该如何保存该索引以备以后使用？
-
我试图解决这个问题，我需要实现线性探测。 给定一个整数数组和一个哈希表大小。使用线性探测将数组元素填充到哈希表中以处理冲突。 例1： 例2： 您的任务： 您不需要读取输入或打印任何内容。 您的任务是完成函数linearProbing（），该函数将空哈希表（hash）、哈希表大小（hashSize）、整数数组arr[]及其大小N作为输入，并将数组arr[]的所有元素插入给定的哈希表中。 哈希表的空单
-
我在研究hackerearth上的哈希表，在那里我遇到了用线性探测实现哈希表的代码。我对这段代码有两个疑问：- 1）为什么他们声明大小为21（而不是大小为20）的hashTable最多容纳20个元素？ 2） 在Insert函数中，当循环无限运行时，如果在连续迭代之后，索引的值变为索引的初始值，不是吗？ 链接至黑客主页：-https://www.hackerearth.com/practice/da
-
主要内容：哈希表的构建,哈希函数的构造,处理冲突的方法,总结前面介绍了静态 查找表以及动态查找表中的一些查找方法，其查找的过程都无法避免同查找表中的数据进行比较，查找算法的效率很大程度取决于同表中数据的查找次数。 而本节所介绍的 哈希表可以通过关键字直接找到数据的存储位置，不需要进行任何的比较，其查找的效率相较于前面所介绍的查找算法是更高的。 哈希表的构建 在初中的数学课本中学习过函数的相关知识，给定一个 x，通过一个数学公式，只需要将 x 的值带入公式就
-
从原理到应用分析什么是哈希？ 一、什么是哈希？ 哈希（hash）：将任意长度的输入（关键字），通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值，通常哈希值代表了关键字的存储位置。 但是为什么要这样做呢？或者说，哈希是怎样来的呢？ 哈希的出现解决了两个问题：存储和搜索。 1. 存储（数据结构）：如果在容器中保存对象及其关联的键，并且不用键