为什么使用空元素数组创建 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;

}

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

他们都对空数组技巧使用了“单个实例”，这很好，但为什么不只使用一个空数组呢？

Answer 1

从 C# 的角度回答。对于空ArrayList的，如果您有一个空数组作为后备存储，您会发现所有逻辑（获取、添加、增长......）都“按原样”工作。不需要额外的代码来处理未初始化的情况，这使得整个实现更加整洁。而且由于空数组被缓存，这不会导致额外的堆分配，因此您无需额外成本即可获得更简洁的代码。因为HashSet这是不可能的，因为访问存储桶是通过公式完成的hashCode % m_buckets.Length。尝试计算% 0被视为除以 0，因此无效。这意味着您需要专门处理“未初始化”的情况，因此您不会从使用空数组预先分配字段中获得任何收益。

Answer 2

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