C#中Dictionary的实现简述
更详细的解析可以查看这篇文章:https://blog.csdn.net/zhaoguanghui2012/article/details/88105715
简要描述就是通过桶Buckets与Entries
1.通过key1值获取哈希值h1 2.h1%桶长度得到入桶位置的m1,Buckets[m1] 3.寻找可存放Entry的位置,得到Entries[n1] 4.h1=>Buckets[m1]=>Entries[n1],形成映射关系
当不同key值hashCode相同时,利用单链表解决碰撞,例如
1.经过上面步骤已经有h1=>Buckets[m1]=>Entries[n1]的关系了,假设有key2获取哈希值同样为h1 2.入桶位置同样为m1,Buckets[m1] 3.寻找Entries位置,得到Entirs[n2] 4.此时即将形成Buckets[m1]=>Entries[n2]的关系,会取代原有关系,此时链表就起作用了 5.链表Entires[n2].next=Buckets[m1],即新元素的下一个指向旧元素 6.Buckets[m1]=Entires[n2],新元素取代以前旧元素的位置 7.5、6步骤就是说,新加入的元素存于链表的第一位,它的next就是上一个元素 8.此时整个映射关系应当是h1=>Buckets[m1]=>Entries[n2] 9.而且还有链表关系Entries[n2].next=>Entries[n1]
那么Dictionary执行查找逻辑顺序就很明显了
1.给定一个key3,获取hash值h3,假定h3与h1相等 2.那么通过关系h1=>Buckets[m1]=>Entires[n2],首先找到了元素n2 3.比较元素n2的key值是否与key3相等,相等就返回n2,不相等则查找链表下一个元素 4.Entries[n2].next=>Entires[n1]找到了n1,继续判定key值是否相等,不相等则继续查找下一个
删除动作
1.通过查找逻辑查找到Entries[x] 2.将其链表上一个元素的next赋值为本元素的.next 3.将其赋值为空,并记录当前Entries的空位置索引freeList=x,将其freeCount++
最新文章
- java常见的问题
- 企业IT管理员IE11升级指南【3】—— IE11 新的GPO设置
- Windows phone应用开发[20]-禁止Pivot手势
- 单页Web应用:
- telnet: connect to address xxxxxxx: No route to host
- 工厂方法(factory method)
- jacob 实现Office Word文件格式转换
- windows系统下的文件夹链接功能mklink/linkd
- Pintos-斯坦福大学操作系统Project详解-Project1
- maven(01)--安装及其介绍
- c# Base64解密加密
- 好的UI管理后台
- docker容器实战-----初级<;2>;
- 在Centos7上安装wxPython4.0.4
- WPF中textBlock 变色功能
- MPU和CPU有什么区别?
- 10. Halloween 万圣节
- mysql登录密码相关
- GO语言的进阶之路-爬虫进阶之路
- 机器学习进阶-案例实战-图像全景拼接-图像全景拼接(RANSCA) 1.sift.detectAndComputer(获得sift图像关键点) 2.cv2.findHomography(计算单应性矩阵H) 3.cv2.warpPerspective(获得单应性变化后的图像) 4.cv2.line(对关键点位置进行连线画图)