ImmutableCollections SetN实现细节

Question

我很难理解java-9中的实现细节ImmutableCollections.SetN; 具体为什么需要两次增加内部数组.

假设你这样做:

Set.of(1,2,3,4) // 4 elements, but internal array is 8

更准确地说,我完全理解为什么这样做(双重扩展)以防万一HashMap- 你从来没有(几乎)想要load_factor成为一个.例如,!=1当条目更好地分散到存储桶时,值可以改善搜索时间.

但是在一个不可变的集合的情况下- 我无法真正说出来.特别是因为选择了内部数组的索引.

让我提供一些细节.首先如何搜索索引:

 int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);

pe是我们放在集合中的实际值.SALT在启动时只生成32位,每次生成一次JVM(如果需要,这是实际的随机化).elements.length我们的例子是8(4个元素,但这里有8个 - 大小加倍).

这个表达式就像一个负安全的模运算.请注意,选择存储桶时HashMap,例如((n - 1) & hash)中会执行相同的逻辑操作.

因此,如果elements.length is 8对于我们的情况,则此表达式将返回任何小于8的正值(0, 1, 2, 3, 4, 5, 6, 7).

现在剩下的方法:

 while (true) {
        E ee = elements[idx];
        if (ee == null) {
            return -idx - 1;
        } else if (pe.equals(ee)) {
            return idx;
        } else if (++idx == elements.length) {
            idx = 0;
        }
    }

让我们分解一下:

if (ee == null) {
    return -idx - 1;

这很好,这意味着数组中的当前插槽是空的 - 我们可以将值放在那里.

} else if (pe.equals(ee)) {
    return idx;

这很糟糕 - 插槽被占用,已经就位的条目等于我们要放置的条目.Sets不能有重复的元素 - 因此稍后会抛出异常.

 else if (++idx == elements.length) {
      idx = 0;
 }

这意味着此插槽已被占用(哈希冲突),但元素不相等.在HashMap这个条目将被放置到同一个桶的LinkedNode或TreeNode在这里,但情况并非如此- .

因此index递增并尝试下一个位置(当它到达最后位置时,它以圆形方式移动的小警告).

这里有一个问题:在搜索索引时,如果没有什么太花哨(除非我遗漏了什么),为什么需要有两倍大的数组？或者为什么函数不是这样编写的:

int idx = Math.floorMod(pe.hashCode() ^ SALT, input.length);

// notice the diff elements.length (8) and not input.length (4)

Answer 1

当前的实现SetN是一个相当简单的闭合散列方案,而不是单独使用的链接方法HashMap.("封闭散列"也混淆地称为" 开放寻址 ".)在封闭散列方案中,元素存储在表本身中,而不是存储在从每个表槽链接的元素的列表或树中,是单独的链接.

这意味着如果两个不同的元素散列到同一个表槽,则需要通过为其中一个元素找到另一个槽来解决此冲突.当前的SetN实现使用线性探测解决了这个问题,其中顺序检查表槽(在末尾环绕),直到找到打开的槽.

如果你想存储N个元素,它们肯定适合大小为N的表.您总是可以找到集合中的任何元素,但您可能需要探测几个(或许多)连续的表槽来查找它,因为会有很多冲突.但是,如果探测到的是不是成员的对象,则线性探测必须先检查每个表槽,然后才能确定该对象不是成员.使用完整表,大多数探测操作将降级到O(N)时间,而大多数基于散列的方法的目标是操作为O(1)时间.

因此,我们有一个类时空权衡.如果我们把桌子做得更大,整个桌子上都会有空的插槽.存储项目时,应该有更少的冲突,线性探测将更快地找到空槽.彼此相邻的完整时隙簇将更小.非成员的探测器将更快地进行,因为他们更可能在线性探测时更快地遇到空槽 - 可能在不必重新探测之后.

在提出实施时,我们使用不同的扩展因子运行了一系列基准测试.(我在代码中使用了术语EXPAND_FACTOR,而大多数文献都使用了载荷因子.原因是扩展因子是载荷因子的倒数,如同使用的那样HashMap,并且对于这两种含义使用"载荷因子"会令人困惑.)当扩展因子接近1.0,探测器性能非常缓慢,如预期的那样.随着扩展系数的增加,它得到了显着改善.到达3.0或4.0时,这种改进确实很平坦.我们选择2.0是因为它获得了大部分性能提升(接近O(1)时间),同时提供了良好的空间节省HashSet.(对不起,我们没有在任何地方公布这些基准数字.)

当然,所有这些都是实现细节,并且可能会从一个版本更改为下一个版本,因为我们找到了更好的方法来优化系统.我确信有办法改进当前的实施.(幸运的是,当我们这样做时,我们不必担心保留迭代顺序.)

有关负载因子的开放寻址和性能折衷的详细讨论可以在3.4节中找到

塞奇威克,罗伯特和凯文韦恩.算法,第四版.Addison-Wesley,2011年.

在线图书网站在这里,但请注意印刷版有更多细节.