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

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

因此，如果我们的情况下 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;
 }

这意味着这个槽被占用(哈希冲突)，但是元素不相等。在 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，因为与 HashSet 相比，它获得了大部分性能改进(接近 O(1) 时间)，同时提供了良好的空间节省。 (抱歉，我们尚未在任何地方发布这些基准数据。)

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

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

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

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