第一章(二) – Dictory 底层源码剖析
提示:个人学习总结,如有错误,敬请指正。
文章目录
一.Dictory
1.底层数据结构
Key和Value用一个Hash函数来建立映射关系,处理Hash哈希冲突的方法在数据结构中会有详细讲解
Dictionary 是以数组为底层数据结构的类。当我们实例化 new Dictionary() 后,内部的数组是0个数组的状态。与 List 组件一样,Dictionary 也是需要扩容的,会随着元素数量的增加而不断扩容。
2.Add – 添加数据
Add 接口就是 Insert 的代理
返回一个size需要的最小质数值,首次定义为3每次扩容两倍-即3->7->17->37(每次都是质数)
int size = HashHelpers.GetPrime(capacity);
对Hash地址执行余数操作确保再数组长度方范围内不溢出。
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; int targetBucket = hashCode % buckets.Length;
指定数组单元格内的链表元素做遍历操作,找出空出来的位置将值填入;
若数组大小不够则需要再次扩容
3.Remove- 删除数据
- 用哈希函数 comparer.GetHashCode 再除余后得到范围内的地址索引,再做余操作确定地址落在数组范围内,从哈希索引地址开始,查找冲突的元素的Key是否与需要移除的Key值相同,相同则进行移除操作并退出。
- Remove并没有对内存进行删减,而是将对应hash位置置为默认值,这是为了减少内存的频繁操作。
4.其他接口
- ContainsKey :
- 与之前类似,FindEntry使用和前面相同的方式查找key的hash位置,然后从链表里匹配元素,成功返回该索引地址。
- TryGetValue :
- 与 ContainsKey 同样,他调用的也是FindEntry的接口,来获取Key对应的Value值。
5.Hash函数的创建过程
哈希冲突的拉链法贯穿了整个底层数据结构。因此哈希函数是关键了,哈希函数的好坏直接决定了效率高低。
if (t == typeof(byte)) {
return (EqualityComparer<T>)(object)(new ByteEqualityComparer()); } // If T implements IEquatable<T> return a GenericEqualityComparer<T> if (typeof(IEquatable<T>).IsAssignableFrom(t)) {
return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), t); } // If T is a Nullable<U> where U implements IEquatable<U> return a NullableEqualityComparer<U> if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
RuntimeType u = (RuntimeType)t.GetGenericArguments()[0]; if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) {
return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), u); } }
对于数字类型,他们实现了IEquatable接口,直接使用GenericEqualityComparer获得hash函数。否则如果实现了Nullable接口,则调用NullableEquality-Comparer(),如果不是以上两种情况则调用ObjectEqualityComparer。
6.线程安全
和List一样,Dictionary并不是线程安全的
Hashtable在多线程读/写中是线程安全的,而Dictionary不是。如果要在多个线程中共享Dictionary的读/写操作,就要自己写lock,以保证线程安全。
7.总结
- 从效率上看,同List一样最好在 实例化对象时,即 new 时尽量确定大致数量会更加高效,另外用数值方式做Key比用类实例方式作为Key值更加高效率。
- 从内存操作上看,大小以3->7->17->37->….的速度,每次增加2倍多的顺序进行,删除时,并不缩减内存。
- 如果想在多线程中,共享 Dictionary 则需要进行我们自己进行lock操作。
- 减少Dictionary的冗余访问
if(Dic.Contains(key)) {
var result = Dic[key]; } //改写成 value result ; if(Dic.TryGetValue(key,out result)) {
// }
附录
主程手记
今天的文章
unity底层架构_unity完全自学手册分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/80208.html