《Unity3D高级编程之进阶主程》第一章 C#要点技术(二) - Dictionary 底层源码剖析

本文主要是介绍《Unity3D高级编程之进阶主程》第一章 C#要点技术(二) - Dictionary 底层源码剖析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Dictionary 底层结构

        与Java中的HashMap结构类似。(Java工作者应该很熟悉)Dictionary底层数据结构是一个存放指针的数组。(数组 + 链表)

        Dictionary 字典型数据结构,是以关键字Key 和 值Value 进行一一映射的。这种映射关系是用一个Hash函数来建立的。解决Hash冲突的方法同样是拉链法。

        当我们实例化 new Dictionary() 后,内部的数组是0个数组的状态。

Add 接口:Insert 的代理

public void Add(TKey key, TValue value)
{Insert(key, value, true);
}

Insert 接口

        它们有专门的方法来计算到底该使用多大的数组。源码 HashHelpers 中,primes数值是这样定义的:

public static readonly int[] primes = {3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};public static int GetPrime(int min) 
{if (min < 0)throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));Contract.EndContractBlock();for (int i = 0; i < primes.Length; i++) {int prime = primes[i];if (prime >= min) return prime;}//outside of our predefined table. //compute the hard way. for (int i = (min | 1); i < Int32.MaxValue;i+=2) {if (IsPrime(i) && ((i - 1) % Hashtable.HashPrime != 0))return i;}return min;
}// Returns size of hashtable to grow to.
public static int ExpandPrime(int oldSize)
{int newSize = 2 * oldSize;// Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow.// Note that this check works even when _items.Length overflowed thanks to the (uint) castif ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize){Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");return MaxPrimeArrayLength;}return GetPrime(newSize);
}

         扩容操作:当没有指定默认值时,初始值是3。每次扩容会调用ExpandPrime,会先在原有的基础上扩大两倍,然后再调用GetPrime方法获取最终扩容长度。例如:3->7->17->37->….

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int targetBucket = hashCode % buckets.Length;

        当调用函数获得Hash哈希值后,还需要对哈希地址做余操作,以确定地址落在 Dictionary 数组长度范围内不会溢出。紧接着对指定数组单元格内的链表元素做遍历操作,找出空出来的位置将值填入。

        当获得Hash值的数组索引后,我们知道了该将数据存放在哪个数组位置上,如果该位置已经有元素被推入,则需要将其推入到链表的尾部

        每存放一个元素,不论是否发生hash碰撞,记录剩余单元格数量的变量 freeCount-1。如果freeCount == 0,执行扩容操作。

Remove 接口

        用哈希函数 comparer.GetHashCode 再除余后得到范围内的地址索引,再做余操作确定地址落在数组范围内,从哈希索引地址开始,查找冲突的元素的Key是否与需要移除的Key值相同,相同则进行移除操作并退出。

        Remove 的移除操作并没有对内存进行删减,而只是将其单元格置空,这是位了减少了内存的频繁操作。

ContainsKey 接口

       它调用了 FindEntry 函数,FindEntry 查找Key值位置的方法跟前面提到的相同。从用Key值得到的哈希值地址开始查找,查看所有冲突链表中,是否有与Key值相同的值,找到即刻返回该索引地址。

TryGetValue 接口

        同样调用FindEntry接口

哈希函数中的比较函数

        源码中,对数字,byte,有‘比较’接口(IEquatable<T>),和没有‘比较’接口,四种方式进行了区分对待。

  • 数字和byte:固定的比较函数
  • 有‘比较’接口(IEquatable<T>)的实体:GenericEqualityComparer<T>来获得哈希函数
  • 没有‘比较’接口(IEquatable)的实体,如果继承了 Nullable<U> 接口: NullableEqualityComparer
  • 什么都不是:ObjectEqualityComparer<T>,比较内存地址

非线程安全

Dictionary 同List一样并不是线程安全的组件,官方源码中进行了这样的解释。

** Hashtable has multiple reader/single writer (MR/SW) thread safety built into 
** certain methods and properties, whereas Dictionary doesn't. If you're 
** converting framework code that formerly used Hashtable to Dictionary, it's
** important to consider whether callers may have taken a dependence on MR/SW
** thread safety. If a reader writer lock is available, then that may be used
** with a Dictionary to get the same thread safety guarantee. 

        Hashtable在多线程读写中是线程安全的,而 Dictionary 不是。如果要在多个线程中共享Dictionaray的读写操作,就要自己写lock以保证线程安全。

总结

      Dictionaray是由数组构成,并且由哈希函数完成地址构建,由拉链法冲突解决方式来解决冲突。

        从效率上看,同List一样最好在实例化对象时,即 new 时尽量确定大致数量会更加高效,另外用数值方式做Key比用类实例方式作为Key值更加高效率。

        从内存操作上看,大小以3->7->17->37->….的速度,每次增加2倍多的顺序进行,删除时,并不缩减内存。

        如果想在多线程中,共享 Dictionary 则需要进行我们自己进行lock操作。

这篇关于《Unity3D高级编程之进阶主程》第一章 C#要点技术(二) - Dictionary 底层源码剖析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1076969

相关文章

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进

C#中Guid类使用小结

《C#中Guid类使用小结》本文主要介绍了C#中Guid类用于生成和操作128位的唯一标识符,用于数据库主键及分布式系统,支持通过NewGuid、Parse等方法生成,感兴趣的可以了解一下... 目录前言一、什么是 Guid二、生成 Guid1. 使用 Guid.NewGuid() 方法2. 从字符串创建

Python中你不知道的gzip高级用法分享

《Python中你不知道的gzip高级用法分享》在当今大数据时代,数据存储和传输成本已成为每个开发者必须考虑的问题,Python内置的gzip模块提供了一种简单高效的解决方案,下面小编就来和大家详细讲... 目录前言:为什么数据压缩如此重要1. gzip 模块基础介绍2. 基本压缩与解压缩操作2.1 压缩文

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

Java中的for循环高级用法

《Java中的for循环高级用法》本文系统解析Java中传统、增强型for循环、StreamAPI及并行流的实现原理与性能差异,并通过大量代码示例展示实际开发中的最佳实践,感兴趣的朋友一起看看吧... 目录前言一、基础篇:传统for循环1.1 标准语法结构1.2 典型应用场景二、进阶篇:增强型for循环2.

使用Python进行GRPC和Dubbo协议的高级测试

《使用Python进行GRPC和Dubbo协议的高级测试》GRPC(GoogleRemoteProcedureCall)是一种高性能、开源的远程过程调用(RPC)框架,Dubbo是一种高性能的分布式服... 目录01 GRPC测试安装gRPC编写.proto文件实现服务02 Dubbo测试1. 安装Dubb

Qt如何实现文本编辑器光标高亮技术

《Qt如何实现文本编辑器光标高亮技术》这篇文章主要为大家详细介绍了Qt如何实现文本编辑器光标高亮技术,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录实现代码函数作用概述代码详解 + 注释使用 QTextEdit 的高亮技术(重点)总结用到的关键技术点应用场景举例示例优化建议

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据