抱歉,由于问题比较广泛,答案也会相当通用,同时提供一些更详细信息的链接。
最好从以下问题开始:
“缓存在哪里使用?”
在现代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)的代码也会更加复杂,因此如果您认为值得麻烦,则应该考虑这个方法...