【C#语言】字典Dictionary的内部实现原理是什么？

泛型集合命名空间using System.Collections.Generic;

任何键都必须是唯一

该类最大的优点就是它查找元素的时间复杂度接近O(1)，实际项目中常被用来做一些数据的本地缓存，提升整体效率。

实现原理

1、哈希算法：将不定长度的二进制数据集给映射到一个较短的二进制长度数据集一个Key通过HashFunc得到HashCode

2、Hash桶算法：对HashCode进行分段显示，常用方法是对HashCode直接取余

3、解决碰撞冲突算法（拉链法）：分段会导致key对应的桶会相同，拉链法的思想就像对冲突的元素，建立一个单链表，头指针存储到对应的哈希桶位置。反之就是通过确定hash桶位置后，遍历单链表，获取对应的value

Key值 HashFunc Buckets桶 Entries入口（最小数据结构）

Dictionary字典中最小的数据结构体Entry，调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。

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

Collection版本控制，字典重要变量version，这个变量，在每一次新增、修改和删除操作时，都会使version++

之后每一次迭代过程都会检查版本号是否一致，如果不一致将抛出异常。

这样就避免了在迭代过程中修改了集合，造成很多诡异的问题。