字典表示一种非常复杂的数据结构,这种数据机构允许按照某个键来访问元素。字典也称为映射或散列表。字典的主要特性是根据键快速查找值。也可以自由添加和删除元素,这有点想List<T>,但没有在内存中移动后续元素的性能开销。
.NET Framework提供了几个字典类。可以使用的最主要的类是Dictionary<TKey,TValue>。这个类的属性和方法与的SortedList<TKey,TValue>几乎完全相同。
键的类型
用作字典的键的类型必须重写Object类的GetHashCode方法。只要字典类需要确定元素的位置,就要调用GetHashCode()方法。GetHashCode()方法返回的int由字典用于计算放置元素的索引。字典的性能取决于GetHashCode()方法的实现代码。GetHashCode()方法的实现代码必须满足如下要求:
- 相同的对象应总是返回相同的值。
- 不同的对象可以返回相同的值。
- 应执行得比较快,计算开销不大。
- 不能抛出异常。
- 应至少使用一个实例字段。
- 散列码值应平均分布在int可以存储的整个数字区域上。
- 散列码最好在对象的生存期中不发生变化。
为什么要散列码值平均分布在整数的取值区域内?如果两个键返回的散列会得到相同的索引,则字典类就必须寻找最近的可用自由单元来存储第二个数据项,这需要进行一定的搜索,以便以后检索这一项。显然这会降低性能,如果许多键都有相同的索引,这类冲突就比较多。根据Microsoft的部分算法的工作方式,计算出来的散列值平均分布在int.MinValue和int.MaxValue之间时,这种风险会降低到最小。
除了实现GetHashCode()方法外,键类型还必须执行IEquality.Equals()方法,或重写Object类的Equals()方法。因为不同的键对象可能返回相同的散列码,所以字典使用Equals()方法来比较键。字典检查两个键A和B是否相等,并调用A.Equals(B)。这表示确保下述条件总是成立: