unity底层架构_unity完全自学手册

unity底层架构_unity完全自学手册从效率上看,同List一样最好在实例化对象时,即new时尽量确定大致数量会更加高效,另外用数值方式做Key比用类实例方式作为Key值更加高效率

第一章(二) – 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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注