Web Analytics
yangyang

码农兼一个普普通通小青年

Dictionary


从Dictionary中key为大小写不敏感的字符串类型说起

本文由一个在Dictionary中使用String作为key,且支持大小写不敏感匹配的例子来说明Dictionary的内部原理。由Key获取hash值是Dictionary实现的关键。在Dictionary声明的时候,可以通过构造函数传递IEqualityComparer参数来指定比较器,通过该对象来获取哈希值。如果不提供这个参数,则会在内部判断Key是否实现了IEquatable泛型接口,如果提供了,则使用该泛型接口中定义的GetHashCode来获取哈希值,否则会根据Key的类型生成一个通用的EqualityComparer,这个通过的EqualityComparer的参数是object类型,所以如果Key的类型为结构体,则必须为其实现IEquatable泛型接口,否则就会产生装箱从而严重影响性能。 …

Dictionary Hash StringComparer IEquatable IEqualityComparer

.NET Core中Dictionary的实现

Dictionary是一种存储键值对的数据结构,可以根据Key快速查找对应的Value,它的内部实现原理其实很简单,在浅谈算法和数据结构: 十一 哈希表这篇文章中有详细介绍,但实际的原理和工程实现可能有所不同,在.NET中有.NET Framework和.NET Core的两个版本,大体相同,但细节上有所区别。这里以.NET Core中的Dictionary源码为例,来说明Dictionary的实现细节。 …

Hashtable Dictionary

浅谈算法和数据结构: 十一 哈希表

在前面的系列文章中,依次介绍了基于无序列表的顺序查找,基于有序数组的二分查找,平衡查找树,以及红黑树,下图是他们在平均以及最差情况下的时间复杂度: 可以看到在时间复杂度上,红黑树在平均情况下插入,查找以及删除上都达到了lgN的时间复杂度。 那么有没有查找效率更高的数据结构呢,答案就是本文接下来要介绍了散列表,也叫哈希表(Hash Table) 什么是哈希表 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。 使用哈希查找有两个步骤: 使用哈希函数将被查找的键转换为数组的索引。在理想的情况 …

Hashtable Dictionary .NET

  • 1