無(wú)論是實(shí)際的項(xiàng)目中，還是在我們學(xué)習(xí)的過(guò)程中，都會(huì)重點(diǎn)的應(yīng)用到Dictionary<TKey, TValue>這個(gè)存儲(chǔ)類型。每次對(duì)Dictionary<TKey, TValue>的添加都包含一個(gè)值和與其關(guān)聯(lián)的鍵， 使用鍵檢索值的速度非?？?，接近 O (1) ，因?yàn)?nbsp;Dictionary<TKey, TValue> 類是作為哈希表實(shí)現(xiàn)的。首先我們來(lái)從一個(gè)簡(jiǎn)單的例子開(kāi)始，以下是對(duì)一個(gè)字典的創(chuàng)建和賦值。

Dictionary<int, string> openWith = new Dictionary<int, string>();
openWith.Add(1000, "key值為1000");
openWith.Add(1001, "key值為1001");

相信絕大部分的開(kāi)發(fā)人員對(duì)以上示例不是會(huì)陌生，那么Dictionary<TKey, TValue>的實(shí)現(xiàn)原理是什么樣的呢？在字典的初始化、賦值、取值、擴(kuò)容的實(shí)現(xiàn)原理是什么樣的呢？很多時(shí)候我們需要知其然，更需要知其所以然。接下來(lái)我們將從其內(nèi)存的存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)、取值的邏輯、擴(kuò)容原則等幾個(gè)視角進(jìn)行仔細(xì)的了解 。那我們就沿著CoreFX中Dictionary<TKey, TValue>的實(shí)現(xiàn)源碼來(lái)做一個(gè)簡(jiǎn)單的學(xué)習(xí)和思考，這里需要特別注意一下：

學(xué)習(xí)和分析源碼時(shí)，不要先入為主，要按照框架和源碼的邏輯進(jìn)行解讀，記錄下不懂的地方重點(diǎn)分析，最后將整個(gè)邏輯串聯(lián)起來(lái)。如果我們一開(kāi)始就設(shè)定了邏輯為A-B-C，但是讀到一個(gè)階段的時(shí)候發(fā)現(xiàn)變成了C-B-A，這個(gè)時(shí)候就無(wú)法再繼續(xù)進(jìn)行下去，因?yàn)榫唧w的實(shí)現(xiàn)過(guò)程中會(huì)有很多因素造成局部調(diào)整，我們可以在解讀完畢之后，將實(shí)際的邏輯與個(gè)人前期理解的邏輯的差異進(jìn)行比較，找出原因并做分析。

一、Dictionary<TKey, TValue>初始化

Dictionary<TKey, TValue>的構(gòu)造方法較多，我們來(lái)看一下其中的基礎(chǔ)實(shí)現(xiàn)方法，首先看一下對(duì)應(yīng)的源碼（源碼中不必要的部分已經(jīng)做了部分刪減，保留了核心的實(shí)現(xiàn)邏輯）。

public Dictionary(int capacity, IEqualityComparer<TKey>? comparer)
  {
      if (capacity > 0) Initialize(capacity);
      if (!typeof(TKey).IsValueType)
      {
         _comparer = comparer ?? EqualityComparer<TKey>.Default;
         if (typeof(TKey) == typeof(string) && NonRandomizedStringEqualityComparer.GetStringComparer(_comparer!) is IEqualityComparer<string> stringComparer)
         {
          _comparer = (IEqualityComparer<TKey>)stringComparer;
         }
      }
      else if (comparer is not null && comparer != EqualityComparer<TKey>.Default)
      {
         _comparer = comparer;
     }
 }

以上的實(shí)現(xiàn)邏輯重點(diǎn)包含了兩個(gè)部分，第一部分：對(duì)Dictionary<TKey, TValue>的容量初始化；第二部分是Dictionary<TKey, TValue>的IEqualityComparer? comparer的初始化，本文重點(diǎn)是對(duì)Dictionary<TKey, TValue>的存儲(chǔ)結(jié)構(gòu)進(jìn)行分析，涉及到比較器的實(shí)現(xiàn)邏輯，將放在后續(xù)的章節(jié)中進(jìn)行重點(diǎn)介紹。

我們接下來(lái)看一下Initialize()的實(shí)現(xiàn)邏輯進(jìn)行一個(gè)簡(jiǎn)單的介紹，首先一起來(lái)看一下對(duì)應(yīng)的源碼實(shí)現(xiàn)(非必要部分已做刪減，方便大家可以直觀的查看)。

private int Initialize(int capacity)
{
  int size = HashHelpers.GetPrime(capacity);
  int[] buckets = new int[size];
  Entry[] entries = new Entry[size];
  _freeList = -1;
#if TARGET_64BIT
  _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)size);
#endif
  _buckets = buckets;
  _entries = entries;
  return size;
}

從上面的源碼可以看出，根據(jù)傳入的capacity參數(shù)來(lái)設(shè)定字典對(duì)應(yīng)的相關(guān)容量大小，其中包含兩部分，第一部分： 根據(jù)設(shè)定的容量(capacity)大小，計(jì)算對(duì)應(yīng)的buckets和entries大小，關(guān)于為什么使用buckets和entries兩個(gè)數(shù)組結(jié)構(gòu)，我們將在下一節(jié)重點(diǎn)介紹；第二部分：判斷當(dāng)前機(jī)器的位數(shù)，計(jì)算對(duì)應(yīng)的_fastModMultiplier。我們看一下HashHelpers.GetPrime(capacity)的計(jì)算邏輯。(該類在System.Collections命名空間下，其對(duì)應(yīng)的類型定義為：internal static partial class HashHelpers)

public static int GetPrime(int min)
{
  foreach (int prime in Primes)
  {
    if (prime >= min) return prime;
    for (int i = (min | 1); i < int.MaxValue; i += 2)
    {
        if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i;
     }
     return min;
   }
}

HashHelpers用于計(jì)算和維護(hù)哈希表容量的素?cái)?shù)值，為什么哈希表需要使用素?cái)?shù)？主要是為了減少哈希沖突（hash collisions）的發(fā)生，素?cái)?shù)的選擇能夠減少共同的因子，減小哈希沖突的可能性。此外，選擇素?cái)?shù)還能夠確保在哈希表的容量變化時(shí)，不容易出現(xiàn)過(guò)多的重復(fù)。如果容量選擇為一個(gè)合數(shù)（非素?cái)?shù)），那么在容量變化時(shí)，可能會(huì)導(dǎo)致新容量與舊容量有相同的因子，增加哈希沖突的風(fēng)險(xiǎn)。

接下來(lái)我們沿著GetPrime()的調(diào)用關(guān)系來(lái)看整個(gè)哈希表容量的計(jì)算邏輯，HashHelpers設(shè)定了一個(gè)Primes[]的只讀素?cái)?shù)數(shù)組，具體的元素如下，至于什么使用這樣的素?cái)?shù)的數(shù)組，主要是這些素?cái)?shù)在實(shí)踐中已經(jīng)被證明是有效的，適用于許多常見(jiàn)的使用場(chǎng)景，更多的是有助于在哈希表等數(shù)據(jù)結(jié)構(gòu)中提供更好的性能。

internal static ReadOnlySpan<int> Primes => new int[]
{
  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
};

GetPrime()會(huì)首先循環(huán)Primes[]，依次判斷設(shè)定的min大小與素?cái)?shù)表元素的關(guān)系，若素?cái)?shù)表中的元素大于min，則直接去對(duì)應(yīng)的素?cái)?shù)，無(wú)需后續(xù)的計(jì)算，如果設(shè)置的min不在預(yù)定的素?cái)?shù)表中，則進(jìn)行素?cái)?shù)的計(jì)算。關(guān)于素?cái)?shù)的計(jì)算邏輯，借助本文開(kāi)頭的Dictionary<TKey, TValue>的定義和賦值進(jìn)行說(shuō)明，首先對(duì)min和1進(jìn)行按位或運(yùn)算，初始化過(guò)程中未對(duì)capacity賦值時(shí)，則(min | 1)為1，對(duì)進(jìn)行位運(yùn)算后的i值校驗(yàn)是否符合素?cái)?shù)定義，再進(jìn)行((i - 1) % HashPrime != 0)運(yùn)算，其中HashPrime = 101，用于在哈希算法中作為質(zhì)數(shù)因子(101是一個(gè)相對(duì)小的質(zhì)數(shù)，可以減少哈希碰撞的可能性，并且在計(jì)算哈希時(shí)更加高效)，對(duì)于初始化未設(shè)置容量的Dictionary<TKey, TValue>，計(jì)算獲取得到的容量為int size=3。(即3*4*8=72(bit))

(注意：對(duì)于已設(shè)定了capacity的Dictionary，按照以上的邏輯進(jìn)行計(jì)算對(duì)應(yīng)的size值。這里就不再做過(guò)多介紹）

計(jì)算獲取到size值后，設(shè)置空閑列表為-1(_freeList = -1)。根據(jù)編譯時(shí)的運(yùn)行機(jī)器的位數(shù)進(jìn)行分類處理，若機(jī)器為非64位，則對(duì)buckets和entries兩個(gè)數(shù)組進(jìn)行初始化。若機(jī)器為64位是，則需要進(jìn)行重新計(jì)算，獲取_fastModMultiplier，其計(jì)算邏輯如下：

public static ulong GetFastModMultiplier(uint divisor) => ulong.MaxValue / divisor + 1;

以上的計(jì)算結(jié)果返回除數(shù)的近似倒數(shù)，計(jì)算用于快速取模運(yùn)算的乘法因子。

通過(guò)以上的計(jì)算過(guò)程，我們可以對(duì)Dictionary<TKey, TValue>的容量計(jì)算有一個(gè)簡(jiǎn)單的認(rèn)識(shí)，接下來(lái)我們來(lái)具體看一下用于存儲(chǔ)數(shù)據(jù)和哈希索引的兩個(gè)數(shù)組。

二、Dictionary<TKey, TValue>的存儲(chǔ)基礎(chǔ)結(jié)構(gòu)

對(duì)于Dictionary<TKey, TValue>的兩個(gè)重要數(shù)組buckets和entries，我們來(lái)具體的分析一下。首先來(lái)看一下Entry[]?_entries的實(shí)際的數(shù)據(jù)結(jié)構(gòu)：

private struct Entry
{
  public uint hashCode;
  public int next;
  public TKey key;
  public TValue value;
}

在Dictionary<TKey, TValue>中實(shí)際存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)是Entry[]，其中數(shù)組的每個(gè)元素是一個(gè)Entry，該類型為一個(gè)結(jié)構(gòu)體，用于在哈希表內(nèi)部存儲(chǔ)每個(gè)鍵值對(duì)的信息，其中定義的key和value則是我們?cè)谠O(shè)置字典時(shí)添加的鍵值對(duì)，那么對(duì)于另外兩個(gè)屬性需要重點(diǎn)分析一下。

hashCode為在添加key時(shí)，將key進(jìn)行計(jì)算獲取得到的哈希值，哈希值的計(jì)算過(guò)程中，需要對(duì)key進(jìn)行按類別進(jìn)行計(jì)算，C#中對(duì)數(shù)值類型、字符串、結(jié)構(gòu)體、對(duì)象的哈希值計(jì)算邏輯都不相同，其中對(duì)于"數(shù)值類型"的哈希值計(jì)算邏輯為"數(shù)字類型的哈希碼生成邏輯通常是將數(shù)字類型的值轉(zhuǎn)換為整數(shù)，然后將該整數(shù)作為哈希碼。"對(duì)于字符串的哈希值計(jì)算邏輯為"默認(rèn)的字符串哈希碼計(jì)算方式采用了所謂的“Jenkins One-at-a-Time Hash”算法的變體。"對(duì)于結(jié)構(gòu)體和對(duì)象的哈希值計(jì)算邏輯就不做具體介紹。

next通常用于處理哈希沖突，即多個(gè)鍵具有相同的哈希碼的情況。next是一個(gè)索引，指向哈希表中下一個(gè)具有相同哈希碼的元素。其中next=-1時(shí)，表示鏈表結(jié)束；next=-2 表示空閑列表的末尾，next=-3 表示在空閑列表上的索引 0，next=-4 表示在空閑列表上的索引 1，后續(xù)則依次類推。

Entry通過(guò)使用結(jié)構(gòu)體而不是類，可以減少內(nèi)存開(kāi)銷，因?yàn)榻Y(jié)構(gòu)體是值類型，而類是引用類型。結(jié)構(gòu)體在棧上分配，而類在堆上分配。

以上介紹了Entry的結(jié)構(gòu)和對(duì)應(yīng)的屬性字段，接下來(lái)我們?cè)賮?lái)看一下int[] buckets的結(jié)構(gòu)和計(jì)算邏輯，buckets是一個(gè)簡(jiǎn)單的int類型的數(shù)組，這樣的數(shù)組通常用于存儲(chǔ)哈希桶的信息。每個(gè)桶實(shí)際上是一個(gè)索引，指向一個(gè)鏈表或鏈表的頭部，用于解決哈希沖突。

private ref int GetBucket(uint hashCode)
{
   int[] buckets = _buckets!;
 #if TARGET_64BIT
   return ref buckets[HashHelpers.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)];
 #else
   return ref buckets[(uint)hashCode % buckets.Length];
 #endif
 }

GetBucket()用于在哈希表中獲取桶索引，其中參數(shù)hashCode為key對(duì)應(yīng)的哈希碼，在64位目標(biāo)體系結(jié)構(gòu)下，使用 HashHelpers.FastMod 方法進(jìn)行快速模運(yùn)算，而在32位目標(biāo)體系結(jié)構(gòu)下，使用普通的取模運(yùn)算。那么為什么在Dictionary<TKey, TValue>中維護(hù)一個(gè)用來(lái)存儲(chǔ)哈希表的桶呢？主要有以下4個(gè)目的：

(1)、解決哈希沖突：兩個(gè)或多個(gè)不同的鍵經(jīng)過(guò)哈希函數(shù)得到相同的哈希碼，導(dǎo)致它們應(yīng)該存儲(chǔ)在哈希表的相同位置。通過(guò)使用桶，可以在同一個(gè)位置存儲(chǔ)多個(gè)元素，解決了哈希沖突的問(wèn)題。

(2)、提供快速查找：通過(guò)哈希函數(shù)計(jì)算鍵的哈希碼，然后將元素存儲(chǔ)在哈希表的桶中，可以在常數(shù)時(shí)間內(nèi)（平均情況下）定位到存儲(chǔ)該元素的位置，實(shí)現(xiàn)快速的查找。

(3)、支持高效的插入和刪除：當(dāng)插入元素時(shí)，通過(guò)哈希函數(shù)確定元素應(yīng)該存儲(chǔ)的桶，然后將其添加到桶的鏈表或其他數(shù)據(jù)結(jié)構(gòu)中。當(dāng)刪除元素時(shí)，同樣可以快速定位到存儲(chǔ)元素的桶，并刪除該元素。

(4)、平衡負(fù)載：哈希表的性能與負(fù)載因子相關(guān)，而負(fù)載因子是元素?cái)?shù)量與桶數(shù)量的比值。使用適當(dāng)數(shù)量的桶可以幫助平衡負(fù)載，防止哈希表變得過(guò)度擁擠，從而保持其性能。在不同的哈希表實(shí)現(xiàn)可能使用不同的數(shù)據(jù)結(jié)構(gòu)，如鏈表、樹等，C#的Dictionary中使用一個(gè)int[]維護(hù)這個(gè)哈希表的桶索引。

三、Dictionary<TKey, TValue>的TryAdd的實(shí)現(xiàn)方式

以上主要介紹了Dictionary<TKey, TValue>的初始化、數(shù)據(jù)對(duì)應(yīng)的存儲(chǔ)和哈希表桶索引的存儲(chǔ)結(jié)構(gòu)，現(xiàn)在我們具體看一下Dictionary<TKey, TValue>的添加元素的實(shí)現(xiàn)方式，下面對(duì)C#的實(shí)現(xiàn)代碼進(jìn)行了精簡(jiǎn)，刪除當(dāng)前并不關(guān)注的部分。

本文實(shí)例中對(duì)key賦值的為整數(shù)類型，部分對(duì)于非數(shù)值類型、調(diào)試代碼等進(jìn)行刪減。(由于對(duì)于對(duì)象或者設(shè)置了比較器邏輯相對(duì)繁瑣，將在下文中進(jìn)行介紹)

private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
{
  Entry[]? entries = _entries;
  uint hashCode = (uint) key.GetHashCode() ;
  uint collisionCount = 0;
  ref int bucket = ref GetBucket(hashCode);
  int i = bucket - 1;
  int index;
  if (_freeCount > 0)
  {
    index = _freeList;
    _freeList = StartOfFreeList - entries[_freeList].next;
    _freeCount--;
  }
  else
  {
    int count = _count;
    if (count == entries.Length)
    {
       Resize();
       bucket = ref GetBucket(hashCode);
     }
     index = count;
     _count = count + 1;
      entries = _entries;
   }
   
   ref Entry entry = ref entries![index];
   entry.hashCode = hashCode;
   entry.next = bucket - 1; 
   entry.key = key;
   entry.value = value;
   bucket = index + 1; 
   _version++;
   
 return true;
}

以上的源碼中的實(shí)現(xiàn)邏輯中核心包含3個(gè)部分，分別是計(jì)算hashCode、計(jì)算哈希表桶索引的bucket、Dictionary擴(kuò)容，上一節(jié)中已經(jīng)介紹了前兩個(gè)實(shí)現(xiàn)邏輯，本節(jié)重點(diǎn)介紹Dictionary<TKey, TValue>的擴(kuò)容邏輯，我們來(lái)看一下Resize()的實(shí)現(xiàn)邏輯。

private void Resize() => Resize(HashHelpers.ExpandPrime(_count), false);

private void Resize(int newSize, bool forceNewHashCodes)
{
   Entry[] entries = new Entry[newSize];
   int count = _count;
   Array.Copy(_entries, entries, count);
   _buckets = new int[newSize];
#if TARGET_64BIT
   _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
#endif
   for (int i = 0; i < count; i++)
   {
      if (entries[i].next >= -1)
      {
        ref int bucket = ref GetBucket(entries[i].hashCode);
        entries[i].next = bucket - 1;
        bucket = i + 1;
       }
    }
   _entries = entries;
}

由以上的源碼(不涉及數(shù)值類型的部分做了刪減)可以看出，HashHelpers.ExpandPrime(_count)計(jì)算新的Entry[]大小，那我們來(lái)具體看一下這個(gè)新的數(shù)組大小的計(jì)算邏輯是如何實(shí)現(xiàn)的。

public static int ExpandPrime(int oldSize)
{
   int newSize = 2 * oldSize;
   if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize) return MaxPrimeArrayLength;
   return GetPrime(newSize);
}

對(duì)于新的entries數(shù)組的擴(kuò)容，首先按照原始數(shù)組大小*2，那么對(duì)于能夠擴(kuò)容的最大數(shù)值為MaxPrimeArrayLength=0x7FFFFFC3，對(duì)應(yīng)32字節(jié)的最大值。計(jì)算新的數(shù)組大小時(shí)，會(huì)基于原始數(shù)組2倍的情況下，再取對(duì)應(yīng)的最少素?cái)?shù)相乘，即：realSize=2*oldSize*y(素?cái)?shù)表中的最少素?cái)?shù))。

【備注：其實(shí)在整個(gè)C#的擴(kuò)容邏輯中，絕大數(shù)大都是按照2倍進(jìn)行擴(kuò)容(按照2倍擴(kuò)容的方式存在一定的弊端，假設(shè)第n次擴(kuò)容分配了2^n的空間（省略常數(shù)C），那么之前釋放掉的空間總和為：1 + 2 + 2^2 + ... + 2^(n-1) = 2^n - 1 正好放不下2^n的空間。這樣導(dǎo)致的結(jié)果就是需要操作系統(tǒng)不斷分配新的內(nèi)存頁(yè)，并且數(shù)組的首地址也在不斷變大，造成緩存缺失?！?/p>

Array.Copy(_entries, entries, count)擴(kuò)容后的新數(shù)組會(huì)將對(duì)舊數(shù)組進(jìn)行Copy()操作，在C#中每次對(duì)數(shù)組進(jìn)行擴(kuò)容時(shí)，都是將就數(shù)組的元素全部拷貝到新的數(shù)組中，這個(gè)過(guò)程是比較耗時(shí)和浪費(fèi)資源，如果在實(shí)際的開(kāi)發(fā)過(guò)程中提前計(jì)算好數(shù)組的容量，可以極大限度的提升性能，降低GC的活動(dòng)頻率。

其中對(duì)于初始化為設(shè)置Dictionary的capacity時(shí)，第一次插入元素時(shí)，C#會(huì)對(duì)兩個(gè)數(shù)組進(jìn)行初始化，其中size=3，即維護(hù)的素?cái)?shù)表中的最小值，后續(xù)超過(guò)該數(shù)組大小后，會(huì)按照以上的擴(kuò)容邏輯進(jìn)行擴(kuò)容。

四、Dictionary<TKey, TValue>的FindValue的實(shí)現(xiàn)方式

介紹完畢Dictionary<TKey, TValue>的元素插入后，我們接下來(lái)看一下Dictionary<TKey, TValue>的查詢邏輯，在Dictionary<TKey, TValue>中實(shí)現(xiàn)查詢邏輯的核心方法是FindValue()，首先我們來(lái)看一下其實(shí)現(xiàn)的源碼。

internal ref TValue FindValue(TKey key)
{
  ref Entry entry = ref Unsafe.NullRef<Entry>();
  if (_buckets != null)
  {
    uint hashCode = (uint)key.GetHashCode();
    int i = GetBucket(hashCode);
    Entry[]? entries = _entries;
    uint collisionCount = 0;
    i--;
    do
      {
        if ((uint)i >= (uint)entries.Length)
        {
           goto ReturnNotFound;
        }
        entry = ref entries[i];
        if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key))
        {
           goto ReturnFound;
        }
        i = entry.next;
        collisionCount++;
      } while (collisionCount <= (uint)entries.Length);
         goto ConcurrentOperation;
    }
      goto ReturnNotFound;
       ConcurrentOperation:
            ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
        ReturnFound:
            ref TValue value = ref entry.value;
        Return:
            return ref value;
        ReturnNotFound:
            value = ref Unsafe.NullRef<TValue>();
            goto Return;
}

以上的源碼中，對(duì)于計(jì)算hashCode和計(jì)算哈希索引的桶的邏輯就不再贅述，重點(diǎn)關(guān)注entry.hashCode == hashCode &&EqualityComparer.Default.Equals(entry.key, key))，在FindValue()中，對(duì)已經(jīng)緩存的Entry[]? entries進(jìn)行循環(huán)遍歷，然后依次進(jìn)行比較，其中比較的邏輯包含兩部分。在判斷取值key時(shí)，不僅需要判斷傳入key值的hashCode與對(duì)應(yīng)Entry[]? entries中的元素的hashCode值相等，還需要判斷key是否相同，通過(guò)EqualityComparer.Default.Equals(entry.key, key)進(jìn)行比較，關(guān)于比較器的邏輯將在下一章中進(jìn)行介紹。

五、學(xué)在最后的思考和感悟

上面介紹了Dictionary<TKey, TValue>的初始化、元素插入、元素插入時(shí)的擴(kuò)容、元素取值的部分邏輯，我們可以發(fā)現(xiàn)在Dictionary<TKey, TValue>中維護(hù)了nt[] buckets和Entry[]? _entries兩個(gè)數(shù)組，其中用于存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)為Entry[]? _entries，這個(gè)類型為一個(gè)結(jié)構(gòu)體，在C#中結(jié)構(gòu)體占用的內(nèi)存要小于一個(gè)對(duì)象的內(nèi)存占用。無(wú)論多么復(fù)雜的存儲(chǔ)結(jié)構(gòu)，其內(nèi)部會(huì)盡量將其簡(jiǎn)化為一個(gè)數(shù)組，然后通過(guò)數(shù)組的存儲(chǔ)和讀取特性進(jìn)行優(yōu)化，規(guī)避了數(shù)組在某方面的不足，發(fā)揮了其優(yōu)勢(shì)。

以上的部分思考中，我們其實(shí)可以發(fā)現(xiàn)在實(shí)際的編碼過(guò)程中，需要注意的幾個(gè)事項(xiàng)：

(1)、創(chuàng)建存儲(chǔ)結(jié)構(gòu)時(shí)，需要思考其對(duì)應(yīng)的存儲(chǔ)場(chǎng)景和對(duì)象，盡量選擇合適的結(jié)構(gòu)進(jìn)行處理，降低內(nèi)存的占用情況。

(2)、對(duì)于存儲(chǔ)結(jié)構(gòu)，盡量可以提前指定容量，避免頻繁的擴(kuò)容，每次擴(kuò)容都會(huì)伴隨數(shù)組的復(fù)制。

(3)、C#的擴(kuò)容機(jī)制都是按照擴(kuò)容2倍，在hash存儲(chǔ)結(jié)構(gòu)中，還會(huì)按照維護(hù)的素?cái)?shù)表進(jìn)行個(gè)性化的計(jì)算優(yōu)化。

(4)、解讀源碼時(shí)，可以先選擇一個(gè)簡(jiǎn)單的場(chǎng)景，盡量剔除與需要驗(yàn)證場(chǎng)景無(wú)關(guān)的代碼，集中核心邏輯進(jìn)行分析，然后再逐步進(jìn)行擴(kuò)展思考。

到此這篇關(guān)于詳解C#中Dictionary<TKey,TValue>的存儲(chǔ)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)C# Dictionary<TKey,TValue>內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論