首页 > 编程语言 >CoreFX中Dictionary<TKey, TValue>的源码解读

CoreFX中Dictionary<TKey, TValue>的源码解读

时间:2023-11-14 12:33:18浏览次数:32  
标签:key CoreFX Dictionary int hashCode 源码 哈希 entries

  无论是实际的项目中,还是在我们学习的过程中,都会重点的应用到Dictionary<TKey, TValue>这个存储类型。每次对Dictionary<TKey, TValue>的添加都包含一个值和与其关联的键, 使用键检索值的速度非常快,接近 O (1) ,因为 Dictionary<TKey, TValue> 类是作为哈希表实现的。首先我们来从一个简单的例子开始,以下是对一个字典的创建和赋值。

1 Dictionary<int, string> openWith = new Dictionary<int, string>();
2 openWith.Add(1000, "key值为1000");
3 openWith.Add(1001, "key值为1001");
  相信绝大部分的开发人员对以上示例不是会陌生,那么Dictionary<TKey, TValue>的实现原理是什么样的呢?在字典的初始化、赋值、取值、扩容的实现原理是什么样的呢?很多时候我们需要知其然,更需要知其所以然。接下来我们将从其内存的存储的数据结构、取值的逻辑、扩容原则等几个视角进行仔细的了解 。那我们就沿着CoreFX中Dictionary<TKey, TValue>的实现源码来做一个简单的学习和思考,这里需要特别注意一下:   学习和分析源码时,不要先入为主,要按照框架和源码的逻辑进行解读,记录下不懂的地方重点分析,最后将整个逻辑串联起来。如果我们一开始就设定了逻辑为A-B-C,但是读到一个阶段的时候发现变成了C-B-A,这个时候就无法再继续进行下去,因为具体的实现过程中会有很多因素造成局部调整,我们可以在解读完毕之后,将实际的逻辑与个人前期理解的逻辑的差异进行比较,找出原因并做分析。 一、Dictionary<TKey, TValue>初始化   Dictionary<TKey, TValue>的构造方法较多,我们来看一下其中的基础实现方法,首先看一下对应的源码(源码中不必要的部分已经做了部分删减,保留了核心的实现逻辑)。
 1  public Dictionary(int capacity, IEqualityComparer<TKey>? comparer)
 2 {
 3     if (capacity > 0) Initialize(capacity);
 4     if (!typeof(TKey).IsValueType)
 5     {
 6        _comparer = comparer ?? EqualityComparer<TKey>.Default;
 7        if (typeof(TKey) == typeof(string) && NonRandomizedStringEqualityComparer.GetStringComparer(_comparer!) is IEqualityComparer<string> stringComparer)
 9        {
10          _comparer = (IEqualityComparer<TKey>)stringComparer;
11         }
12      }
13      else if (comparer is not null && comparer != EqualityComparer<TKey>.Default)
14      {
15         _comparer = comparer;
16      }
17 }
  以上的实现逻辑重点包含了两个部分,第一部分:对Dictionary<TKey, TValue>的容量初始化;第二部分是Dictionary<TKey, TValue>的IEqualityComparer? comparer的初始化,本文重点是对Dictionary<TKey, TValue>的存储结构进行分析,涉及到比较器的实现逻辑,将放在后续的章节中进行重点介绍。   我们接下来看一下Initialize()的实现逻辑进行一个简单的介绍,首先一起来看一下对应的源码实现(非必要部分已做删减,方便大家可以直观的查看)。
 1 private int Initialize(int capacity)
 2 {
 3   int size = HashHelpers.GetPrime(capacity);
 4   int[] buckets = new int[size];
 5   Entry[] entries = new Entry[size];
 6   _freeList = -1;
 7 #if TARGET_64BIT
 8   _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)size);
 9 #endif
10   _buckets = buckets;
11   _entries = entries;
12   return size;
13 } 
  从上面的源码可以看出,根据传入的capacity参数来设定字典对应的相关容量大小,其中包含两部分,第一部分: 根据设定的容量(capacity)大小,计算对应的buckets和entries大小,关于为什么使用buckets和entries两个数组结构,我们将在下一节重点介绍;第二部分:判断当前机器的位数,计算对应的_fastModMultiplier。我们看一下HashHelpers.GetPrime(capacity)的计算逻辑。(该类在System.Collections命名空间下,其对应的类型定义为:internal static partial class HashHelpers)
 1 public static int GetPrime(int min)
 2 {
 3   foreach (int prime in Primes)
 4   {
 5     if (prime >= min) return prime;
 6     for (int i = (min | 1); i < int.MaxValue; i += 2)
 7     {
 8         if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i;
 9      }
10      return min;
11    }
12 }
  HashHelpers用于计算和维护哈希表容量的素数值,为什么哈希表需要使用素数?主要是为了减少哈希冲突(hash collisions)的发生,素数的选择能够减少共同的因子,减小哈希冲突的可能性。此外,选择素数还能够确保在哈希表的容量变化时,不容易出现过多的重复。如果容量选择为一个合数(非素数),那么在容量变化时,可能会导致新容量与旧容量有相同的因子,增加哈希冲突的风险。   接下来我们沿着GetPrime()的调用关系来看整个哈希表容量的计算逻辑,HashHelpers设定了一个Primes[]的只读素数数组,具体的元素如下,至于什么使用这样的素数的数组,主要是这些素数在实践中已经被证明是有效的,适用于许多常见的使用场景,更多的是有助于在哈希表等数据结构中提供更好的性能。
1 internal static ReadOnlySpan<int> Primes => new int[]
2 {
3   3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
4   1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
5   17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
6   187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
7   1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
8 };
  GetPrime()会首先循环Primes[],依次判断设定的min大小与素数表元素的关系,若素数表中的元素大于min,则直接去对应的素数,无需后续的计算,如果设置的min不在预定的素数表中,则进行素数的计算。关于素数的计算逻辑,借助本文开头的Dictionary<TKey, TValue>的定义和赋值进行说明,首先对min和1进行按位或运算,初始化过程中未对capacity赋值时,则(min | 1)为1,对进行位运算后的i值校验是否符合素数定义,再进行((i - 1) % HashPrime != 0)运算,其中HashPrime = 101,用于在哈希算法中作为质数因子(101是一个相对小的质数,可以减少哈希碰撞的可能性,并且在计算哈希时更加高效),对于初始化未设置容量的Dictionary<TKey, TValue>,计算获取得到的容量为int size=3。(即3*4*8=72(bit))   (注意:对于已设定了capacity的Dictionary,按照以上的逻辑进行计算对应的size值。这里就不再做过多介绍)   计算获取到size值后,设置空闲列表为-1(_freeList = -1)。根据编译时的运行机器的位数进行分类处理,若机器为非64位,则对buckets和entries两个数组进行初始化。若机器为64位是,则需要进行重新计算,获取_fastModMultiplier,其计算逻辑如下:
public static ulong GetFastModMultiplier(uint divisor) => ulong.MaxValue / divisor + 1;
  以上的计算结果返回除数的近似倒数,计算用于快速取模运算的乘法因子。   通过以上的计算过程,我们可以对Dictionary<TKey, TValue>的容量计算有一个简单的认识,接下来我们来具体看一下用于存储数据和哈希索引的两个数组。 二、Dictionary<TKey, TValue>的存储基础结构   对于Dictionary<TKey, TValue>的两个重要数组buckets和entries,我们来具体的分析一下。首先来看一下Entry[]?_entries的实际的数据结构:
1 private struct Entry
2 {
3   public uint hashCode;
4   public int next;
5   public TKey key;
6   public TValue value;
7 }
  在Dictionary<TKey, TValue>中实际存储数据的结构是Entry[],其中数组的每个元素是一个Entry,该类型为一个结构体,用于在哈希表内部存储每个键值对的信息,其中定义的key和value则是我们在设置字典时添加的键值对,那么对于另外两个属性需要重点分析一下。   hashCode为在添加key时,将key进行计算获取得到的哈希值,哈希值的计算过程中,需要对key进行按类别进行计算,C#中对数值类型、字符串、结构体、对象的哈希值计算逻辑都不相同,其中对于"数值类型"的哈希值计算逻辑为"数字类型的哈希码生成逻辑通常是将数字类型的值转换为整数,然后将该整数作为哈希码。"对于字符串的哈希值计算逻辑为"默认的字符串哈希码计算方式采用了所谓的“Jenkins One-at-a-Time Hash”算法的变体。"对于结构体和对象的哈希值计算逻辑就不做具体介绍。   next通常用于处理哈希冲突,即多个键具有相同的哈希码的情况。next是一个索引,指向哈希表中下一个具有相同哈希码的元素。其中next=-1时,表示链表结束;next=-2 表示空闲列表的末尾,next=-3 表示在空闲列表上的索引 0,next=-4 表示在空闲列表上的索引 1,后续则依次类推。   Entry通过使用结构体而不是类,可以减少内存开销,因为结构体是值类型,而类是引用类型。结构体在栈上分配,而类在堆上分配。   以上介绍了Entry的结构和对应的属性字段,接下来我们再来看一下int[] buckets的结构和计算逻辑,buckets是一个简单的int类型的数组,这样的数组通常用于存储哈希桶的信息。每个桶实际上是一个索引,指向一个链表或链表的头部,用于解决哈希冲突。
1  private ref int GetBucket(uint hashCode)
2 {
3    int[] buckets = _buckets!;
4  #if TARGET_64BIT
5    return ref buckets[HashHelpers.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)];
6  #else
7    return ref buckets[(uint)hashCode % buckets.Length];
8  #endif
9  }   
  GetBucket()用于在哈希表中获取桶索引,其中参数hashCode为key对应的哈希码,在64位目标体系结构下,使用 HashHelpers.FastMod 方法进行快速模运算,而在32位目标体系结构下,使用普通的取模运算。那么为什么在Dictionary<TKey, TValue>中维护一个用来存储哈希表的桶呢?主要有以下4个目的:     (1)、解决哈希冲突:两个或多个不同的键经过哈希函数得到相同的哈希码,导致它们应该存储在哈希表的相同位置。通过使用桶,可以在同一个位置存储多个元素,解决了哈希冲突的问题。     (2)、提供快速查找:通过哈希函数计算键的哈希码,然后将元素存储在哈希表的桶中,可以在常数时间内(平均情况下)定位到存储该元素的位置,实现快速的查找。     (3)、支持高效的插入和删除:当插入元素时,通过哈希函数确定元素应该存储的桶,然后将其添加到桶的链表或其他数据结构中。当删除元素时,同样可以快速定位到存储元素的桶,并删除该元素。     (4)、平衡负载:哈希表的性能与负载因子相关,而负载因子是元素数量与桶数量的比值。使用适当数量的桶可以帮助平衡负载,防止哈希表变得过度拥挤,从而保持其性能。在不同的哈希表实现可能使用不同的数据结构,如链表、树等,C#的Dictionary中使用一个int[]维护这个哈希表的桶索引。 三、Dictionary<TKey, TValue>的TryAdd的实现方式   以上主要介绍了Dictionary<TKey, TValue>的初始化、数据对应的存储和哈希表桶索引的存储结构,现在我们具体看一下Dictionary<TKey, TValue>的添加元素的实现方式,下面对C#的实现代码进行了精简,删除当前并不关注的部分。   本文实例中对key赋值的为整数类型,部分对于非数值类型、调试代码等进行删减。(由于对于对象或者设置了比较器逻辑相对繁琐,将在下文中进行介绍)
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;
}
  以上的源码中的实现逻辑中核心包含3个部分,分别是计算hashCode、计算哈希表桶索引的bucket、Dictionary扩容,上一节中已经介绍了前两个实现逻辑,本节重点介绍Dictionary<TKey, TValue>的扩容逻辑,我们来看一下Resize()的实现逻辑。
 1 private void Resize() => Resize(HashHelpers.ExpandPrime(_count), false);
 2 
 3 private void Resize(int newSize, bool forceNewHashCodes)
 4 {
 5    Entry[] entries = new Entry[newSize];
 6    int count = _count;
 7    Array.Copy(_entries, entries, count);
 8    _buckets = new int[newSize];
 9 #if TARGET_64BIT
10    _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
11 #endif
12    for (int i = 0; i < count; i++)
13    {
14       if (entries[i].next >= -1)
15       {
16         ref int bucket = ref GetBucket(entries[i].hashCode);
17         entries[i].next = bucket - 1;
18         bucket = i + 1;
19        }
20     }
21    _entries = entries;
22 }    
  由以上的源码(不涉及数值类型的部分做了删减)可以看出,HashHelpers.ExpandPrime(_count)计算新的Entry[]大小,那我们来具体看一下这个新的数组大小的计算逻辑是如何实现的。
1 public static int ExpandPrime(int oldSize)
2 {
3    int newSize = 2 * oldSize;
4    if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize) return MaxPrimeArrayLength;
5    return GetPrime(newSize);
6 } 
  对于新的entries数组的扩容,首先按照原始数组大小*2,那么对于能够扩容的最大数值为MaxPrimeArrayLength=0x7FFFFFC3,对应32字节的最大值。计算新的数组大小时,会基于原始数组2倍的情况下,再取对应的最少素数相乘,即:realSize=2*oldSize*y(素数表中的最少素数)。   【备注:其实在整个C#的扩容逻辑中,绝大数大都是按照2倍进行扩容(按照2倍扩容的方式存在一定的弊端,假设第n次扩容分配了2^n的空间(省略常数C),那么之前释放掉的空间总和为:1 + 2 + 2^2 + ... + 2^(n-1) = 2^n - 1 正好放不下2^n的空间。这样导致的结果就是需要操作系统不断分配新的内存页,并且数组的首地址也在不断变大,造成缓存缺失。】   Array.Copy(_entries, entries, count)扩容后的新数组会将对旧数组进行Copy()操作,在C#中每次对数组进行扩容时,都是将就数组的元素全部拷贝到新的数组中,这个过程是比较耗时和浪费资源,如果在实际的开发过程中提前计算好数组的容量,可以极大限度的提升性能,降低GC的活动频率。   其中对于初始化为设置Dictionary的capacity时,第一次插入元素时,C#会对两个数组进行初始化,其中size=3,即维护的素数表中的最小值,后续超过该数组大小后,会按照以上的扩容逻辑进行扩容。 四、Dictionary<TKey, TValue>的FindValue的实现方式   介绍完毕Dictionary<TKey, TValue>的元素插入后,我们接下来看一下Dictionary<TKey, TValue>的查询逻辑,在Dictionary<TKey, TValue>中实现查询逻辑的核心方法是FindValue(),首先我们来看一下其实现的源码。
 1 internal ref TValue FindValue(TKey key)
 2 {
 3   ref Entry entry = ref Unsafe.NullRef<Entry>();
 4   if (_buckets != null)
 5   {
 6     uint hashCode = (uint)key.GetHashCode();
 7     int i = GetBucket(hashCode);
 8     Entry[]? entries = _entries;
 9     uint collisionCount = 0;
10     i--; 
11     do
12       {
13         if ((uint)i >= (uint)entries.Length)
14         {
15            goto ReturnNotFound;
16         }
17         entry = ref entries[i];
18         if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key))
19         {
20            goto ReturnFound;
21         }
22         i = entry.next;
23         collisionCount++;
24       } while (collisionCount <= (uint)entries.Length);
25          goto ConcurrentOperation;
26     }
27       goto ReturnNotFound;
28        ConcurrentOperation:
29             ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
30         ReturnFound:
31             ref TValue value = ref entry.value;
32         Return:
33             return ref value;
34         ReturnNotFound:
35             value = ref Unsafe.NullRef<TValue>();
36             goto Return;
37 }
  以上的源码中,对于计算hashCode和计算哈希索引的桶的逻辑就不再赘述,重点关注entry.hashCode == hashCode &&EqualityComparer.Default.Equals(entry.key, key)),在FindValue()中,对已经缓存的Entry[]? entries进行循环遍历,然后依次进行比较,其中比较的逻辑包含两部分。在判断取值key时,不仅需要判断传入key值的hashCode与对应Entry[]? entries中的元素的hashCode值相等,还需要判断key是否相同,通过EqualityComparer.Default.Equals(entry.key, key)进行比较,关于比较器的逻辑将在下一章中进行介绍。 五、学在最后的思考和感悟   上面介绍了Dictionary<TKey, TValue>的初始化、元素插入、元素插入时的扩容、元素取值的部分逻辑,我们可以发现在Dictionary<TKey, TValue>中维护了nt[] buckets和Entry[]? _entries两个数组,其中用于存储数据的结构为Entry[]? _entries,这个类型为一个结构体,在C#中结构体占用的内存要小于一个对象的内存占用。无论多么复杂的存储结构,其内部会尽量将其简化为一个数组,然后通过数组的存储和读取特性进行优化,规避了数组在某方面的不足,发挥了其优势。   以上的部分思考中,我们其实可以发现在实际的编码过程中,需要注意的几个事项:     (1)、创建存储结构时,需要思考其对应的存储场景和对象,尽量选择合适的结构进行处理,降低内存的占用情况。     (2)、对于存储结构,尽量可以提前指定容量,避免频繁的扩容,每次扩容都会伴随数组的复制。     (3)、C#的扩容机制都是按照扩容2倍,在hash存储结构中,还会按照维护的素数表进行个性化的计算优化。     (4)、解读源码时,可以先选择一个简单的场景,尽量剔除与需要验证场景无关的代码,集中核心逻辑进行分析,然后再逐步进行扩展思考。   以上内容是对CoreFx中Dictionary<TKey, TValue>的存储和读取逻辑的简单介绍,如错漏的地方,还望指正。

标签:key,CoreFX,Dictionary,int,hashCode,源码,哈希,entries
From: https://www.cnblogs.com/pengze0902/p/17830689.html

相关文章

  • NS-3源码学习(一)
    NS-3源码学习(一)NS-3项目的源码包装的非常严密,对于仿真来说仅需要使用helper函数即可完成环境的配置。但是这种封装简直是解析ns-3数据传输的过程的一座大山。想要用传统的单步调试的方案去观察数据的流向更是寄,各种回调函数满天飞。没办法,只能从源码入手,一点点褪下这层helper函数......
  • Linux 源码包安装
    SRPM包,比RPM包多了一个“S”,是“Source”的首字母,所以SRPM可直译为“源代码形式的RPM包”。也就是说,SRPM包中不再是经过编译的二进制文件,都是源代码文件。可以这样理解,SRPM包是软件以源码形式发布后直接封装成RPM包的产物。从表中可以看到,SRPM包的命名与RPM包基本类......
  • 医院等级评审,离不开不良事件上报系统【医院不良事件报告源码】
    不良事件上报系统对事件的报告、处置、跟踪、评价、分析、改进、学习等进行了综合管理,通过双向互评机制实现临床科室与职能部门之间的进一步互动,加强不良事件报告处置过程中的信息互通能力。围绕患者安全、医疗、护理、药品、器械耗材、输血、感染、后勤、治安、患者满意度、职业暴......
  • 怎样阅读 h2 数据库源码
    阅读h2数据库的源码是一项复杂的任务,需要对数据库原理、Java语言和操作系统有深入的理解。可以从以下几方面入手来完成。环境准备首先,你需要在你的机器上安装和配置好开发环境,包括JDK、Maven、IDE调试器等工具。然后,从h2的官方网站或GitHub上下载源码。IDE导入h2数据......
  • 傣族节日及民间故事推广小程序-计算机毕业设计源码+LW文档
    摘  要互联网的兴起从本质上改变了整个社会对信息的管理方式,国内各大市场从上个世纪90年代互联网兴起之时,就产生了通过网络进行系统管理的想法。但是由于在互联网上的信誉难以认证、网络的法规政策不健全等一系列的原因,限制了网上信息管理发展的步伐。进入21世纪以后,随着整个......
  • 直播app系统源码,底部弹框显示,底部导航隐藏
    直播app系统源码,底部弹框显示,底部导航隐藏在uni-app中,如果你在tabbar页面显示一个底部弹框,底部导航默认是会依旧显示的。如果你想在弹框显示时隐藏底部导航,你可以使用uni.hideTabBar和uni.showTabBar方法来控制底部导航的显示和隐藏。 exportdefault{ methods:{  ope......
  • 成品直播源码推荐,uni底部导航栏隐藏单个
    成品直播源码推荐,uni底部导航栏隐藏单个uni.showTabBar()uni.setTabBarItem({index:0,visible:false})uni.setTabBarItem({index:2,visible:false})​以上就是成品直播源码推荐,uni底部导航栏隐藏单个,更多内容欢迎关注之后的文章 ......
  • 在线直播源码,修改默认的箭头的两种方式
    在线直播源码,修改默认的箭头的两种方式方式一:在配置文件中有个android:groupIndicator属性,将其设置为:你的selector,例如:android:groupIndicator="@drawable/arrow_expandable_list" <?xmlversion="1.0"encoding="utf-8"?><selectorxmlns:android="http://schem......
  • 热门游戏网游推荐网站的设计与开发-计算机毕业设计源码+LW文档
    摘要热门网游推荐网站是一个利用JAVA技术建设的网上管理系统,在热门网游推荐管理中实现信息化。系统的设计就是为了迎合广大用户需求而创建的一个界面简洁、有定向内容、业务逻辑简单易操作的热门网游推荐网站。本文以热门网游推荐为例,提出了利用JAVA技术设计和实现热门网游推荐......
  • 医院不良事件管理系统源码,不同事件和等级实现智能预警提示
    医院不良事件管理系统源码 不良事件管理系统源码医院不良事件管理系统,支持医疗管理、护理管理、药品管理、医技管理、器械管理、输血管理、院感管理、职业防护管理、信息管理、后勤管理、治安管理等事件,内容齐全,预设项详尽,医院可根据自身实际情况进行事件类型扩展,满足全院级不良事......