解析 C# Dictionary 代码

 entries用于存储当前每个节点的数据，其中四个字段分别表示：

hashCode：key对应的hash值next：处理hash冲突，可以理解为是一个链表结构，邻接表key：存储的keyvalue：存储的value

buckets存储桶，用于存储hash映射

设计的巧妙之处在这个桶buckets，每个hashCode取模（当前size最近的大于size的素数），这里用素数是为了减少hash冲突的频率，key取hash再取模=index，就放入存储桶中，buckets[index]记录的是当前key对应的第一个entries的下标位置，entries不管是增加还是删除，会优先连续的放在数组中，举例删了index[2]的数据，这个时候加入一个数据，会无脑放在这个index[2]的位置，同理[.next]也维护了删除的单向链表的数据，所有删掉的index下标数据，也是存在链中等待新的数据插入，这里是反向链表获取index，所以可以理解为最早清理的index，最晚被用到。

具体可以看看代码

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Text;namespace DictionaryTest
{public static class MHashHelpers{public const int MaxPrimeArrayLength = 0x7FEFFFFD;public static readonly int[] 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};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);}public static int GetPrime(int min){for (int i = 0; i < primes.Length; i++){int prime = primes[i];if (prime >= min) return prime;}for (int i = (min | 1); i < Int32.MaxValue; i += 2){if (IsPrime(i) && ((i - 1) % 101 != 0))return i;}return min;}public static int ExpandPrime(int oldSize){int newSize = 2 * oldSize;// Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow.// Note that this check works even when _items.Length overflowed thanks to the (uint) castif ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize){Contract.Assert(MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");return MaxPrimeArrayLength;}return GetPrime(newSize);}}public class MDictionary<TKey, TValue>{private struct Entry{public int          hashCode;           // 存储 Key 对应的 hashCodepublic int          next;               // 指向上一个存储的对象的indexpublic TKey         key;                // 存储的 Keypublic TValue       value;              // 存储的 Value}private IEqualityComparer<TKey> comparer;private int[]           buckets;            // 定长的存储桶private Entry[]         entries;            // 定长的存储元素的数组private int             count;              // 当前元素个数private int             freeList;           // 删掉元素之后，还空余的位置，最新的一个，根据entries链表指向上一个private int             freeCount;          // 空余的个数public MDictionary() : this(0) { }public MDictionary(int capacity){if (capacity > 0){Initialize(capacity);}this.comparer = EqualityComparer<TKey>.Default;}private void Initialize(int capacity){int size = MHashHelpers.GetPrime(capacity);buckets = new int[size];entries = new Entry[size];for (int i = 0; i < buckets.Length; i++){buckets[i] = -1;entries[i].hashCode = -1;entries[i].next = -1;entries[i].key = default(TKey);entries[i].value = default(TValue);}count = 0;freeList = -1;freeCount = 0;}private void Resize(){Console.WriteLine($"[Resize]");int newSize = MHashHelpers.ExpandPrime(count);int[] newBuckets = new int[newSize];for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;Entry[] newEntries = new Entry[newSize];Array.Copy(entries, 0, newEntries, 0, count);for (int i = 0; i < count; i++){if (newEntries[i].hashCode != -1){newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);}}for (int i = 0; i < count; i++){if (newEntries[i].hashCode != -1){int bucket = newEntries[i].hashCode % newSize;newEntries[i].next = newBuckets[bucket];newBuckets[bucket] = i;}}buckets = newBuckets;entries = newEntries;PrintAll();}public void Insert(TKey key, TValue value){Console.WriteLine($"[Insert] {key} {value}");int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;int targetBucket = hashCode % buckets.Length;for (int i = buckets[targetBucket]; i != -1; i = entries[i].next){if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)){entries[i].value = value;PrintAll();return;}}int index;if (freeCount > 0){index = freeList;freeList = entries[index].next;freeCount--;}else{if (count == buckets.Length){Resize();targetBucket = hashCode % buckets.Length;}index = count;count++;}entries[index].hashCode = hashCode;entries[index].next = buckets[targetBucket];entries[index].key = key;entries[index].value = value;buckets[targetBucket] = index;PrintAll();}public bool Remove(TKey key){Console.WriteLine($"[Remove] {key}");int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;int bucket = hashCode % buckets.Length;int last = -1;for (int i = buckets[bucket]; i != -1; last = i, i = entries[i].next){if (comparer.Equals(key, entries[i].key) && entries[i].hashCode == hashCode){if (last == -1){buckets[bucket] = entries[i].next;}else{entries[last].next = entries[i].next;}entries[i].hashCode = -1;entries[i].next = -1;entries[i].key = default(TKey);entries[i].value = default(TValue);freeList = i;freeCount++;PrintAll();return true;}}PrintAll();return false;}public bool TryGetValue(TKey key, out TValue value){Console.WriteLine($"[TryGetValue] {key}");int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;int targetBucket = hashCode % buckets.Length;for (int i = buckets[targetBucket]; i != -1; i = entries[i].next){if (comparer.Equals(key, entries[i].key) && entries[i].hashCode == hashCode){value = entries[i].value;return true;}}value = default(TValue);return false;}public void Clear(){Console.WriteLine($"[Clear]");if (count > 0){for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;Array.Clear(entries, 0, count);count = 0;freeList = -1;freeCount = 0;}PrintAll();}public void PrintAll(){Console.WriteLine($"[PrintAll]");StringBuilder bucketInfo = new StringBuilder();StringBuilder entriesInfo = new StringBuilder();for (int i = 0; i < buckets.Length; i++){bucketInfo.Append($"{i} [{buckets[i]}]").Append("\n");}Console.WriteLine("buckets: " + buckets.Length);Console.Write(bucketInfo);for (int i = 0; i < entries.Length; i++){entriesInfo.Append($"{i} [{entries[i].hashCode}={entries[i].next}={entries[i].key}={entries[i].value}]").Append("\n");}Console.WriteLine("entries: " + entries.Length);Console.Write(entriesInfo);}}class Program{static void Main(string[] args){Console.WriteLine("Hello World!");MDictionary<int, string> dict = new MDictionary<int, string>(2);dict.Clear();dict.Insert(0, "000");dict.Insert(1, "111");dict.Remove(0);dict.Insert(2, "222");dict.Insert(3, "333");dict.Insert(4, "444");dict.Remove(2);dict.Insert(5, "555");dict.Insert(6, "666");dict.Remove(1);dict.Insert(7, "777");dict.Insert(14, "1414");dict.Insert(21, "2121");dict.Remove(14);dict.Insert(28, "2828");dict.Insert(35, "3535");dict.Insert(42, "4242");dict.Insert(55, "5555");dict.Remove(21);}}
}

一些参考：

https://zhuanlan.zhihu.com/p/96633352

Reference Source

https://www.cnblogs.com/pengze0902/p/17830689.html