使用二次探测实现哈希表的原因

最近我一直在学习哈希表。有几个碰撞解决方案的例子，其中一个是二次探测。为什么有人会使用二次探测？他知道散列表总是少于一半吗？如果是的话，他为什么要用这么大的桌子开始呢？使用二次探测实现哈希表的原因

你似乎是要求两种完全不同的。，正交问题 –

我明白你的意思了，我把这个问题改写得更清楚 – user2278279

为什么有人会使用二次探测？

假设我们需要一些冲突分解算法，

二次探测可以在一个封闭的哈希表更有效的算法，因为它更好地避免了可与线性探测发生聚类问题，尽管它不是免疫的。

的二次链接（或其他形式的）的优点是

简单逻辑存储管理（没有动态分配）

更快的插入（由于si mpler存储）

一般

减少存储需求，他是否知道哈希表总是会比全少了一半？

不一定;它取决于所使用的调整策略，如果有的话。

考虑你对QP的学习主要是教育。根据我的经验，实际的哈希表实现不经常使用open addressing,。

2013-04-13 20:47:32

噢，好吧，你可以从任何大小开始，每当它满足调整大小时，就可以调整大小。浪费空间吗？改变散列函数不是更好吗？ – user2278279

@ user2278279-这不会浪费太多空间。通常，你的空间不会超过你需要的4倍，因为任何时候你有2x空间你的桌子大小加倍。这是一个相当标准的实现。 – templatetypedef

现在我明白了。这取决于你如何实现散列表，如果你使用了一个指针数组，那么相比于散列函数的简单性，指针的两倍并不是那么糟糕，但是如果你使用一个大对象数组，那么你将会浪费空间。 – user2278279

二次方rehash是避免线性散列聚类问题的一种非常简单快速的方法。它通常只在表格大小为素数时使用（这可能也适用于其他原因）。

为了避免担心“表格半满”，在某些点切换到线性探头是最简单的。（你可以把阈值测试用于这种切换内部通常如果（指数> =大小）{索引 - =大小;}块，以避免任何性能损失

2013-04-14 01:47:53

回答