考察数据结构(6)

2019-07-13 16:36

更好的挖掘技术是―二次挖掘‖（quadratic probing），每次检查位置空间的步长以平方倍增加。也就是说，如果位置s被占用，则首先检查s+1处，然后检查s-1，s+2，s-2，s+3依此类推，而不是象线性挖掘那样从s+1，s+2……线性增长。当然二次挖掘同样会导致同类聚合。下一节我们将介绍第三种冲突解决机制——二度哈希，它被应用在.Net Framework的哈希表类中。

System.Collections.Hashtable 类

.Net Framework 基类库包括了Hashtable类的实现。当我们要添加元素到哈希表中时，我们不仅要提供元素（item），还要为该元素提供关键字（key）。Key和item可以是任意类型。在员工例子中，key为员工的社保号，item则通过Add()方法被添加到哈希表中。

要获得哈希表中的元素（item），你可以通过key作为索引访问，就象在数组中用序数作为索引那样。下面的C#小程序演示了这一概念。它以字符串值作为key添加了一些元素到哈希表中。并通过key访问特定的元素。 using System;

using System.Collections; public class HashtableDemo {

private static Hashtable ages = new Hashtable(); public static void Main() {

// Add some values to the Hashtable, indexed by a string key ages.Add(\ ages.Add(\ ages.Add(\

// Access a particular key if (ages.ContainsKey(\ {

int scottsAge = (int) ages[\

Console.WriteLine(\ scottsAge.ToString()); } else

Console.WriteLine(\ } }

程序中的ContainsKey()方法，是根据特定的key判断是否存在符合条件的元素，返回布尔值。Hashtable类中包含keys属性（property），返回哈希表中使用的所有关键字的集合。这个属性可以通过遍历访问，如下：

// Step through all items in the Hashtable foreach(string key in ages.Keys)

Console.WriteLine(\ key + \ \要认识到插入元素的顺序和关键字集合中key的顺序并不一定相同。关键字集合是以存储的关键字对应的元素为基础，上面的程序的运行结果是： Value at ages[\ 25 Value at ages[\ 25 Value at ages[\

即使插入到哈希表中的顺序是：Scott，Sam， Jisun。 Hashtable类的哈希函数

Hashtable类中的哈希函数比我们前面介绍的社保号的哈希值更加复杂。首先，要记住的是哈希函数返回的值是序数。对于社保号的例子来说很容易办到，因为社保号本身就是数字。我们只需要截取其最后四位数，就可以得到合适的哈希值。然而Hashtable类中可以接受任何类型的值作为key。就象上面的例子，key是字符串类型，如―Scott‖或―Sam‖。在这样一个例子中，我们自然想明白哈希函数是怎样将string转换为数字的。

这种奇妙的转换应该归功于GetHashCode()方法，它定义在System.Object类中。Object类中GetHashCode()默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修

改。既然每种类型都是直接或间接从Object派生的，因此所以object都可以访问该方法。自然，字符串或其他类型都能以唯一的数字值来表示。 Hashtable类中的对于哈希函数的定义如下：

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize

这里的GetHash(key)，默认为对key调用GetHashCode()方法的返回值（虽然在使用Hashtable时，你可以自定义GetHash()函数）。GetHash(key)>>5表示将得到key的哈希值，向右移动5位，相当于将哈希值除以32。%操作符就是之前介绍的求模运算符。Hashsize指的是哈希表的长度。因为要进行求模，因此最后的结果H（k）在0到hashsize-1之间。既然hashsize为哈希表的长度，因此结果总是在可以接受的范围内。 Hashtable类中的冲突解决方案

当我们在哈希表中添加或获取一个元素时，会发生冲突。插入元素时，必须查找内容为空的位置，而获取元素时，即使不在预期的位置处，也必须找到该元素。前面我们简单地介绍了两种解决冲突的机制——线性和二次挖掘。在Hashtable类中使用的是一种完全不同的技术，成为二度哈希（rehasing）(有的资料也将其称为双精度哈希double hashing)。

二度哈希的工作原理如下：有一个包含多个哈希函数（H1……Hn）的集合。当我们要从哈希表中添加或获取元素时，首先使用哈希函数H1。如果导致冲突，则尝试使用H2，一直到Hn。各个哈希函数极其相似，不同的是它们选用的乘法因子。通常，哈希函数Hk的定义如下： Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

注：运用二度哈希重要的是在执行了hashsize次挖掘后，哈希表中的每一个位置都确切地被有且仅有一次访问。也就是说，对于给定的key，对哈希表中的同一位置不会同时使用Hi和Hj。在Hashtable类中使用二度哈希公式，其保证为：(1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))与hashsize两者互为素数。（两数互为素数表示两者没有共同的质因子。）如果hashsize是一个素数，则保证这两个数互为素数。二度哈希较前两种机制较好地避免了冲突。调用因子（load factors）和扩充哈希表

Hashtable类中包含一个私有成员变量loadFactor，它指定了哈希表中元素个数与表位置总数之间的最大比例。例如：loadFactor等于0.5，则说明哈希表中只有一半的空间存放了元素值，其余一半皆为空。

哈希表的构造函数以重载的方式，允许用户指定loadFactor值，定义范围为0.1到1.0。要注意的是，不管你提供的值是多少，范围都不超过72%。即使你传递的值为1.0，Hashtable类的loadFactor值还是0.72。微软认为loadFactor的最佳值为0.72，因此虽然默认的loadFactor为1.0，但系统内部却自动地将其改变为0.72。所以，建议你使用缺省值1.0（事实上是0.72，有些迷惑，不是吗？）

注：我花了好几天时间去咨询微软的开发人员为什么要使用自动转换？我弄不明白，为什么他们不直接规定值为0.072到0.72之间。最后我从编写Hashtable类的开发团队的到了答案，他们非常将问题的缘由公诸于众。事实上，这个团队经过测试发现如果loadFactor超过了0.72，将会严重的影响哈希表的性能。他们希望开发人员能够更好地使用哈希表，但却可能记不住0.72这个无规律数，相反如果规定1.0为最佳值，开发者会更容易记住。于是，就形成现在的结果，虽然在功能上有少许牺牲，但却使我们能更加方便地使用数据结构，而不用感到头疼。向Hashtable类添加新元素时，都要进行检查以保证元素与空间大小的比例不会超过最大比例。如果超过了，哈希表空间将被扩充。步骤如下：

1．哈希表的位置空间近似地成倍增加。准确地说，位置空间值从当前的素数值增加到下一个最大的素数值。（回想一下前面讲到的二度哈希的工作原理，哈希表的位置空间值必须是素数。） 2．既然二度哈希时，哈希表中的所有元素值将依赖于哈希表的位置空间值，所以表中所有值也需要二度哈希（因为在第一步中位置空间值增加了）。

幸运的是，Hashtable类中的Add()方法隐藏了这些复杂的步骤，你不需要关心它的实现细节。调用因子（load factor）对冲突的影响决定于哈希表的总体长度和进行挖掘操作的次数。Load factor越大，哈希表越密集，空间就越少，比较于相对稀疏的哈希表，进行挖掘操作的次数就越多。如果不作精确地分析，当冲突发生时挖掘操作的预期次数大约为1/(1-lf)，这里lf指的是load factor。

如前所述，微软将哈希表的缺省调用因子设定为0.72。因此对于每次冲突，平均挖掘次数为3.5次。既然该数字与哈希表中实际元素个数无关，因此哈希表的渐进访问时间为O（1），显然远远好于数组的O(n)。

最后，我们要认识到对哈希表的扩充将以性能损耗为代价。因此，你应该预先估计你的哈希表中最后可能会容纳的元素总数，在初始化哈希表时以合适的值进行构造，以避免不必要的扩充。考察数据结构——第三部分：二叉树和BSTs[译]