链接列表与哈希表中的开放寻址

Question

我有一个有130000个元素的数据集，我有两种不同的数据结构，即双链表和哈希表。当将数据集元素插入链表时，我使用尾指针将节点放在列表的末尾。当将数据集元素插入哈希表时，我受益于带有探测功能的开放式寻址方法。我面临数据集中最后10个元素的110000次冲突。

然而，两种不同数据结构的插入总运行时间之差等于0.0981秒。

链接列表=0.028521秒

哈希表=0.120102秒

指针操作很慢还是探测方法很快？

Answer 1

指针操作很慢还是探测方法很快？

由于没有实际的算法，因此答案将相当理论化。

就性能而言，一般的答案是：缓存未命中代价高昂。由于DDR具有60 ns的延迟和3.2 GHz的CPU，最后一级缓存未命中会使CPU暂停60*3.2=~200个周期。

对于双链表算法，你必须访问尾指针、尾元素和新元素。如果你只是在循环中添加元素，所有这些访问都很有可能在中央处理器缓存中。

在实际应用程序中，如果在添加之间执行某些操作，可能会有多达3次缓存未命中（尾部指针、尾部元素、新元素）。

对于具有开放寻址的哈希表，情况有点不同。哈希函数在哈希表中生成一个随机索引，因此通常，对哈希表的第一次访问是缓存未命中。在您的例子中，哈希表没有那么大（130K个指针），所以它可能适合三级缓存。不过，L3缓存未命中率大约为30个CPU暂停周期。

但接下来会发生什么？只需将指针放入表中，无需更新tail元素或新元素。所以这里没有缓存丢失。

如果哈希表元素被占用，只需检查下一个。这样的顺序访问很容易被CPU预取器预测，所以所有这些访问通常也不会产生任何缓存未命中：CPU将下一个哈希表预取到一级缓存中。

所以，在实际应用中，哈希表通常有一个缓存未命中，但由于哈希是不可预测的，哈希表总是有第一个缓存未命中。

为了得到一个实用的答案，你的应用程序中发生了什么，你应该使用一个工具来分析CPU性能计数器，比如Linux上的perf或Windows上的VTune。该工具将显示你的CPU到底花了什么时间。

这里还有一个理论上的免责声明。我猜，如果你修复哈希表（比如，使用每个桶的几个元素，而不是打开的地址），并且有效地减少冲突的数量，性能可能是平价的。

你应该在哈希表上使用双链表，还是反之亦然？这取决于你的申请。哈希表适用于随机访问，也就是说，您可以在O（1）时间内访问任何元素。对于双链表，您必须遍历该列表，因此估计值为O（n）。

另一方面，仅在列表末尾添加元素不仅成本更低，而且更容易实现。您不关心任何冲突和哈希表溢出。

因此，在某些情况下，与哈希表相比，双链表具有巨大的优势，并且取决于应用程序最适合什么。

Answer 2

正如您在这里读到的，通过尾部指针在双链表末尾插入的值是O（1）。

在具有打开寻址的哈希表中的插入也可以是恒定的，您也可以在这里阅读。

然而，正确有效地实现具有开放寻址的哈希表是相当棘手的，因为很多事情都可能出错（探测、负载因子、哈希函数等）。就连维基百科也提到了。。

在最后10个元素中，我面临110000次冲突（在哈希表中）

这强烈表明哈希表实现中存在一些不好的地方。

这解释了为什么你所做的时间测量，如果它们是正确的，使双链表比哈希表更快。