在.NET中，System.Collection及System.Collection.Generic命名空間中提供了一系列的集合類，HashSet定義在System.Collections.Generic中，是一個不重復、無序的泛型集合，本文學習下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 = https://www.cnblogs.com/louzixl/archive/2022/03/12/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 = https://www.cnblogs.com/louzixl/archive/2022/03/12/default!;
}
_freeList = i; // 記錄洗掉元素位置，下次插入元素時，會插入在此
_freeCount++; // 更新洗掉后空位數量
return true;
}
last = i; // 存在沖突，記錄鏈表上一位置
i = entry.Next;
}
return false;
}
總結
通過上文分析可以看出HashSet是個設計巧妙，使用靈活的資料結構，基于哈希表的思想，HashSet的插入、查找速度很快，只需要簡單的計算，基于此，HashSet也具備了高性能集合運算的條件，可以高效執行合并、裁剪等運算，但這也導致了HashSet無法存盤重復元素，洗掉時空位鏈表的設計非常巧妙，但也導致了HashSet無序，也就無法使用索引，因此，當選擇資料結構時，如果需要包含重復元素，或者需要有序，則應考慮使用其它資料結構，如List，
另外，Dictionary與HashSet原理相同，只是HashSet只有Key，沒有Value，
參考文章
- HashSet
Class - HashSet.cs
- DotNet Dictionary 實作簡介
- 哈希表演算法原理
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/441887.html
標籤：.NET技术