番石榴的ImmutableSet.contains性能(Performance of Guava&#

番石榴的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 ，这是二的幂。 等做了哈希，因为如何Integer.hashCode定义。 散列得到经由功能处理smear相同这一个 ，以最小化在某些普通情况下的最低位的碰撞。

大小的表2*N被分配和成员M得到投入它。 作为smear仅涉及右移，它映射M到其自身上，这意味着该表的连续范围被填充。 因此，可以说，在该表的左半部分的所有插槽都使用，而另一半未使用。

当contains(o)被调用时，搜索在该位置由下式确定一个槽开始o.hashCode() 如果o被发现，结果是true ，如果空槽被击中，结果是false 。 否则，搜索前进到另一个时隙。 为了最大限度地减少高速缓存未命中， 线性探测被使用。

当我们倒霉足以启动在第一次使用的插槽搜索，所有的人都必须穿过，这意味着N步骤。 在随机位置开始意味着N/4的平均步骤。

发生了什么事在我的基准是不是就像上面那样，但其糟糕表现的原因是一样的。 使得大小，以二的幂使问题变得更糟。

文章来源: Performance of Guava's ImmutableSet.contains