不可变集合 SetN 实现详细信息

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

假设您执行以下操作：

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

更确切地说，我完全理解为什么在a的情况下这样做（双重扩展） - 你永远不会（几乎）想要成为一个。例如，当条目更好地分散到存储桶中时，值为 可缩短搜索时间。HashMapload_factor!=1

但是在不可变的集合的情况下 - 我真的不能说。特别是因为内部数组的索引选择方式。

让我提供一些细节。首先如何搜索索引：

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

pe是我们放入集合中的实际值。 在启动时仅生成32位，每一次（如果需要，这是实际的随机化）。 对于我们的例子是（4个元素，但这里8个 - 大小加倍）。SALTJVMelements.length8

此表达式类似于负安全模运算。请注意，例如，在选择存储桶时，会在 （） 中完成相同的逻辑操作。HashMap(n - 1) & hash

因此，对于我们的情况，则此表达式将返回任何小于 8 的正值。elements.length is 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;

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

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

这意味着此槽被占用（哈希冲突），但元素不相等。在此条目中，将放入与 or 相同的存储桶中 - 但此处不是这种情况。HashMapLinkedNodeTreeNode

因此递增并尝试下一个位置（小警告是，当它到达最后一个位置时，它会以圆形方式移动）。index

问题是：如果在搜索索引时没有做任何太花哨的事情（除非我错过了什么），为什么需要一个两倍大的数组？或者为什么函数不是这样写的：

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

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