ImmutableCollections SetN实现细节
我很难理解java-9 ImmutableCollections.SetN的实现细节; 具体为什么需要增加两次内部数组。
假设你这样做：
Set.of(1,2,3,4) // 4 elements, but internal array is 8
更确切地说，我完全理解为什么在HashMap情况下完成（双重扩展） – 你从来没有（几乎）想要load_factor为1。 值!=1改善搜索时间，因为条目更好地分散到例如桶中。
但是在一个不可变的集合的情况下 – 我无法真正说明。 特别是因为选择内部arrays的索引的方式。
让我提供一些细节。 首先如何搜索索引：
int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);
pe是我们放入集合的实际值。 SALT在启动时只生成32位，每个JVM一次（如果需要，这是实际的随机化）。 我们的例子中的elements.length是8 （4个元素，但这里8个 – 大小加倍）。
这个表达式就像一个负安全的模运算 。 请注意，在选择存储桶时，例如（ (n - 1) & hash ）在HashMap完成相同的逻辑操作。
因此，如果elements.length is 8对于我们的情况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;
这很糟糕 – 插槽被占用，已经存在的条目等于我们想要放置的条目。 Set s不能有重复的元素 – 因此稍后会抛出exception。
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)
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年。
在线图书网站在这里，但请注意印刷版有更多细节。