我最近了解了处理哈希表中冲突的不同方法，并发现与链表的单独链接始终比线性探测更节省时间。为了提高空间效率，我们为线性探测分配了预定义的内存，以后我们可能不会使用它，但是对于单独的链接，我们会动态使用内存。
用链表进行单独链接比线性探测更有效吗？如果是这样，我们为什么还要使用线性探测呢？
最佳答案
令您惊讶的是，您看到链式哈希比线性探测要快-实际上，线性探测通常比链式探测快得多。这主要归因于locality of reference，因为在线性探测中执行的访问趋向于在内存中比在链式哈希中执行的访问更近。
线性探测还有其他优势。例如，插入线性探测哈希表不需要任何新的分配(除非您要重新哈希表)，因此在内存不足的网络路由器之类的应用中，很高兴知道一旦建立了表，可以将元素放入其中，而不会出现malloc失败的风险。
线性探测的一个缺点是，如果哈希函数选择不正确，primary clustering可能导致表的性能显着下降。尽管链式散列仍会受到不良散列函数的影响，但它对具有附近散列码的元素不那么敏感，不会对运行时间产生不利影响。从理论上讲，如果哈希函数是5-independent或there's sufficient entropy in the keys，则线性探测仅会提供预期的O(1)查找。有很多方法可以解决此问题，因为使用Robin Hood hashing技术或hopscotch hashing时，这两种情况下的最坏情况都比 Vanilla 线性探测好得多。
线性探测的另一个缺点是，随着负载系数接近1，其性能会大大降低。您可以通过定期重新哈希或使用上述Robin Hood哈希技术来解决此问题。
希望这可以帮助!