哈希表中链表与开放寻址的比较

Question

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

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

链表= 0.028521秒

哈希表= 0.120102秒

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

Answer 1

通过尾部指针在双链表的末尾插入是O(1)，因为你也读到了here。

使用开放寻址的哈希表中的插入也可以是常量的，因为您也可以读取here。

然而，使用开放寻址的哈希表的正确和有效的实现是相当棘手的，因为很多事情都可能出错(探测、加载因子、哈希函数等)。甚至Wikipedia都提到..

对于最后10个元素，

I面临110000个冲突(在哈希表中)

这是一个强烈的迹象，表明您的哈希表实现中有一些不好的地方。

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

Answer 2

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

没有实际的算法，所以答案将是相当理论的。

在性能方面，通常的答案是:缓存未命中的代价很高。具有60 ns延迟和3.2CPU的DDR，末级高速缓存未命中使GHz停止60 * 3.2 =~ 200个周期。

双向链表

对于双向链表算法，需要访问尾指针、尾元素和新元素。如果您只是在循环中添加元素，那么所有这些访问都将在CPU缓存中的可能性很大。

在实际应用中，如果你在加法之间做一些事情，你可能会有多达3个缓存未命中(尾部指针，尾部元素，新元素)。

哈希表

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

但是接下来会发生什么呢？所以这里没有缓存未命中。

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

答案

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

真正的应用

这里还有一个理论上的免责声明。我猜想，如果你修复你的哈希表(比如，每个桶使用少量的元素，而不是开放寻址)，并有效地减少冲突的数量，性能可能与之相当。

您是否应该在哈希表上使用双向链表，反之亦然？这取决于您应用程序。

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

因此，在某些情况下，双向链表比哈希表具有巨大的优势，这取决于应用程序的最佳选择。