热门教程推荐
  • 【一】算法是什么
    【一】算法是什么
    提到“算法”,很多人都觉得它高深莫测、晦涩难懂。事实上的确存在一些算法,学员必须具备优秀的数学基础和编程能力才能驾驭。
  • 【二十一】创建之单例设计模式
    【二十一】创建之单例设计模式
    单例模式是Java中最简单的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。
  • 【九】部分背包问题
    【九】部分背包问题
    背包问题是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。
  • 【二】Unity3D视图界面
    【二】Unity3D视图界面
    Unity3D视图界面Unity3D视图界面Unity3D视图界面Unity3D视图界面Unity3D视图界面Unity3D视图界面Unity3D视图界面Unity3D视图界面
  • 【九】Unity3D游戏发布
    【九】Unity3D游戏发布
    Unity3D游戏发布Unity3D游戏发布Unity3D游戏发布Unity3D游戏发布Unity3D游戏发布Unity3D游戏发布Unity3D游戏发布Unity3D游戏发布
  • 【十】表查找解
    【十】表查找解
    查找表又可分为静态查找表和动态查找表。借助静态查找表可引申出顺序查找算法、折半查找算法、分块查找算法等;而记住动态查找表,也可以通过构建二叉排序树、平衡二叉树等实现查找操作。
  • 【二】游戏世界之渲染窗口
    【二】游戏世界之渲染窗口
    游戏世界之渲染窗口
  • 【九】动态内存管理
    【九】动态内存管理
    动态内存管理机制,主要包含两方面内容,用户申请内存空间时,系统如何分配;用户使用内存空间完成后,系统如何及时回收。

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

4847

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

任何键都必须是唯一

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

实现原理

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

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

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

Key值 HashFunc Buckets桶 Entries入口(最小数据结构)

字典Dictionary的内部实现原理是什么?_C#语言-游民部落(gamecolg.com)

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++

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

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


特别声明:本文仅供交流学习 , 版权归属原作者,并不代表游民部落赞同其观点和对其真实性负责。若文章无意侵犯到您的知识产权,损害了您的利益,烦请与我们联系vmaya_gz@126.com,我们将在24小时内进行修改或删除。

相关推荐:

精品教程推荐
  • 【四】3D美术资源规范
    【四】3D美术资源规范
    美术3D资源规范美术3D资源规范美术3D资源规范美术3D资源规范美术3D资源规范
  • 【三十】游戏UI之列表和无线列表
    【三十】游戏UI之列表和无线列表
    游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表游戏UI界面之列表和无线列表
  • 【二十】排序之快速排序算法
    【二十】排序之快速排序算法
    提到排序算法,多数人最先想到的就是快速排序算法。快速排序算法是在分治算法基础上设计出来的一种排序算法,和其它排序算法相比,快速排序算法具有效率高、耗费资源少、容易实现等优点。
  • 【二】项目工程结构规划
    【二】项目工程结构规划
    项目工程结构规划项目工程结构规划项目工程结构规划项目工程结构规划
  • 【六】数组和广义表
    【六】数组和广义表
    数组存储结构,99%的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。
  • 【七】Unity3D模型与动画
    【七】Unity3D模型与动画
    Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画Unity3D模型与动画
  • 【四十三】图之图的应用
    【四十三】图之图的应用
    当图的每条边都被分配了权重时,我们就有了一个加权图,如果边的权重被忽略,那么可以将(每条边的)权重都视为1(译者注:权重都是一样,也就是无权重)。
  • 【八】贪心算法
    【八】贪心算法
    贪心算法是所有算法中最简单,最易实现的算法,该算法之所以“贪心”,是因为算法中的每一步都追求最优的解决方案。