ImmutableCollections中为何EXPAND_FACTOR要设置为2

 有时候我会用Map.of(k1, v1, k2, v2)来快速构建一个Map。 顺便看了下源代码，其实Map.of的实现是这样子的：

    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
        return new ImmutableCollections.MapN<>(k1, v1, k2, v2);
    }

这里的MapN是ImmutableCollections的静态内部类（PS,静态类只能是静态内部类）。下面是她的定义。因为看到在MapN的构造函数中table的大小是table = new Object[len]，其中len是2被的元素个数。理论上table只要能存下所有的input就行了，为何这里要设置成input个数的2被呢？

其实这是因为MapN的table是使用的open addressing 方法来解决的hash冲突，所以如果刚好用和input个数一样大的table来存下来所有的input的话，就会出现查询的时候，有可能每个key的寻找复杂度都是O(n)。也就是把整个table遍历了一遍。那这样子基本上不能叫做Map了， 所以这里table的大小一定要留有余地，比input个数大才行。至于为什么是2， 不是1.5， 不是3， 可能是经验来的吧。

        static final int EXPAND_FACTOR = 2;
        MapN(Object... input) {
            if ((input.length & 1) != 0) { // implicit nullcheck of input
                    throw new InternalError("length is odd");
            }
            size = input.length >> 1;

            int len = EXPAND_FACTOR * input.length;
            len = (len + 1) & ~1; // ensure table is even length
            table = new Object[len];

            for (int i = 0; i < input.length; i += 2) {
                @SuppressWarnings("unchecked")
                    K k = Objects.requireNonNull((K)input[i]);
                @SuppressWarnings("unchecked")
                    V v = Objects.requireNonNull((V)input[i+1]);
                int idx = probe(k);
                if (idx >= 0) {
                    throw new IllegalArgumentException("duplicate key: " + k);
                } else {
                    int dest = -(idx + 1);
                    table[dest] = k;
                    table[dest+1] = v;
                }
            }
        }

这是在stack overflow上提的问题。

https://stackoverflow.com/questions/59627308/why-expand-factor-is-2-in-immutablecollections-java