番石榴ImmutableSet.contains的表现

Question

ImmutableSet在我的基准测试中,番石榴似乎表现不佳contains.对于某些尺寸,它甚至比List以下更慢:

  size            benchmark         ns linear runtime
100000         ListContains  110279.54 ==
100000          SetContains       7.15 =
100000 ImmutableSetContains   76716.47 =
200000         ListContains  275367.66 =====
200000          SetContains       7.34 =
200000 ImmutableSetContains  322185.50 ======
500000         ListContains  935210.10 ====================
500000          SetContains       7.79 =
500000 ImmutableSetContains 1382765.76 ==============================

基本上,我填充一组有几千个负整数,测试包含非负数.代码很简单,但在一个小的文本区域粘贴有点太长,所以请看这里.

我想知道这里发生了什么.可能,我遇到了一些堕落的情况,尽管我显然没有尝试过.或许我刚刚吹了基准.否则,我想知道它是否可以而且应该修复.

---

解决方案是通过替换来改变拖尾功能

hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);

通过

return C2 * Integer.rotateLeft(hashCode * C1, 15);

这需要大约相同的时间并且可能有一些缺点,但通过很好地散布哈希来解决当前的问题.

Answer 1

解释实际上非常简单.想象一下,M = {0, 1, ..., N-1}对于某些人而言N,整数位于集合中,这是2的幂.哈希Integer.hashCode也是如此,因为如何定义.散列通过smear与此相同的函数进行处理,以便在一些常见情况下最小化最低位中的冲突.

2*N分配一个大小的表,并将其中的成员M放入其中.由于smear只涉及右移,它映射M到自身,这意味着表的连续范围被填充.因此,假设使用了表左半部分的所有插槽而另一半未使用.

当contains(o)被调用时,搜索在该位置由下式确定的槽开始o.hashCode().如果o找到了,结果是true,如果一个空槽被击中,结果是false.否则,搜索进入另一个时隙.为了最小化缓存未命中,使用线性探测.

当我们不幸在第一个使用过的插槽中开始搜索时,必须遍历所有这些,这意味着N步骤.从随机位置开始意味着N/4平均步数.

在我的基准测试中发生的事情并不完全如上所述,但其性能不佳的原因是相同的.使大小达到2的幂会使问题变得更糟.