我最近了解了处理哈希表中冲突的不同方法，发现使用链表的单独链接总是比线性探测更省时。为了空间效率，我们为线性探测分配了一个预定义的内存，稍后我们可能不会使用它，但对于单独的链接，我们动态地使用内存。
使用链表的单独链接是否比线性探测更有效？如果是这样，我们为什么还要使用线性探测？
最佳答案
我很惊讶您看到链式哈希比线性探测更快 - 实际上，线性探测通常比链式快得多。这主要是由于 locality of reference ，因为在线性探测中执行的访问往往比在链式哈希中执行的访问更接近内存。
线性探测还有其他优势。例如，插入线性探测哈希表不需要任何新分配(除非您正在重新哈希表)，因此在内存稀缺的网络路由器等应用程序中，很高兴知道一旦设置了表，可以将元素放入其中，而不会有 malloc 失败的风险。
线性探测的一个弱点是，如果哈希函数选择不当，primary clustering会导致表的性能显着下降。虽然链式哈希仍然会受到不良哈希函数的影响，但它对具有附近哈希码的元素不那么敏感，这不会对运行时产生不利影响。从理论上讲，如果哈希函数是 5-independent，线性探测只会给出预期的 O(1) 查找。或者如果 there's sufficient entropy in the keys .有很多方法可以解决这个问题，因为使用 Robin Hood hashing技术或 hopscotch hashing ，两者的最坏情况都明显好于普通线性探测。
线性探测的另一个弱点是，当负载因子接近 1 时，其性能会显着降低。您可以通过定期重新散列或使用上述 Robin Hood 散列技术来解决这个问题。
希望这对您有所帮助!
关于performance - 当有单独的链接与列表链接时，为什么我们在哈希表中使用线性探测？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23821764/