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 is 8 对于我们的情况，则此表达式将 return 任何小于 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;
 }

表示这个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 使用的分离链方法相反。（"Closed hashing" 也容易混淆地称为“open addressing”。）在封闭的散列方案中，元素存储在 table 本身中，而不是存储在元素列表或树中从每个 table 插槽链接，这是单独的链接。

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

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

因此我们有 class space 时间权衡。如果我们让 table 变大，那么整个 table 中都会散布着空槽。存储物品时，应该减少碰撞，线性探测会更快地找到空槽。彼此相邻的满槽集群将更小。对非成员的探测将进行得更快，因为他们更有可能在线性探测时更快地遇到空槽——可能在根本不必重新探测之后。

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

当然，所有这些都是实现细节，随着我们找到优化系统的更好方法，可能会从一个版本到下一个版本发生变化。我确信有一些方法可以改进当前的实施。（幸运的是，当我们这样做时，我们不必担心。）

可以在

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

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

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

ImmutableCollections SetN 实现细节

ImmutableCollections SetN implementation detail

java

collections

java-9