最近我一直在学习哈希表。其中有几个冲突解决的例子，其中之一是二次探测法。为什么会使用二次探测法？他知道哈希表始终不会超过一半吗？如果是这样，为什么要使用如此大的表呢？
使用二次探测来实现哈希表的原因
3
- user2278279
2
你似乎在问两个完全不同、正交的问题。 - Matt Ball
我明白你的意思了，我重新措辞问题以使其更清晰。 - user2278279
2个回答
2
为什么有人会使用二次探测？
假设我们需要一些冲突解决算法，
二次探测可以在闭散列表中提供更有效的算法，因为它更好地避免了线性探测可能出现的聚集问题，尽管它并不免疫。
（来自Wikipedia）
二次探测并非完美，但与其他替代方案相比它确实提供了一些优点： 链式存储的优点是
- 存储管理逻辑更简单（没有动态分配） - 插入速度更快（由于存储更简单） - 一般情况下减少了存储需求
（来自mjv的答案）
他知道哈希表总是少于半满吗？
不一定，这取决于使用的调整大小策略（如果有）。
将您在 QP 上的学习视为主要的教育性质。根据我的经验，实际的哈希表实现很少使用开放地址法。
假设我们需要一些冲突解决算法，
二次探测可以在闭散列表中提供更有效的算法，因为它更好地避免了线性探测可能出现的聚集问题，尽管它并不免疫。
（来自Wikipedia）
二次探测并非完美，但与其他替代方案相比它确实提供了一些优点： 链式存储的优点是
- 存储管理逻辑更简单（没有动态分配） - 插入速度更快（由于存储更简单） - 一般情况下减少了存储需求
（来自mjv的答案）
他知道哈希表总是少于半满吗？
不一定，这取决于使用的调整大小策略（如果有）。
将您在 QP 上的学习视为主要的教育性质。根据我的经验，实际的哈希表实现很少使用开放地址法。
- Matt Ball
4
1哦，好的，所以你可以从任何大小开始，当它超过一半时重新调整表格大小。那不是浪费空间吗？改变哈希函数会更好吧？ - user2278279
@user2278279- 这不会浪费太多的空间。通常，你所需的空间不会超过实际需要的4倍，因为当你拥有2倍的空间时，你会使表格大小加倍。这是一种相当标准的实现方式。 - templatetypedef
现在我明白了。这取决于你如何实现哈希表，如果你使用指针数组，那么相比哈希函数的简单性，两倍的指针并不算太糟糕，但如果你使用大对象的数组，那么你将浪费空间。 - user2278279
当然这取决于
:) 二次探测是一种实现细节。 - Matt Ball1
二次再哈希是一种非常简单和快速的方式，可以避免线性哈希的聚集问题。通常只在表大小为质数时使用（这也可能有其他好处）。
为了避免任何对“表半满”的担忧，最简单的方法是在某个时刻切换到线性探测。 （您可以将此类切换的阈值测试放置在通常的 if（index>=size）{index-=size;} 块内，以避免任何性能损失。
- James Dow Allen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接