4 java algorithm hash performance hashtable
好的,所以我一直在做一些哈希表和不同的冲突解决问题的实验.我试图找出哪个更有效地进行查找,哈希表使用单独的链接或二次探测来进行冲突解决.我的结果表明,即使对于0.4或0.2等小负载因子,单独链接也比二次探测更快.是这种情况还是我的结果错了？
在差值处理成本两种方法之间是的
(具有链接)
-的间接的,即指针引用
与
(与二次探测)
- [简单但复合]算术式的评价
-索引到新的位置
-可以重复(由于探测值与存储在这些位置的非目标值之间的碰撞;链接不必担心.
因此,链接更快是不足为奇的 ; 指针解除引用是大多数CPU的"本机"指令,与索引到数组中的指令相当(在大多数情况下相同),将算术运算和可能的冲突作为开销而不利于探测.最简单的探测序列公式将需要一些CPU指令(初始化stepNr,通常是stepNr的一些移位,添加到当前位置/探测器),其本身比指针解除引用慢几倍.(Poss.警告:此后不久请看'编辑',因为它讨论了链接如何导致更多CPU级别的缓存未命中因此使其效率低于线性探测)
二次(或其他形式)链接的优点是
考虑到这种空间与速度(或插入时间与搜索时间)的广泛关系,链接的存储开销(主要针对指针本身,不考虑可能的堆管理开销)用于存储前- [探测的内容]"探测位置"的计算值.由于这些计算很容易完成,因此链接方法在搜索时更快.
编辑(感谢,Ants Aasma)
对于这个论点[关于预先计算的位置]的一个警告是,在现代CPU及其缓存上,运行小计算的成本可能远低于在缓存时访问[数据]内存的成本未命中.这表明,由于缓存未命中率较低,顺序探测(或更一般地,探测功能产生物理上靠近碰撞点的位置)可能优于链接策略.在这种情况下,纯顺序探测方法是探测函数中最好的,因为它的计算非常简单,但更重要的是因为它最大化了缓存命中的几率.考虑到这一点,当散列函数具有良好的分布并且负载因子很小时(因此在初始碰撞之后具有短/局部搜索路径),应该尝试线性(或非常局部)探测方法 ; 但是,应该避免探测提供非物理本地搜索路径的功能.
很难对问题中提到的实验做出具体评论,例如不知道散列的大小(如果这个大小与CPU中的单词/寄存器匹配,算术可以更快),或者不知道碰撞比率(让我们假设一个好的,分布均匀的哈希函数).
在您不断尝试这一点时,收集一组单独的时间/统计信息来访问具有哈希槽的项目与产生冲突的项目将会很有趣.
" 即使是小负载因子...... "中的" 偶数 "表示您期望链接的相对优势应随负载进一步增加,因此碰撞变得更多.我也期待这种情况.
此外,增加负载可以说明探测的另一个缺点:探测周期时的情况和/或更一般地说当没有适合特定项目的空间时.