public Stack (int capacity) 
public List (int capacity)
public Queue (int capacity)
public HashSet (int capacity)
public Dictionary (int capacity)

// 用于存在實(shí)際的數(shù)據(jù)，添加進(jìn)List的元素都由存儲(chǔ)在_items數(shù)組中
internal T[] _items;
// 當(dāng)前已經(jīng)存儲(chǔ)了多少元素
internal int _size;
// 當(dāng)前的版本號(hào)，List每發(fā)生一次元素的變更，版本號(hào)都會(huì)+1
private int _version;

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(T item)
{
    // 版本號(hào)+1
    _version++;
    T[] array = _items;
    int size = _size;
    // 如果當(dāng)前已經(jīng)使用的空間 小于數(shù)組大小那么直接存儲(chǔ) size+1
    if ((uint)size < (uint)array.Length)
    {
        _size = size + 1;
        array[size] = item;
    }
    else
    {
        // 注意??！ 如果已經(jīng)使用的空間等于數(shù)組大小，那么走AddWithResize方法
        AddWithResize(item);
    }
}

// AddWithResize方法
[MethodImpl(MethodImplOptions.NoInlining)]
private void AddWithResize(T item)
{
    Debug.Assert(_size == _items.Length);
    int size = _size;
    // 調(diào)用Grow方法，并且把size+1，至少需要size+1的空間才能完成Add操作
    Grow(size + 1);
    _size = size + 1;
    _items[size] = item;
}

// Grow方法
private void Grow(int capacity)
{
    Debug.Assert(_items.Length < capacity);
    // 如果內(nèi)部數(shù)組長(zhǎng)度等于0，那么賦值為DefaultCapacity(大小為4)，否則就賦值兩倍當(dāng)前長(zhǎng)度
    int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
    // 這里做了一個(gè)判斷，如果newcapacity大于Array.MaxLength(大小是2^31元素)
    // 也就是說(shuō)一個(gè)List最大能存儲(chǔ)2^32元素
    if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;
    // 如果newpapacity小于預(yù)算需要的容量，也就是說(shuō)元素?cái)?shù)量大于Array.MaxLength
    // 后面Capacity會(huì)拋出異常
    if (newcapacity < capacity) newcapacity = capacity;
    // 為Capacity屬性設(shè)置值
    Capacity = newcapacity;
}

// Capacity屬性
public int Capacity
{
    // 獲取容量，直接返回_items的容量
    get => _items.Length;
    set
    {
        // 如果value值還小于當(dāng)前元素個(gè)數(shù)
        // 直接拋異常
        if (value < _size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }

        // 如果value值和當(dāng)前數(shù)組長(zhǎng)度不匹配
        // 那么走擴(kuò)容邏輯
        if (value != _items.Length)
        {
            // value大于0新建一個(gè)新的數(shù)組
            // 將原來(lái)的數(shù)組元素拷貝過(guò)去
            if (value > 0)
            {
                T[] newItems = new T[value];
                if (_size > 0)
                {
                    Array.Copy(_items, newItems, _size);
                }
                _items = newItems;
            }
            // value小于0 那么直接把_items賦值為空數(shù)組
            // 原本的數(shù)組可以被gc回收了
            else
            {
                _items = s_emptyArray;
            }
        }
    }

public class ListCapacityBench
{
    // 宇宙的真理 42
    private static readonly Random OriginRandom = new(42);

    // 整一個(gè)數(shù)列模擬常見(jiàn)的集合大小 最大12萬(wàn)
    private static readonly int[] Arrays =
    {
        3, 5, 8, 13, 21, 34, 55, 89, 100, 120, 144, 180, 200, 233, 
        250, 377, 500, 550, 610, 987, 1000, 1500, 1597, 2000, 2584,
        4181, 5000, 6765, 10946, 17711, 28657, 46368, 75025, 121393
    };

    // 生成一些隨機(jī)數(shù)
    private static readonly int[] OriginArrays = Enumerable.Range(0, Arrays.Max()).Select(c => OriginRandom.Next()).ToArray();
       
    // 不設(shè)置容量
    [Benchmark(Baseline = true)]
    public int WithoutCapacity()
    {
        return InnerTest(null);
    }

    // 剛好設(shè)置需要的容量
    [Benchmark]
    public int SetArrayLengthCapacity()
    {
        return InnerTest(null, true);
    }

    // 設(shè)置為8
    [Benchmark]
    public int Set8Capacity()
    {
        return InnerTest(8);
    }
    
    // 設(shè)置為16
    [Benchmark]
    public int Set16Capacity()
    {
        return InnerTest(16);
    }

    // 設(shè)置為32
    [Benchmark]
    public int Set32Capacity()
    {
        return InnerTest(32);
    }
    
    
    // 設(shè)置為64
    [Benchmark]
    public int Set64Capacity()
    {
        return InnerTest(64);
    }
    
    // 實(shí)際的測(cè)試方法
    // 不使用JIT優(yōu)化，模擬集合的實(shí)際使用場(chǎng)景
    [MethodImpl(MethodImplOptions.NoOptimization)]
    private static int InnerTest(int? capacity, bool setLength = false)
    {
        var list = new List<int>();
        foreach (var length in Arrays)
        {
            List<int> innerList;
            if (capacity == null)
            {
                innerList = setLength ? new List<int>(length) : new List<int>();
            }
            else
            {
                innerList = new List<int>(capacity.Value);
            }
            
            // 真正的測(cè)試方法  簡(jiǎn)單的填充數(shù)據(jù)
            foreach (var item in OriginArrays.AsSpan()[..length])
            {
                innerList.Add(item);
            }
            
            list.Add(innerList.Count);
        }

        return list.Count;
    }

private void Grow(int capacity)
{
    Debug.Assert(_array.Length < capacity);
    const int GrowFactor = 2;
    const int MinimumGrow = 4;
    int newcapacity = GrowFactor * _array.Length;

    if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;

    newcapacity = Math.Max(newcapacity, _array.Length + MinimumGrow);

    if (newcapacity < capacity) newcapacity = capacity;
    SetCapacity(newcapacity);
}

private void Resize() => Resize(HashHelpers.ExpandPrime(_count), forceNewHashCodes: false);
private void Resize(int newSize, bool forceNewHashCodes)
{
    // Value types never rehash
    Debug.Assert(!forceNewHashCodes || !typeof(T).IsValueType);
    Debug.Assert(_entries != null, "_entries should be non-null");
    Debug.Assert(newSize >= _entries.Length);
    var entries = new Entry[newSize];
    int count = _count;
    Array.Copy(_entries, entries, count);
    if (!typeof(T).IsValueType && forceNewHashCodes)
    {
        Debug.Assert(_comparer is NonRandomizedStringEqualityComparer);
        _comparer = (IEqualityComparer<T>)((NonRandomizedStringEqualityComparer)_comparer).GetRandomizedEqualityComparer();
        for (int i = 0; i < count; i++)
        {
            ref Entry entry = ref entries[i];
            if (entry.Next >= -1)
            {
                entry.HashCode = entry.Value != null ? _comparer!.GetHashCode(entry.Value) : 0;
            }
        }
        if (ReferenceEquals(_comparer, EqualityComparer<T>.Default))
        {
            _comparer = null;
        }
    }
    // Assign member variables after both arrays allocated to guard against corruption from OOM if second fails
    _buckets = new int[newSize];
#if TARGET_64BIT
    _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
#endif
   for (int i = 0; i < count; i++)
   {
       ref Entry entry = ref entries[i];
       if (entry.Next >= -1)
       {
           ref int bucket = ref GetBucketRef(entry.HashCode);
           entry.Next = bucket - 1; // Value in _buckets is 1-based
           bucket = i + 1;
       }
   }
   _entries = entries;
}

public const uint HashCollisionThreshold = 100;
// 這是比Array.MaxLength小最大的素?cái)?shù)
public const int MaxPrimeArrayLength = 0x7FFFFFC3;
public const int HashPrime = 101;
public static int ExpandPrime(int oldSize)
{
    // 新的size等于舊size的兩倍
    int nwSize = 2 * oldSize;
    // 和List一樣，如果大于了指定最大值，那么直接返回最大值
    if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
    {
        Debug.Assert(MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
        return MaxPrimeArrayLength;
    }
    // 獲取大于newSize的第一素?cái)?shù)
    return GetPrime(newSize);
}   
public static int GetPrime(int min)
{
    if (min < 0)
        throw new ArgumentException(SR.Arg_HTCapacityOverflow);
    // 獲取大于min的第一個(gè)素?cái)?shù)
    foreach (int prime in s_primes)
    {
        if (prime >= min)
            return prime;
    }
    // 如果素?cái)?shù)列表里面沒(méi)有 那么計(jì)算
    for (int i = (min | 1); i < int.MaxValue; i += 2)
    {
        if (IsPrime(i) && ((i - 1) % HashPrime != 0))
            return i;
    }
    return min;
}
// 用于擴(kuò)容的素?cái)?shù)列表
private static readonly int[] s_primes =
{
    3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
    1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
    17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
    187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
    1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
};
// 當(dāng)容量大于7199369時(shí)，需要計(jì)算素?cái)?shù)
public static bool IsPrime(int candidate)
{
    if ((candidate & 1) != 0)
  {
        int limit = (int)Math.Sqrt(candidate);
        for (int divisor = 3; divisor <= limit; divisor += 2)
        {
            if ((candidate % divisor) == 0)
                return false;
        }
        return true;
    }
    return candidate == 2;
}