最近我一直在学习哈希表。其中有几个冲突解决的例子,其中之一是二次探测法。为什么会使用二次探测法?他知道哈希表始终不会超过一半吗?如果是这样,为什么要使用如此大的表呢?
最近我一直在学习哈希表。其中有几个冲突解决的例子,其中之一是二次探测法。为什么会使用二次探测法?他知道哈希表始终不会超过一半吗?如果是这样,为什么要使用如此大的表呢?
:)
二次探测是一种实现细节。 - Matt Ball二次再哈希是一种非常简单和快速的方式,可以避免线性哈希的聚集问题。通常只在表大小为质数时使用(这也可能有其他好处)。
为了避免任何对“表半满”的担忧,最简单的方法是在某个时刻切换到线性探测。 (您可以将此类切换的阈值测试放置在通常的 if(index>=size){index-=size;} 块内,以避免任何性能损失。