System.Collections中字典的介绍及其工作原理

朱雀 2022-08-25 12:47 97阅读 0赞

**字典的介绍**

图10-5是字典的一个简化表示。其中employee-id，如B4711，是添加到字典中的键。键会转换为一个散列。利用散列创建一个数字，它将索引和值关联起来。然后索引包含一个到值的链接。该图做了简化处理，因为一个索引项可以关联多个值，索引可以存储为一个树形结构。

.NET Framework提供了几个字典类。可以使用的最主要的类是Dictionary<TKey, TValue>。这个类的属性和方法与上面的SortedList<TKey, TValue>几乎完全相同，这里不再赘述。

**字典的原理![image023.gif][]**

字典表示一种非常复杂的数据结构，这种数据结构允许按照某个键来访问元素。字典也称为映射或散列表。字典的主要特性是能根据键快速查找值。也可以自由添加和删除元素，这有点像List<T>，但没有在内存中移动后续元素的性能开销。

字典的使用非常方便，但这里有一个问题:Hashtable(和其它字典类)使用某种算法，根据键来确定每个对象的位置，实际上,该算法并不完全是由Hashtable提供的.它有两个部分，其中一部分的代码必须由key类来提供。如果使用一个Microsoft提供的类，并把这个类用作键(例如字符串)，就不会有任何问题。但如果自己编写的key，就必须自己编写这部分算法。

在计算机中，由key类执行的部分算法称为散列(因此字典也称为表)，Hashtable在散列算法中有非常特殊的地位：它提供了对象的getHashCode方法，继承于System.Object。只要字典类需要定位数据项的位置，就会调用键对象的GegHashCode()方法。如果重写了getHashCode 方法，就会对如何重写该方法有很多苛刻要求，原意是重写该方法必须保证字典类能正常工作。

其工作方式是GetHashCode()返回一个int，它应使用这个键的值来生成该int数值，.Hashtable获取这个int， 并对它进行其它的一些操作，其中涉及到一引起复杂的数学计算，最后返回一个索引，表示带有给定散列的数据项在字典中的存储的位置。我们不详细介绍这部分算法，Microsoft 已经为这部分算法编写好了代码，所以不需要详细了解，但该算法用素数，而且这是散列表容量为什么应是一个素数的原因了.

为了使GetHashCode()重写方法正常工作，有一些相当严格的要求。这引起要求听起来相当抽象，难以理解，但不必太担心，编写一个满足要求的key类也不是那么困难(如果有时间,再写出来后面的例子):

*  该方法应比较快(因为在字典中旋转或获取条目要求比较快) 
 *  该方法应比较一致,如果两个键表示相同的值,那么它们必须为散列提供相同的值. 
 *  该方法给出的原因是有一个潜在的问题:如果在字典中,两个数据项的散列有相同的索引,该怎么办? k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。即不同的key 但指向同一个索引位置。

如果发生这种情况，字典就必须寻找最近的可利用的自由单元来存储第二个数据项，必须进行一定的搜索，以便以后获取这个数据项。这显然会降低性能， 如果许多键都有相同的索引，就有可能出现崩溃。根据Microsoft的部分算法工作的方式,在计算出来的散列值平均分布在int.MinValue和int.MaxValue之间时，这种崩溃的危险会被降低到最小（当然是在理论上）.  hashtable 利用load factor 来控制负载比例，

散列表的装填因子 load factor = 表中填入的结点数/表长. α越大，表越满，冲突的机会也越大。通常取α≤1。

字典的元素最多，键之间的崩溃危险也就越大，所以最好确保字典的容量大于其中的元素个数。因此,在字典被填满之前，Hashtable会自动重新分配内存，增大其容量，表被填满的比例称为负载(load)，可以为这个负载设置一个最大值, 该负载会达到这个最大值是，在另一个Hashtable构造函数中给Hashtable重新分配内存:

//capacity = 50,MaxLoad=0.5

Hashtable Employees = new Hashtable(50,0.5)

负载的最大值越小，散列表的工作次序就越高，但它占据的内存也越大。当散列表为了增大其容量而重新分配内存时，总会选择一个素数作为其新容量.

上面列出的另一个要点是，散列算法必须一致，如果两个key对象包含相同的数据（A == B）它们就必须给出相同的散列值，这就是重写System.Object的Equals()和GetHashCode()方法时，必须遵循的重要限制，Hashtable确定两个键A和B是否相等的方式就是调用A.Equals(B)，即必须确保下述条件总是true:

如果A.Equals(B)是true，则A.GetHashCode()和B.GetHashCode()必须返回相同的散列.

这看起来可能非常微妙，但非常重要。如果采用重写方法不能保证上述语句为true，用这个类实例作为键的散列表就不可能正常工作。例如,把一个对象放在散列表中，但从来没有猎取过它，或者试图获取一个数据项，但会返回错误的数据项.

因此，如果为Equals()提供了一个重写方法，但没有为GetHashCode()提供重写方法，C\#编译器就会显示一个编译警告。

对于System.Object，这个条件为true，因为Equals()仅比较引用，GetHashCode会根据对象的地址返回一个散列，也就是说，没有重写这些方法的基于建的hashtable将正常工作。但是，这种方式也有问题，只有键是相同的对象时，才是相等的。当把一个对象放在字典中时，就必须挂起键的引用，以后也不能实例化另一个有相同值的键对象，因为相同的值被定义为表示相同的实例，如果没有重写Equals()和GetHashCode()的Object版本，类就不能在散列表中方便的使用，**因此，应根据键的值来执行GetHashCode()，生成一个散列，而不是根据内存中的地址来执行该方法**，这就是必须为要用作键的类重写Equals()和GetHashCode()的原因.

System.String有三个重载方法,重载Equals()提供了值的对比,GetHashCode()也被相应地重载,根据字符串的值返回一个散列.因此,字典中把字符串用作键是非常方便的.

key 调用散列/gethashcode 生成一个int， hashtable用这个int通过基于素数的复杂算法找到一个索引，即给定散列的数据项在字典中的存储位置。

通过某种算法把键转换成一个索引并将数据项指向这个索引，这个算法就是hashing(散列) 的基本方式。

[image023.gif]: /images/20220824/2422af5ef7744b4e96d84ed39eaf916e.png