当前位置： 首页 > article >正文

C# Dictionary实现原理

article 2024/11/26 11:17:34

目录

一、概念整理

1，Hash 算法

2、Hash 桶算法

3、解决冲突算法

二、源码分析

1，数据存储的最小单元(Entry)的数据结构

2，字典初始化

3，添加新元素

4，字典的扩容

5，移除元素

三、答疑时间

1，字典为什么能无限地Add呢

2，为什么从字典中取数据这么快

3，初始化字典可以指定字典容量,这是否多余呢

4，为什么字典的桶buckets 长度为素数

一、概念整理

1，Hash 算法

Hash 算法是一种数字摘要算法，它能将不定长度的二进制数据集给映射到一个较短的二进制长度数据集，常见的 MD5 算法就是一种 Hash 算法，通过 MD5 算法可对任何数据生成数字摘要。而实现了 Hash 算法的函数我们叫她Hash 函数。Hash 函数有以下几点特征。

  1. 相同的数据进行 Hash 运算，得到的结果一定相同。HashFunc(key1) == HashFunc(key1)
  2. 不同的数据进行 Hash 运算，其结果也可能会相同，(Hash 会产生碰撞)。key1 != key2 => HashFunc(key1) == HashFunc(key2).
  3. Hash 运算时不可逆的，不能由 key 获取原始的数据。key1 => hashCode但是hashCode =\=> key1。

常见的构造 Hash 函数的算法有以下几种：

1. 直接寻址法：取 keyword 或 keyword 的某个线性函数值为散列地址。即 H(key)=key 或 H(key) = a•key + b，当中 a 和 b 为常数（这样的散列函数叫做自身函数）

2. 数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3. 平方取中法：取 keyword 平方后的中间几位作为散列地址。

4. 折叠法：将 keyword 切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。

5. 随机数法：选择一随机函数，取 keyword 的随机值作为散列地址，通经常使用于 keyword 长度不同的场合。

6. 除留余数法：取 keyword 被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅能够对 keyword 直接取模，也可在折叠、平方取中等运算之后取模。对 p 的选择非常重要，一般取素数或 m，若 p 选的不好，容易产生碰撞.

哈希函数

哈希函数又称散列函数,是一种从任何一种数据中创建小的数字“指纹”的方法。

public int hashCode() {
        int h = hash;
 //hash default value : 0 
        if (h == 0 && value.length > 0) {
 //value : char storage
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

可以看到,无论多长的字符串,最终都会返回一个int值,当哈希函数确定的情况下,任何一个字符串的哈希值都是唯一且确定的.

当然,这里只是找了一种最简单的字符数哈希值求法,理论上只要能把一个对象转换成唯一且确定值的函数,我们都可以把它称之为哈希函数.

这是哈希函数的示意图.

所以,一个对象的哈希值是确定且唯一的!.

2、Hash 桶算法

说到 Hash 算法大家就会想到Hash 表，一个 Key 通过 Hash 函数运算后可快速的得到 hashCode，通过 hashCode 的映射可直接 Get 到 Value，但是 hashCode 一般取值都是非常大的，经常是 2^32 以上，不可能对每个 hashCode 都指定一个映射。

因为这样的一个问题，所以人们就将生成的 HashCode 以分段的形式来映射，把每一段称之为一个Bucket（桶），一般常见的 Hash 桶就是直接对结果取余。

假设将生成的 hashCode 可能取值有 2^32 个，然后将其切分成一段一段，使用8个桶来映射，那么就可以通过bucketIndex = HashFunc(key1) % 8这样一个算法来确定这个 hashCode 映射到具体的哪个桶中。

大家可以看出来，通过 hash 桶这种形式来进行映射，所以会加剧 hash 的冲突。

3、解决冲突算法

对于一个 hash 算法，不可避免的会产生冲突，那么产生冲突以后如何处理，是一个很关键的地方，目前常见的冲突解决算法有拉链法(Dictionary 实现采用的)、开放定址法、再 Hash 法、公共溢出分区法，本文只介绍拉链法与再 Hash 法，对于其它算法感兴趣的同学可参考文章最后的参考文献。

1. 拉链法：**这种方法的思路是将产生冲突的元素建立一个单链表，并将头指针地址存储至 Hash 表对应桶的位置。这样定位到 Hash 表桶的位置后可通过遍历单链表的形式来查找元素。

2. 再 Hash 法：顾名思义就是将 key 使用其它的 Hash 函数再次 Hash，直到找到不冲突的位置为止。


二、源码分析

1，数据存储的最小单元(Entry)的数据结构

private struct Entry {
    public int hashCode;    // 除符号位以外的31位hashCode值, 如果该Entry没有被使用，那么为-1
    public int next;        // 下一个元素的下标索引，如果没有下一个就为-1
    public TKey key;        // 存放元素的键
    public TValue value;    // 存放元素的值
}

一个Entry包括该key的HashCode,以及下个Entry的索引Next,该键值对的Key以及数据Vaule。

2，字典初始化

private int[] buckets;  // Hash桶
private Entry[] entries; // Entry数组，存放元素
private int count;   // 当前entries的index位置
private int version;  // 当前版本，防止迭代过程中集合被更改
private int freeList;  // 被删除Entry在entries中的下标index，这个位置是空闲的
private int freeCount;  // 有多少个被删除的Entry，有多少个空闲的位置
private IEqualityComparer<TKey> comparer; // 比较器
private KeyCollection keys;  // 存放Key的集合
private ValueCollection values;  // 存放Value的集合
        private void Initialize(int capacity)
        {
            int size = HashHelpersMini.GetPrime(capacity);
            _buckets = new int[size];
            for (int i = 0; i < _buckets.Length; i++)
            {
                _buckets[i] = -1;
            }

            _entries = new Entry[size];

            _freeList = -1;
        }

字典初始化时,首先要创建int数组,分别为buckets和entries,其中buckets的index是key的哈希值%size,它的value是数据在entries中的index,我们要取的数据就存在entries中.当某一个bucket没有指向任何entry时,它的value为-1.

另外,很有意思得一点,buckets的数组长度是多少呢?这个我研究了挺久,发现取的是大于capacity的最小质数。

3，添加新元素

  private void Insert(TKey key, TValue value, bool add)
        {
            if (key == null)
            {
                throw new ArgumentNullException();
            }
            //如果buckets为空,则重新初始化字典.
            if (_buckets == null) Initialize(0);
            //获取传入key的 哈希值
            var hashCode = _comparer.GetHashCode(key);
            //把hashCode%size的值作为目标Bucket的Index.
            var targetBucket = hashCode % _buckets.Length;
            //遍历判断传入的key对应的值是否已经添加字典中
            for (int i = _buckets[targetBucket]; i > 0; i = _entries[i].Next)
            {
                if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
                {
                    //当add为true时,直接抛出异常,告诉给定的值已存在在字典中.
                    if (add)
                    {
                        throw new Exception("给定的关键字已存在!");
                    }
                    //当add为false时,重新赋值并退出.
                    _entries[i].Value = value;
                    return;
                }
            }
            //表示本次存储数据的数据在Entries中的索引
            int index;
            //当有数据被Remove时,freeCount会加1
            if (_freeCount > 0)
            {
                //freeList为上一个移除数据的Entries的索引,这样能尽量地让连续的Entries都利用起来.
                index = _freeList;
                _freeList = _entries[index].Next;
                _freeCount--;
            }
            else
            {
                //当已使用的Entry的数据等于Entries的长度时,说明字典里的数据已经存满了,需要对字典进行扩容,Resize.
                if (_count == _entries.Length)
                {
                    Resize();
                    targetBucket = hashCode % _buckets.Length;
                }
                //默认取未使用的第一个
                index = _count;
                _count++;
            }
            //对Entries进行赋值
            _entries[index].HashCode = hashCode;
            _entries[index].Next = _buckets[targetBucket];
            _entries[index].Key = key;
            _entries[index].Value = value;
            //用buckets来登记数据在Entries中的索引.
            _buckets[targetBucket] = index;
        }

4，字典的扩容

private void Resize()
        {
            //获取大于当前size的最小质数
            Resize(HashHelpersMini.GetPrime(_count), false);
        }
 private void Resize(int newSize, bool foreNewHashCodes)
        {
            var newBuckets = new int[newSize];
            //把所有buckets设置-1
            for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
            var newEntries = new Entry[newSize];
            //把旧的的Enties中的数据拷贝到新的Entires数组中.
            Array.Copy(_entries, 0, newEntries, 0, _count);
            if (foreNewHashCodes)
            {
                for (int i = 0; i < _count; i++)
                {
                    if (newEntries[i].HashCode != -1)
                    {
                        newEntries[i].HashCode = _comparer.GetHashCode(newEntries[i].Key);
                    }
                }
            }
            //重新对新的bucket赋值.
            for (int i = 0; i < _count; i++)
            {
                if (newEntries[i].HashCode > 0)
                {
                    int bucket = newEntries[i].HashCode % newSize;
                    newEntries[i].Next = newBuckets[bucket];
                    newBuckets[bucket] = i;
                }
            }

            _buckets = newBuckets;
            _entries = newEntries;
        }

5，移除元素

        //通过key移除指定的item
        public bool Remove(TKey key)
        {
            if (key == null)
                throw new Exception();

            if (_buckets != null)
            {
                //获取该key的HashCode
                int hashCode = _comparer.GetHashCode(key);
                //获取bucket的索引
                int bucket = hashCode % _buckets.Length;
                int last = -1;
                for (int i = _buckets[bucket]; i >= 0; last = i, i = _entries[i].Next)
                {
                    if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
                    {
                        if (last < 0)
                        {
                            _buckets[bucket] = _entries[i].Next;
                        }
                        else
                        {
                            _entries[last].Next = _entries[i].Next;
                        }
                        //把要移除的元素置空.
                        _entries[i].HashCode = -1;
                        _entries[i].Next = _freeList;
                        _entries[i].Key = default(TKey);
                        _entries[i].Value = default(TValue);
                        //把该释放的索引记录在freeList中
                        _freeList = i;
                        //把空Entry的数量加1
                        _freeCount++;
                        return true;
                    }
                }
            }

            return false;
        }

三、答疑时间

1，字典为什么能无限地Add呢

向Dictionary中添加元素时,会有一步进行判断字典是否满了,如果满了,会用Resize对字典进行自动地扩容,所以字典不会向数组那样有固定的容量。

2，为什么从字典中取数据这么快

Key-->HashCode-->HashCode%Size-->Bucket Index-->Bucket-->Entry Index-->Value

整个过程都没有通过遍历来查找数据,一步到下一步的目的性时非常明确的,所以取数据的过程非常快。

3，初始化字典可以指定字典容量,这是否多余呢

前面说过,当向字典中插入数据时,如果字典已满,会自动地给字典Resize扩容.

扩容的标准时会把大于当前前容量的最小质数作为当前字典的容量,比如,当我们的字典最终存储的元素为15个时,会有这样的一个过程。

new Dictionary()------------------->size:3

字典添加低3个元素---->Resize--->size:7

字典添加低7个元素---->Resize--->size:11

字典添加低11个元素--->Resize--->size:23

可以看到一共进行了三次次Resize,如果我们预先知道最终字典要存储15个元素,那么我们可以用new Dictionary(15)来创建一个字典.

new Dictionary(15)---------->size:23

这样就不需要进行Resize了,可以想象,每次Resize都是消耗一定的时间资源的,需要把OldEnties Copy to NewEntries 所以我们在创建字典时,如果知道字典的中要存储的字典的元素个数,在创建字典时,就传入capacity,免去了中间的Resize进行扩容.

Tips:

即使指定字典容量capacity,后期如果添加的元素超过这个数量,字典也是会自动扩容的。

4，为什么字典的桶buckets 长度为素数

我们假设有这样的一系列keys,他们的分布范围时K={ 0, 1,..., 100 },又假设某一个buckets的长度m=12,因为3是12的一个因子,当key时3的倍数时,那么targetBucket也将会是3的倍数.

        Keys {0,12,24,36,...}
        TargetBucket将会是0.
        Keys {3,15,27,39,...}
        TargetBucket将会是3.
        Keys {6,18,30,42,...}
        TargetBucket将会是6.
        Keys {9,21,33,45,...}
        TargetBucket将会是9.

如果Key的值是均匀分布的(K中的每一个Key中出现的可能性相同),那么Buckets的Length就没有那么重要了,但是如果Key不是均匀分布呢?

想象一下,如果Key在3的倍数时出现的可能性特别大,其他的基本不出现,TargetBucket那些不是3的倍数的索引就基本不会存储什么数据了,这样就可能有2/3的Bucket空着,数据大量第聚集在0,3,6,9中。

这种情况其实时很常见的。 例如，又一种场景，您根据对象存储在内存中的位置来跟踪对象,如果你的计算机的字节大小是4，而且你的Buckets的长度也为4,那么所有的内存地址都会时4的倍数,也就是说key都是4的倍数,它的HashCode也将会时4的倍数,导致所有的数据都会存储在TargetBucket=0(Key%4=0)的bucket中,而剩下的3/4的Buckets都是空的. 这样数据分布就非常不均匀了。

K中的每一个key如果与Buckets的长度m有公因子,那么该数据就会存储在这个公因子的倍数为索引的bucket中.为了让数据尽可能地均匀地分布在Buckets中,我们要尽量减少m和K中的key的有公因子出现的可能性.那么,把Bucket的长度设为质数就是最佳选择了,因为质数的因子时最少的.这就是为什么每次利用Resize给字典扩容时会取大于当前size的最小质数的原因。

 源码链接：

C# Dictionaryicon-default.png?t=O83Ahttps://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs

参考：

浅析C# Dictionary实现原理-腾讯云开发者社区-腾讯云

你真的了解字典吗(dictionary)?-腾讯云开发者社区-腾讯云


http://www.kler.cn/a/409861.html

相关文章：

  • 10大排序总结
  • HTML飞舞的爱心
  • 网络原理（一）：应用层自定义协议的信息组织格式 初始 HTTP
  • 【linux学习指南】初识Linux进程信号与使用
  • Ray 和 PyTorch
  • 软件工程第14章小测
  • 面向对象高级（9）包装
  • 什么是Portage-学习笔记
  • 学习threejs，使用设置normalMap法向量贴图创建更加细致的凹凸和褶皱
  • Python Selenium介绍（一）
  • 深入解析Java面向对象编程：Object类、泛型、序列化与网络编程
  • 如何通过cPanel创建品牌电子邮件
  • H5流媒体播放器EasyPlayer.js网页直播/点播播放器如果H.265视频在播放器上播放不流畅，可以考虑的解决方案
  • JavaWeb——Ajax、Element、打包部署
  • 鱼眼相机模型-MEI
  • 24/11/25 视觉笔记 深度传感器和手势识别
  • Spring Boot英语知识网站：性能优化
  • 【Linux学习】【Ubuntu入门】2-3 make工具和makefile引入
  • MySQL基础知识大总结
  • Vue2 常见知识点（一）
  • RGB图片 、RGBA、 灰度图、二值图
  • 拳皇98笔记
  • 【人工智能】Python常用库-Pandas常用方法教程
  • Mybatis PLUS查询对List使用OR模糊查询
  • 读《Effective Java》笔记 - 条目7
  • C#基础控制台程序