为什么数组列表是使用空元素数组创建的，而哈希集是使用空表创建的？

Question

也许有点哲学问题。

查看java的ArrayList实现，我注意到在创建新实例时，内部“elementData”数组（保存项目）被创建为新的空数组：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

但是，使用表创建哈希集（基于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#的列表和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# 的角度回答。对于空的 ，您会发现，如果您有一个空数组作为后备存储，则所有逻辑（get，add，grow，...）都“按原样”工作。无需额外的代码来处理未初始化的情况，这使得整个实现更加整洁。由于空数组是缓存的，这不会导致额外的堆分配，因此您可以获得更干净的代码，而无需额外费用。ArrayList因为这是不可能的，因为访问存储桶是通过公式完成的。尝试计算被视为除以 0，因此无效。这意味着您需要专门处理“未初始化”的情况，因此使用空数组预先分配字段不会获得任何好处。HashSethashCode % m_buckets.Length% 0

Answer 2

初始化为 中的空数组可以避免在方法中签入，该方法调用：elementDataArrayListnullgrow(int minCapacity)elementData&nbsp;=&nbsp;Arrays.copyOf(elementData,&nbsp;newCapacity);以增加后备阵列的容量。首次调用该方法时，该语句会将空数组“复制”到新数组的开头（实际上它不会复制任何内容）。在类似的策略中，没有用，因为当您重新调整存储桶数组的大小时，您不会将原始数组复制到新数组的开头，您必须遍历所有条目并找到每个条目的新存储桶。因此，将 bucket 数组初始化为空数组而不是将其保留为 null 将要求您检查数组的长度是否 == 0，而不是检查它是否为 null。用另一个条件替换一个条件是没有用的。HashMap