【Unity主程手记（摘录）】第一章（二） – Dictory 底层源码剖析

大家好，欢迎来到IT知识分享网。

第一章（二） – 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)) { 
            // } 

附录

主程手记