set - Guava 的 ImmutableSet.contains 的性能

Question

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 ==============================

基本上，我用几千个负整数填充一个集合，测试包含非负整数。代码很简单，但是粘贴在一个小的文本区域有点太长，所以请看 here .

我想知道这里发生了什么。也许，我遇到了一些退化的情况，尽管我显然没有尝试。或者也许我刚刚打破了基准。否则，我想知道它是否可以并且应该修复。

解决方法是通过 replacing改变涂抹功能

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 处理等同于 this one为了在某​​些常见情况下最小化最低位的冲突。

尺寸表2*N被分配和 M 的成员投入其中。如 smear只涉及右移，它映射 M自身，这意味着表格的连续范围被填充。因此，假设表左半部分中的所有插槽都已使用，而另一半未使用。

当contains(o)被调用时，搜索从位置由 o.hashCode() 确定的槽开始。 .如 o找到了，结果是true , 如果一个空槽被命中，结果是 false .否则，搜索继续到另一个时隙。为了最小化缓存未命中，linear probing被使用。

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

我的基准测试中发生的情况并不完全如上，但其性能不佳的原因是相同的。将大小变为 2 的幂会使问题变得更糟。