15

GuavaImmutableSet在我关于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);

这需要大约相同的时间并且可能有一些缺点，但通过很好地散布散列解决了当前的问题。

4

1 回答 1

9

解释其实很简单。想象一下整数位于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 的幂会使问题变得更糟。

于 2012-09-25T18:14:18.780 回答