java - 为什么 ArrayList 是用空元素数组创建的，而 HashSet 是用空表创建的？

Question

也许有点哲学问题。

查看 java 的 ArrayList 实现，我注意到在创建新实例时，内部“elementData”数组(包含项目)被创建为新的空数组:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

但是，HashSet(基于 HashMap)是用表创建的，entreySet 只是空的；

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

这让我开始思考，所以我去查找 C# 的 List 和 HashSet: https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,61f6a8d9f0c40f6e https://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs,2d265edc718b158b

列表:

static readonly T[]  _emptyArray = new T[0]; 

public List() {
        _items = _emptyArray;
}

哈希集:

private int[] m_buckets;

public HashSet()
        : this(EqualityComparer<T>.Default) { }

public HashSet(IEqualityComparer<T> comparer) {
    if (comparer == null) {
        comparer = EqualityComparer<T>.Default;
    }

    this.m_comparer = comparer;
    m_lastIndex = 0;
    m_count = 0;
    m_freeList = -1;
    m_version = 0;
}

那么，为什么这两种语言都为列表选择空而为集合/映射选择空有充分的理由吗？

他们都使用“单一实例”来实现空数组技巧，这很好，但为什么不直接使用空数组呢？

Answer 1

从 C# 的角度回答。

对于一个空的 ArrayList，如果您有一个空数组作为后备存储，您会发现所有逻辑(获取、添加、增长……)都“按原样”工作。不需要额外的代码来处理未初始化的情况，这使得整个实现更加整洁。由于缓存了空数组，因此不会导致额外的堆分配，因此您无需额外成本即可获得更清晰的代码。

对于 HashSet，这是不可能的，因为访问存储桶是通过公式 hashCode % m_buckets.Length 完成的。尝试计算 %0 被视为除以 0，因此无效。这意味着您需要专门处理“未初始化”的情况，因此您可以从为字段预分配空数组中获得任何好处。