從Dictionary源碼看哈希表
- 2019 年 10 月 3 日
- 筆記
一、基本概念
哈希：哈希是一種查找演算法，在關鍵字和元素的存儲地址之間建立一個確定的對應關係，每個關鍵字對應唯一的存儲地址，這些存儲地址構成了有限、連續的存儲地址。
哈希函數：在關鍵字和元素的存儲地址之間建立確定的對應關係的函數。
哈希表是一種利用哈希函數組織數據，支援快速插入和搜索的數據結構。
哈希函數步驟：
1.散列：將關鍵字映射到hashcode(.Net中為一個int類型的值)，要求儘可能的平均分布，減少衝突
2.映射：將及其分散的hashcode轉換為有序、連續的存儲地址
哈希衝突的原因:
1.將關鍵字散列為特定長度的整數值時，產生衝突
2.在除留餘數法中，取餘數時產生衝突。
1.構造哈希函數的要點： 1.1.運算過程簡單高效，以提高哈希表的查找、插入效率 1.2.具有較好的散列性，以降低哈希衝突的概率 1.3.哈希函數應具有較大的壓縮性，以節省記憶體 2.哈希函數構造方法： 2.1.直接定址法: >>>>取關鍵字的某個線性函數值作為哈希地址: Hash(K)=α*GetHashCode(K)+C 優點：產生衝突的可能性較小 缺點：空間複雜度可能會很高，佔用大量記憶體 2.2.除留餘數法： >>>>取關鍵字除以某個常數所得的餘數作為哈希地址: Hash(K)=GetHashCode(K) MOD C。 該方法計算簡單，適用範圍廣泛，是最經常使用的一種哈希函數。該方法的關鍵是常數的選取，一般要求是接近或等於哈希表本身的長度，理論研究表明，該常數取素數時效果最好 3.解決哈希衝突的方法: 3.1.開放定址法:它是一類以發生哈希衝突的哈希地址為自變數，通過某種哈希函數得到一個新的空閑記憶體單元地址的方法，開放定址法的哈希衝突函數通常是一組； 3.2.鏈表法:當未發生衝突時，則直接存放該數據元素；當衝突產生時，把產生衝突的數據元素另外存放在單鏈表中。以上參考：
https://zhuanlan.zhihu.com/p/63142005、https://www.lmlphp.com/user/7277/article/item/355045/、http://www.nowamagic.net/academy/detail/3008050
二、從 Dictionary<TKey, TValue> 源碼解讀哈希表的構建
哈希表的關鍵思想:通過哈希函數將關鍵字映射到存儲桶。存儲桶是一個抽象概念，用於保存相同具有哈希地址的元素。
數組在所有程式語言中都是最基本的數據結構，實例化數組的時候，會在記憶體中分配一段連續的地址空間，用於保存同一類型的變數。對於哈希表來講，數組就是實際存儲元素的數據結構，數組索引就是其實際的存儲地址，而哈希函數的功能就是將n個關鍵字唯一對應到到數組索引 0~m-1(m>=n)。為了兼顧性能，哈希函數是很難避免哈希衝突的，也就是說，沒有辦法直接將哈希地址作為元素的實際地址。
假設以下情況:
- 1.聲明數組長度為13，現有8個元素需要插入到哈希表中，該8個元素對應的數組索引為[0]~[7] (實際存儲地址)
- 2.通過哈希函數，可以將8個關鍵字映射到哈希地址(範圍:0~20)
由於哈希衝突不可避免，如何通過哈希地址找到對應的實際存儲地址？答案是通過數組在元素間構建單向鏈表來作為存儲桶，將具有相同哈希地址的元素在保存在同一個存儲桶(鏈表)中，並創建一個新的數組，數組長度為'哈希地址範圍長度'，該數組使用哈希地址作為索引，並保存鏈表的第一個節點的實際存儲地址。下圖展示了Dictionary<TKey, TValue> 中的實現。
了解了大概的原理之後，有兩個問題需要解決：
1.如何通過數組構建單項鏈表：
自定義一個結構:其包含關鍵字、元素和next。Entry.next將具有相同哈希地址的元素構建為一個單向鏈表，Entry.next用於指向單向鏈表中的下一個元素所在的數組索引。通過哈希地址找到對應鏈表的第一個元素所在數組索引後，就可以找到整個單向鏈表，通過遍歷鏈表對比關鍵字是否相等，來找到元素。
public class Dictionary<TKey, TValue> { private struct Entry { // 鏈表下一元素索引 // -1:鏈表結束 // -2:freeList鏈表結束 // -3:索引為0 屬於freeList鏈表 // -4:索引為1 屬於freeList鏈表 // -n-3:索引為n 屬於freeList鏈表 public int next; public uint hashCode; public TKey key; // Key of entry public TValue value; // Value of entry } private IEqualityComparer<TKey> _comparer; //保存Entry鏈表第一個節點的索引，默認為零 //Entry實際索引=_buckets[哈希地址]-1 private int[] _buckets; private Entry[] _entries;//組成了n+1個單向鏈表 //n:用於保存哈希值相同的元素 //1:用於保存已釋放的元素 private int _freeCount;//已釋放元素的個數 private int _freeList;//最新已釋放元素的索引 private int _count;//數組中下一個將被使用的空位 private int _version;//增加刪除容量變化時,_version++ private const int StartOfFreeList = -3; } 2.如何將具有很多可能的關鍵字映射到有限的的哈希地址：
該問題分為兩個步驟：
- 1.散列函數:將所有可能的關鍵字映射到一個有限的整數值，由於可能性非常非常多，為了減少衝突，所以該整數值範圍也比較大，在.net中是一個
int類型的整數值,一般稱為GetHashCode()方法 - 2.
int值的範圍為-2147483648 ~ 2147483647，為了節省空間，不可能使用這麼大的數組去保存單向鏈表頭部元素的實際索引，所以需要壓縮數組大小。
如何解決:
- 1.使用直接定址法:
哈希地址 = (GetHashCode(Ki)*0.000000001 +21) 取整雖然在係數取很小的情況下，達到了壓縮的效果，但是哈希衝突非常高，無法實現高效的查詢。如果係數取大，空間複雜度又會特別高。 - 2.使用除留餘數法:
哈希地址 = GetHashCode(Ki) MOD C實際證明該方法的哈希衝突更少，在C為素數的情況下，效果更好。
在Dictionary<TKey, TValue>內部使用數組Entry[]來保存關鍵字和元素，使用 private int[] _buckets來保存單向鏈表頭部元素所在的數組索引。上面提到，因為哈希衝突是不可避免的，對於有n個哈希地址的哈希表來說，Dictionary<TKey, TValue>一共構建了n+1個單向鏈表。另外單獨的一個鏈表，用於保存已經釋放的數組空位。
增加元素邏輯：
- 1.使用
_count來作為數組的空位指針，_count值永遠指向數組中下一個將被使用的空位 - 2.使用
_freeList來保存釋放鏈表的頭部元素所在數組(_entries[])索引 - 3.如果釋放鏈表為空的情況下，保存元素到
_entries[_count],否則保存到_entries[_freeList] - 4.根據關鍵字獲取哈希地址,如果
_buckets[哈希地址]中的值不為-1，則將剛保存元素的next置為_buckets[哈希地址]值(將元素加到單向鏈表的頭部)。 - 5.更新
_buckets[哈希地址]的值為_freeList或者_count
public bool TryInsert(TKey key, TValue value) { if (key == null) { throw new ArgumentNullException("TKey不能為null"); } if (_buckets == null) { Initialize(0); } Entry[] entries = _entries; IEqualityComparer<TKey> comparer = _comparer; uint hashCode = (uint)comparer.GetHashCode(key); int collisionCount = 0;//哈希碰撞次數 ref int bucket = ref _buckets[hashCode % (uint)_buckets.Length];//元素所在的實際地址 // Entry鏈表最新索引 // -1:鏈表結束 // >=0:有下一節點 int i = bucket - 1; //統計哈希碰撞次數 do { if ((uint)i >= (uint)entries.Length) { break; } if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { entries[i].value = value; _version++; return true; } i = entries[i].next; if (collisionCount >= entries.Length) { throw new InvalidOperationException("不支援多執行緒操作"); } collisionCount++; } while (true); bool updateFreeList = false; int index; //如果FreeList鏈表中長度大於0 //優先使用FreeList if (_freeCount > 0) { index = _freeList; updateFreeList = true; _freeCount--; } else { int count = _count; //超出數組大小 if (count == entries.Length) { //將數組長度擴展為大於原長度兩倍的最小素數 var forceNewHashCodes = false; var newSize = HashHelpers.ExpandPrime(_count); Resize(newSize, forceNewHashCodes); bucket = ref _buckets[hashCode % (uint)_buckets.Length]; } index = count; _count = count + 1; entries = _entries; } ref Entry entry = ref entries[index]; if (updateFreeList) { _freeList = StartOfFreeList - entries[_freeList].next; } entry.hashCode = hashCode; // Value in _buckets is 1-based entry.next = bucket - 1; entry.key = key; entry.value = value; // Value in _buckets is 1-based bucket = index + 1; _version++; // 如果不採用隨機字元串哈希，並達到碰撞次數時，切換為默認比較器(採用隨機字元串哈希) if (default(TKey) == null && collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer) // TODO-NULLABLE: default(T) == null warning (https://github.com/dotnet/roslyn/issues/34757) { _comparer = null; Resize(entries.Length, true); } return true; }刪除元素邏輯：
- 1.根據關鍵字獲取哈希地址,鏈表頭部元素索引=
_buckets[哈希地址]。 - 2.遍歷鏈表，找到對應關鍵字的元素。
- 3.將元素賦為默認值，並加入到釋放鏈表的頭部。
- 4.構建上一個節點與下一個節點之間的指向關係
lastEle.next = nextEle.index
/// .NetCore3.0 Remove執行之後_version沒有自增 public bool Remove(TKey key) { int[] buckets = _buckets; Entry[] entries = _entries; int collisionCount = 0; if (buckets != null) { uint hashCode = (uint)(_comparer?.GetHashCode(key) ?? key.GetHashCode()); uint bucket = hashCode % (uint)buckets.Length; int last = -1;//記錄上一個節點,在刪除中間節點時，將前後節點建立關聯 int i = buckets[bucket] - 1; while (i >= 0) { ref Entry entry = ref entries[i]; if (entry.hashCode == hashCode && _comparer.Equals(entry.key, key)) { if (last < 0) { //刪除的節點為首節點,保存最新索引 buckets[bucket] = entry.next + 1; } else { //刪除節點不是首個節點,建立前後關係 entries[last].next = entry.next; } // 將刪除節點加入FreeList頭部 entry.next = StartOfFreeList - _freeList; // 置為默認值 if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>()) { entry.key = default; } if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>()) { entry.value = default; } // 保存FreeList頭部索引 _freeList = i; _freeCount++; return true; } // 當前節點不是目標節點 last = i; i = entry.next; if (collisionCount >= entries.Length) { // The chain of entries forms a loop; which means a concurrent update has happened. // Break out of the loop and throw, rather than looping forever. // ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported(); throw new InvalidOperationException("不支援多執行緒操作"); } collisionCount++; } } return false; }三、GitHub源碼地址
四、String.GetHashCode()方法
不採用隨機字元串的方法：源碼地址
對於某一個確定的字元串，返回確定的hashcode，缺點：容易被哈希洪水攻擊。
// Use this if and only if 'Denial of Service' attacks are not a concern (i.e. never used for free-form user input), // or are otherwise mitigated internal unsafe int GetNonRandomizedHashCode() { fixed (char* src = &_firstChar) { Debug.Assert(src[this.Length] == '', "src[this.Length] == '\0'"\0'"); Debug.Assert(((int)src) % 4 == 0, "Managed string should start at 4 bytes boundary"); uint hash1 = (5381 << 16) + 5381; uint hash2 = hash1; uint* ptr = (uint*)src; int length = this.Length; while (length > 2) { length -= 4; // Where length is 4n-1 (e.g. 3,7,11,15,19) this additionally consumes the null terminator hash1 = (BitOperations.RotateLeft(hash1, 5) + hash1) ^ ptr[0]; hash2 = (BitOperations.RotateLeft(hash2, 5) + hash2) ^ ptr[1]; ptr += 2; } if (length > 0) { // Where length is 4n-3 (e.g. 1,5,9,13,17) this additionally consumes the null terminator hash2 = (BitOperations.RotateLeft(hash2, 5) + hash2) ^ ptr[0]; } return (int)(hash1 + (hash2 * 1566083941)); } }採用隨機字元串的方法: 源碼地址
特點：
- 1.兩個字元串相等，返回相同的哈希值
- 2.不同的字元串可以返回相同的哈希值
- 3.基於不同的.Net實現、.Net平台、.Net版本、應用程式域，同一個字元串可能返回不同的哈希值
- 4.哈希值決不能在創建它們的應用程式域的外部使用
public override int GetHashCode() { ulong seed = Marvin.DefaultSeed; // Multiplication below will not overflow since going from positive Int32 to UInt32. return Marvin.ComputeHash32(ref Unsafe.As<char, byte>(ref _firstChar), (uint)_stringLength * 2 /* in bytes, not chars */, (uint)seed, (uint)(seed >> 32)); }