阅读量:0
entries用于存储当前每个节点的数据，其中四个字段分别表示：
hashCode：key对应的hash值 next：处理hash冲突，可以理解为是一个链表结构，邻接表 key：存储的key value：存储的valuebuckets存储桶，用于存储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) cast if ((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 对应的 hashCode public int next; // 指向上一个存储的对象的index public TKey key; // 存储的 Key public 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); } } } 一些参考：
