.NET中的HashSet及原理解析

private int[]? _buckets; // _entries索引陣列
private Entry[]? _entries; // 實體陣列

private int _count; // 實際儲存的元素數量
private int _freeList; // 空位連結串列頭索引，初始值-1
private int _freeCount; // 空位數量
private struct Entry
{
    public int HashCode;
    public int Next;
    public T Value;
}
public int Count => _count - _freeCount; // _count不會記錄被刪除的元素，因此實際元素數量為_count - _freeCount

private int Initialize(int capacity)
{
    int size = HashHelpers.GetPrime(capacity); // 獲取>=capacity的最小素數
    var buckets = new int[size];
    var entries = new Entry[size];
    // ...
    return size;
}

private int FindItemIndex(T item)
{
    // ...
    int hashCode = item != null ? item.GetHashCode() : 0;
    if (typeof(T).IsValueType)
    {
        int i = GetBucketRef(hashCode) - 1; // _buckets元素從1開始
        while (i >= 0) // 存在與item相同的雜湊值，不一定存在item
        {
            ref Entry entry = ref entries[i];
            if (entry.HashCode == hashCode && EqualityComparer<T>.Default.Equals(entry.Value, item))
            {
                return i; // HashCode相等且元素相等，則查詢到元素，返回_entries索引
            }
            i = entry.Next;

            collisionCount++;
            // ...
        }
    }
    // ...
    return -1;
}

private ref int GetBucketRef(int hashCode)
{
    int[] buckets = _buckets!;
    return ref buckets[(uint)hashCode % (uint)buckets.Length]; // 使用除留餘數法構造雜湊函數
}

private bool AddIfNotPresent(T value, out int location)
{
    bucket = ref GetBucketRef(hashCode); // bucket為ref int型別，若不存在衝突，bucket應為0，因為int預設值為0
    // ...

    int index;
    if (_freeCount > 0) // 存在刪除後的空位，將元素放在空位上
    {
        index = _freeList;
        _freeCount--; // 更新刪除後空位數量
        _freeList = StartOfFreeList - entries[_freeList].Next; // 更新空位索引
    }
    else // 按_entries順序儲存元素
    {
        int count = _count;
        if (count == entries.Length) // 容量不足，擴容
        {
            Resize();
            bucket = ref GetBucketRef(hashCode);
        }
        index = count;
        _count = count + 1;
        entries = _entries;
    }

    {   // 賦值
        ref Entry entry = ref entries![index];
        entry.HashCode = hashCode;
        entry.Next = bucket - 1; // 若不存在衝突則為-1，否則形成連結串列，指向衝突的下一元素索引
        entry.Value = value;
        bucket = index + 1; // 此處對bucket賦值，即改變_buckets對應元素，即將以插入元素雜湊值為索引的_buckets值指向存放插入元素的_entries的索引+1
        _version++;
        location = index;
    }

    // ...
    return true;
}

private void Resize() => Resize(HashHelpers.ExpandPrime(_count), forceNewHashCodes: false);

public static int ExpandPrime(int oldSize)
{
    int num = 2 * oldSize;
    if ((uint)num > 2146435069u && 2146435069 > oldSize)
    {
        return 2146435069;
    }

    return GetPrime(num); // 返回原大小2倍的最小素數
}

private void Resize(int newSize, bool forceNewHashCodes)
{
    var entries = new Entry[newSize];
    Array.Copy(_entries, entries, count);
    // ...

    _buckets = new int[newSize];
    for (int i = 0; i < count; i++)
    {
        ref Entry entry = ref entries[i];
        if (entry.Next >= -1) // 更新_buckets內容
        {
            ref int bucket = ref GetBucketRef(entry.HashCode); // 獲取以新大小作為除數的雜湊函數運算得到的雜湊值
            entry.Next = bucket - 1; // 更新Next
            bucket = i + 1; // 更新_buckets的元素，指向重新計算的_entry索引+1
        }
    }

    _entries = entries;
}

public bool Remove(T item)
{
    int last = -1;
    int hashCode = item != null ? (_comparer?.GetHashCode(item) ?? item.GetHashCode()) : 0;
    ref int bucket = ref GetBucketRef(hashCode);
    int i = bucket - 1;

    while (i >= 0)
    {
        ref Entry entry = ref entries[i];
        if (entry.HashCode == hashCode && (_comparer?.Equals(entry.Value, item) ?? EqualityComparer<T>.Default.Equals(entry.Value, item)))
        {
            // 找到待刪除元素
            if (last < 0) // 待刪除元素位於連結串列頭部，更新_buckets元素值指向連結串列下一位置
            {
                bucket = entry.Next + 1;
            }
            else // 待刪除元素非連結串列頭，需更新連結串列上一元素Next值
                entries[last].Next = entry.Next;
            entry.Next = StartOfFreeList - _freeList; // 空位連結串列，記錄下一空位索引相對位置，插入時根據該值更新_freeList
            if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
                entry.Value = default!;
            _freeList = i; // 記錄刪除元素位置，下次插入元素時，會插入在此
            _freeCount++;  // 更新刪除後空位數量
            return true;
        }
        last = i; // 存在衝突，記錄連結串列上一位置
        i = entry.Next;
    }
    return false;
}