一、基础概念

      哈希（Hash又称散列）：将任意长度的消息压缩到某一固定长度的消息摘要的函数。

      哈希表Hashtable：给定一张表，通过哈希函数F(key)能将键值转化成表中的一个地址，便是哈希表。

      哈希Hash函数：能将键值转换为哈希表范围内的索引（0~M-1）的函数。

      哈希Hash冲突：利用哈希函数计算地址时，不同的key值计算出了一样的结果，这种现象称为哈希冲突。

       装载因子：是0.1 到 1.0 范围内的数字。 

二、构造Hash函数的方法 

1 直接定址法
　　取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b。

2 平方取中法
　　对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取中间的两位数{72，89，00}作为Hash地址。

3 折叠法
　　将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。 

4 数字分析法

5 除留取余法

如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p，p一般取不大于m的最大质数。

6 伪随机数法 

如此多的构建哈希函数的方法，在选择的时候，需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面：

关键字的长度。如果长度不等，就选用随机数法。如果关键字位数较多，就选用折叠法或者数字分析法；反之如果位数较短，可以考虑平方取中法；哈希表的大小。如果大小已知，可以选用除留余数法；关键字的分布情况；查找表的查找频率；计算哈希函数所需的时间（包括硬件指令的因素）。

三、哈希Hash冲突解决方法

哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，发生冲突的可能性又跟以下两个因素有关：

（1） 装填因子α  C#的HashTable类把α的最大值定为0.72。

（2） 与所采用的哈希函数有关。 

冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内：

（1） 开散列法发生冲突的元素存储于数组空间之外。可以把“开”字理解为需要另外“开辟”空间存储发生冲突的元素。主要方法有链地址法和公共溢出法。 

（2）闭散列法发生冲突的元素存储于数组空间之内。方法有：线性探测、二次探测、伪随机数探测法以及再哈希法。 

四、C#中哈希表Hashtable的实现 

在C#中，实现了哈希表数据结构的集合有二类： 

System.Collections.Hashtable 

System.Collections.Generic.Dictionary<TKey,TValue> 

前者为一般类型的哈希表，后者是泛型版本的哈希表。Dictionary和Hashtable之间并非只是简单的泛型和非泛型的区别，两者使用了完全不同的哈希冲突解决办法。

单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分。
    多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入, 多线程读取, 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型。而 Dictionary 非线程安全, 必须人为使用 lock 语句进行保护。

五、剖析System.Collections.Hashtable

Hashtable的实现原理 

C#对Hashtable的设计是可以使用任何数据类型作为其关键字。C#中，每种类型都是直接或间接从object派生的，它在object类中定义了一个GetHashCode()方法，这个方法默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修改。因此所有对象都可以访问该方法。自然，字符串或其他类型都能以唯一的数字值来表示。也就是说，GetHashCode()方法使得所有对象的哈希函数构造方法都趋于统一。当然，由于GetHashCode()方法是一个虚方法，你也可以通过重写这个方法来构造自己的哈希函数。

Hashtable使用了闭散列法来解决冲突，它通过一个结构体bucket来表示哈希表中的单个元素，这个结构体中有三个成员：

（1）key ：表示键，即哈希表中的关键字。

（2） val ：表示值，即跟关键字所对应值。

（3）  hash_coll ：它是一个int类型，用于表示键所对应的哈 

希码。

int类型占据32个位的存储空间，它的最高位是符号位，为“0”时，表示这是一个正整数；为“1”时表示负整数。hash_coll使用最高位表示当前位置是否发生冲突，为“0”时，也就是为正数时，表示未发生冲突；为“1”时，表示当前位置存在冲突。之所以专门使用一个位用于存放哈希码并标注是否发生冲突，主要是为了提高哈希表的运行效率。 

Hashtable解决冲突使用了双重散列法。

它探测地址的方法如下： 

h(key, i) = h₁(key) + i * h₂(key)

其中哈希函数h₁和h₂的公式如下： 

h₁(key) = key.GetHashCode()

h₂(key) = 1 + (((h₁(key) >> 5) + 1) % (hashsize - 1)) 

由于使用了二度哈希，最终的h(key, i)的值有可能会大于hashsize，所以需要对h(key, i)进行模运算，最终计算的哈希地址为：

哈希地址 = h(key, i) % hashsize

bucket结构体的hash_coll字段所存储的是h(key, i)的值而不是哈希地址。 

哈希表的所有元素存放于一个名称为buckets（又称为数据桶） 的bucket数组之中。 

六、C#中实现哈希表Hashtable源代码 

哈希表的实现较为复杂，为了简化代码，作者忽略了部分出错判断及自动扩容部分，测试时请不要设置空值，须手动设置表大小。 

七、哈希表Hashtable源代码解读

1、HashHelpers这个辅助类 

先对HashHelpers类的二个关键方法进行介绍。

这是一张素数表，共72个元素，所有元素都是符合f(n) =1 +2n(n=1,2,….)的素数。这样做一方面加快了寻找素数的速度，另一方面也排除了一些不合适的素数。 

GetPrime是用于获得一个素数，如果min小于预定表的最大数7199369就直接返回素数表中大于min数中最小的一个，如果超出预定表的最大数7199369，就按另一种复杂的方法判断。

2、构造函数 

Hashtable的构造函数需要2个参数，一个是容量，一个是装载因子。 

装载因子是存储桶数（count）所占桶数组（buckets）桶数（hashsize）的最大比率。bucket桶这个类型存储Hashtable的Hash信息。装载因子默认为1.0，但实际上微软将它设为0.72。

Hashtable内部的构造函数主要做了什么呢？它利用容量 /装载因子获取了一个桶数组大小的估值，借助HashHelpers.GetPrime获取了一个大于等于3的素数作为内部桶数组的初始长度，并以此长度初始桶数组。

3、哈希算法函数 

Hashtable内部采用的是双重散列法。

我们可以看到函数利用out 关键词引用传递了seek和incr2个变量，seek就是key本身的哈希值，incr则是第二个哈希函数的增量。

就是有2个哈希函数，如果bucketNumber发现是冲突的地址，就利用第二个哈希函数继续计算地址，如果一直失败就持续为上次的·计算结果加上增量，至于% (uint)lbuckets.Length)是为将计算后的地址限制在哈希表的地址范围。

4、插入和修改元素

添加元素使用Add()方法，当Add参数的的实参为true时表示添加操作，为false时为修改操作。

接着在循环体内按照双重散列法寻找对应键的桶赋值。

5、删除元素

  元素删除的核心就是按照双重散列法寻找对应键的桶后，将桶变成空桶。

八、哈希表Hashtable效果图 

固定链接 | 评论 (0) | 订阅文章