java - 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 个 - 大小加倍)。

这个表达式就像一个负安全模运算。 Notice that the same logical thing is done in HashMap for example ((n - 1) & hash) when the bucket is chosen.

所以如果 elements.length 是 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;

这很糟糕 - 插槽已被占用，并且已经存在的条目等于我们要放置的条目。 Set 不能有重复的元素 - 因此稍后会抛出异常。

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

意思是这个slot被占用了(哈希冲突)，但是元素不相等。在 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 使用的分离链方法相反。 (“闭合散列”也容易混淆地称为“open addressing”。)在闭合散列方案中，元素存储在表本身中，而不是存储在从每个表槽链接的元素列表或树中，这是单独的链接。

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

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

因此我们有类时空权衡。如果我们把 table 变大，就会有空位散布在整个 table 上。存储元素时，应该减少碰撞，线性探测会更快地找到空槽。彼此相邻的满槽集群将更小。对非成员的探测将进行得更快，因为他们更有可能在线性探测时更快地遇到空槽——可能是在根本不必重新探测之后。

在实现过程中，我们使用不同的扩展因子运行了一系列基准测试。 (我在代码中使用了术语EXPAND_FACTOR，而大多数文献使用加载因子。原因是扩展因子是加载因子的倒数，如HashMap，并且对这两种含义都使用“加载因子”会造成混淆。)当扩展因子接近 1.0 时，探测性能如预期的那样相当慢。随着扩展系数的增加，它得到了显着改善。当它上升到 3.0 或 4.0 时，改进真的趋于平缓。我们选择 2.0 是因为它获得了大部分性能改进(接近 O(1) 时间)，同时与 HashSet 相比提供了良好的空间节省。 (抱歉，我们尚未在任何地方发布这些基准数据。)

当然，所有这些都是实现细节，并且随着我们找到优化系统的更好方法，可能会从一个版本到下一个版本发生变化。我确信有一些方法可以改进当前的实现。 (幸运的是，我们在执行此操作时不必担心 preserving iteration order。)

可以在第 3.4 节中找到关于开放式寻址和性能与负载因子权衡的很好的讨论

Sedgewick, Robert and Kevin Wayne. Algorithms, Fourth Edition. Addison-Wesley, 2011.

在线图书网站是here但请注意，打印版包含更多详细信息。