.NET中的HashSet原理是什么

這篇文章主要介紹“.NET中的HashSet原理是什么”，在日常操作中，相信很多人在.NET中的HashSet原理是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”.NET中的HashSet原理是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

哈希表原理

HashSet是基于哈希表的原理實現的，學習HashSet首先要了解下哈希表。

哈希表（hash table, 也叫散列表）是根據key直接訪問存儲位置的數據結構，它通過一個鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問，加快了查找速度。

上述函數即為哈希函數，哈希函數應盡量計算簡單以提高插入、檢索效率；計算得到的地址應盡量分布均勻，以降低哈希沖突；應具有較大的壓縮性，以節省內存。常見的哈希函數構造方法有直接定址法、除留余數法、數字分析法等。HashSet采用除留余數法，將元素的HashCode除以某個常數（哈希表Size）的余數作為地址，常數通常選取一個素數。

兩個相等的對象的哈希值相同，但兩個不等的對象的哈希值是有可能相同的，這就是哈希沖突。處理沖突的方法有開放定址法、鏈表法、雙散列法等。HashSet使用鏈表法，將沖突元素放在鏈表中。

哈希表是一種用于高性能集合操作的數據結構，它有如下特點：

• 無序、不重復；插入、查找時間復雜度為O(1)；

• 不使用索引；

• 容量不足時自動擴容，但擴容成本高；

• 可提供很多高性能集合操作，如合并、裁剪等；

HashSet實現

HashSet內置了兩個數組，如下。_buckets中存放由哈希函數計算得到的索引值，_buckets中的值從1開始，因此在使用時需要-1。該值即為_entries數組的相對索引，若未發生沖突，指向的值即為待查找元素的相對索引。如果發生了沖突，根據沖突鏈表也可以快速定位到元素。_entries存放的是Entry對象，Entry類型如下所示。HashCode為元素的哈希值，在查找、插入、刪除、擴容等操作時都會用到。Value存儲數據。Next在不同時刻有不同的作用，當Entry在列表中時，形成沖突鏈表，其Next指向沖突鏈表的下一元素，鏈表最后一個元素的Next值為-1；若Entry已被列表刪除，形成空位鏈表，其Next指向空位鏈表的下一元素，空位鏈表的最后一個元素值為-2。

HashSet還有幾個關鍵成員：_count、_freeList、_freeCount。_count表示添加元素數量，注意它并不是實際存儲的元素數量，因為在刪除元素時未更新它。_freeList為空位鏈表頭，其值指向被刪除的_entries索引，_entries[_freeList].Next指向下一空位的相對位置。_freeCount表示空位數量，列表實際存儲的元素數量為_count - _freeCount。

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

HashSet提供了多個構造函數重載，如果不傳任何參數，不會初始化_buckets和_entries。當添元素時，會調用Initialize(0)。Initialize方法接受一個int參數，該參數表示需要初始化的列表容量。實際初始化的列表容量為大于等于該值的最小素數。取素數作為列表長度是因為該值作為使用除留余數法構造的哈希函數的除數，對素數求余結果分布更均勻，減少了沖突的發生。

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

查找元素時，首先調用元素的GetHashCode方法計算哈希值，然后調用GetBucketRef方法執行哈希函數運算，獲得索引。GetBucketRef的返回值-1為真實索引i，若i為-1，則未找到元素。若i>=0，表示列表中存在與待查找元素哈希值相同的元素，但相等的哈希值并不一定表示元素相等，還要進一步判斷HashCode，若HashCode相等，再判斷元素是否相等，滿足則查找到元素，返回_entries的索引i。

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]; // 使用除留余數法構造哈希函數
}

插入元素時，首先會查找待插入的元素是否存在，HashSet是不重復的，因此若插入元素已存在會直接返回false。若不存在元素，則會尋找存放元素的index。如果存在刪除后的空位，則會將元素放到_freeList指向的空位上；如果不存在空位，則按_entries順序插入元素。找到index后，即可將元素的HashCode及元素賦值到_entries[index]對應字段，當沒有沖突時，Next值為-1；若存在沖突，則形成鏈表，將其添加到鏈表頭，Next指向沖突的下一位置。

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;
}

插入時若列表容量不足，會調用Resize方法進行擴容。擴容后的大小為大于等于原大小2倍的最小素數。獲取待擴容的大小后，以新大小重新分配entries內存，并調用Array.Copy方法將原內容拷貝到新位置。由于列表長度變了，因此哈希值會變，因此需要更新_buckets的內容(_entries索引)，同理entry.Next的值也要更新。

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;
}

當刪除元素時，首先查找待刪除元素是否存在。若哈希值存在沖突，會記錄沖突鏈表的上一索引。查找到元素后，需要更新沖突鏈表的指針。刪除元素后，會更新_freeCount空位數量，并將刪除元素索引賦值給_freeList，記錄刪除空位，添加到空位鏈表頭，其Next指向下一空位的相對位置。插入元素時，會將元素插入到_freeList記錄的空位索引處，并根據該空位的Next更新_freeList的值。

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;
}

到此，關于“.NET中的HashSet原理是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！