散列表中使用链式法和开放地址法的缓存性能对比

Question

散列表中使用链式法和开放地址法的缓存性能对比

performancecachinghashlinked-listhashtable

15

在 geeksforgeeks.org 的这个网站上，它说：

由于键使用链表存储，所以链接的缓存性能不好。开放地址提供更好的缓存性能，因为所有内容都存储在同一张表中。

因此我的问题是：

什么导致链接的缓存性能不佳？
缓存用在哪里？
为什么开放地址提供更好的缓存性能，因为我看不出缓存如何影响这个？
在决定使用链接、线性探测开放地址和二次探测开放地址之间，还需要考虑哪些因素？

- Trajan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andriy Berestovskyy · Accepted Answer

抱歉，由于问题比较广泛，答案也会相当通用，同时提供一些更详细信息的链接。

最好从以下问题开始：

“缓存在哪里使用？”

在现代CPU上，缓存被用于读取程序指令和读/写内存中的数据。在大多数CPU上，缓存是透明的，即无需显式管理缓存。

缓存比主存储器（DRAM）快得多。仅为了让您有一个参考，访问Level 1缓存中的数据需要约4个CPU周期，而在同一CPU上访问DRAM需要约200个CPU周期，即快50倍。

缓存在称为缓存行的小块上运行，通常为64字节长。

更多信息：https://en.wikipedia.org/wiki/CPU_cache “什么导致链接法对缓存性能不佳？”

基本上，链接法不友好缓存。这不仅适用于哈希表中的情况，对于“传统”列表也存在同样的问题。

哈希键（或列表节点）相距很远，因此每个键访问都会生成“缓存未命中”，即慢速DRAM访问。因此，在链中检查10个键需要10个DRAM访问，即对于我们的通用CPU，需要200 x 10 = 2000个周期。

下一个键的地址在读取当前键中的next指针之前是未知的，因此没有太多优化的空间...

为什么开放寻址可以提供更好的缓存性能，我看不出缓存如何参与其中？

线性探测对缓存友好。键被“聚集”在一起，因此一旦我们访问了第一个键（慢速DRAM访问），很可能下一个键已经在缓存中，因为缓存行是64字节。因此，使用开放寻址访问相同的10个键只需要1个DRAM访问和9个缓存访问，即对于我们的通用CPU，200 x 1 + 9 x 4 = 236个周期。这比链接键的2000个周期快得多。

此外，由于我们以可预测的方式访问内存，因此有优化的余地，例如缓存预取：https://en.wikipedia.org/wiki/Cache_prefetching 决定链式、线性探测开放寻址和二次探测开放寻址之间的考虑因素是什么？

链式或线性探测无论如何都不是一个好迹象。因此，我首先要考虑的是通过使用良好的哈希函数和合理的哈希大小来确保碰撞的概率最小。

我考虑的第二件事是现成的解决方案。当然，仍然可能存在一些罕见情况，需要您自己实现...

不确定语言，但这里有一个带有BSD许可证的极快的哈希表实现：http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_cuckoo_hash.h

因此，如果您仍需要自己的哈希表实现并且关心性能，下一个相当简单的实现就是使用与缓存对齐的桶(bucket)而不是普通的哈希元素。这将浪费每个元素几个字节（即每个哈希表元素将长达64个字节），但在冲突的情况下，至少会有一些快速存储来存储几个键。管理这些桶(bucket)的代码也会更加复杂，因此如果您认为值得麻烦，则应该考虑这个方法...