页数：27页文件大小：443.9 KB来源： 数据结构-C#语言描述ppt课件
本课件从 object 的 GetHashCode 方法切入讲解哈希表：先给出直接定址法、数字分析法与除留余数法等哈希函数构造方法，再系统讲解闭散列法中的线性探测、二次探测、双重散列与开散列法（链地址法），分析二次聚集现象的成因，最后剖析 C# 中 Hashtable 与 Dictionary 两个集合类的内部结构、冲突解决方式与选用建议。
本页为第八章哈希表封面。本章讲解哈希函数的构造方法、哈希冲突的解决技术，以及 C# 中 Hashtable 与 Dictionary 两个集合类的实现原理。
在 C# 的万物之母 object 对象中定义了一个虚方法 GetHashCode()，这个方法用于获取对象的哈希码。
什么是哈希码？它有什么作用？为什么要在如此重要的类中定义这个方法？哈希码跟哈希表有什么内在的联系吗？本章将对这些问题展开论述。
例 8-1 Demo8-1.cs 使用学号查找学生地址；例 8-2 Demo8-2.cs 演示哈希查找地址（Address）。
已知若干学号与学生地址的对应关系，例如 200809001 广西南宁、200809002 广西南宁、200809003 北京、200809004 上海、200809005 广东深圳。
若把学号直接作为数组下标，需要开辟与学号等长的巨大空间；而通过哈希函数把学号映射到较小的连续索引区间，即可用很小的空间实现快速查找。
构造哈希函数的目标是使哈希地址尽可能均匀地分布在连续的内存单元地址上，以减少冲突发生的可能性，同时使计算尽可能简单以达到尽可能高的时间效率。
根据关键字的结构和分布不同，可构造出与之适应的各不相同的哈希函数。这里主要讨论几种常用的整数类型关键字的哈希函数构造方法。
直接定址法取关键字或关键字的某个线性函数为哈希地址。即：h(key) = key 或 h(key) = a × key + b，其中 a、b 为常数，调整 a 与 b 的值可以使哈希地址取值范围与存储空间范围一致。
这种哈希函数计算简单，并且不会有冲突发生。它适合于关键字的分布基本连续的情况，若关键字分布不连续，将造成存储空间的大量浪费。
该方法是提取关键字中随机性较好的数字位，然后把这些数位拼接起来作为哈希地址。
它适合于所有关键字值都已知的情况，并需要对关键字中每位的取值分布情况进行分析。图中给出了若干关键字各位取值的分布，以及从中提取若干位拼接成哈希地址的结果。
除留余数法采用取模运算（%），把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址。哈希函数的形式为：h(key) = key % p。
除留余数法的关键是选好 p，使得记录集合中的每个关键字通过该哈希函数转换后映射到哈希表范围内任意地址上的概率相等，从而尽可能减少发生冲突的可能性。
例如 507683 % 2 的 5 次方相当于取其二进制的低 5 位。
哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，所以在冲突发生时，必须有相应的解决方案。
而发生冲突的可能性又跟以下两个因素有关：
冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。
哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内。
闭散列法是把所有的元素存储在哈希表数组中。当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程称为探测。上述方法可用如下公式表示：
hi = (h(key) + di) % m，其中 i = 1，2，…，k（k ≤ m-1）。
其中 h(key) 为哈希函数；m 为哈希表长；di 为增量的序列。根据 di 取值的不同，可以分成几种探测方法。
线性探测法的基本思想是：当发生冲突时，从冲突位置的下一个单元顺序寻找，只要找到一个空位，就把元素放入此空位中。
顺序查找时，把哈希表看成一个循环表，即如果到最后一个位置也没有找到空位，则回到表头开始继续查找。此时，如果仍然未找到空位，则说明哈希表已满，需要进行溢出处理。
本页给出线性探测法的构造实例：已知一组关键字为（12，19，23，28，39，51，56，76，84），哈希表长 m=13，哈希函数为 h(key) = key % 11。
各关键字按插入顺序依次入表：12 的哈希地址为 1，28 为 6，19 为 8，23 为 1（与 12 冲突后线性后移），39 为 6（冲突后后移），56 为 1（继续后移直到空位），76 为 10，51 为 7，84 为 7（与 51 冲突后后移）。图中标出了各元素的最终下标位置及查找所需的比较次数。
原课件该页表格中关键字、哈希地址与比较次数三组数字在文本提取时粘连严重，为保证数据准确此处未按表格还原，具体数值请以原课件图示为准。
每个元素经哈希函数计算出来的地址称为基地址，这种不同基地址的元素争夺同一个单元的现象叫做二次聚集。
二次聚集实际上是在处理同义词之间的冲突时引发的非同义词的冲突。显然，这种现象对查找不利。线性探测很容易出现二次聚集，小的聚集能汇合成大的聚集，最终导致很长的探测序列，从而降低哈希表的运算效率。
线性探测法的缺点是容易出现二次聚集，为了减少二次聚集的产生，可以加大探测序列的步长，使发生冲突的元素的位置比较分散。
如果在地址 i 产生冲突，不是探测 i+1 地址，而是探测 i + 1 的平方、i-1 的平方、i + 2 的平方、i-2 的平方……的地址。该方法的优点是可以减少二次聚集的产生，缺点是不易探测到整个哈希空间。
双重散列法又称二度哈希，是闭散列法中较好的一种方法，它是以关键字的另一个散列函数值作为增量。设两个哈希函数为 h1 和 h2，则得到的探测序列为：
(h1(key)+h2(key))%m，(h1(key)+2×h2(key))%m，(h1(key)+3×h2(key))%m，……
其中，m 为哈希表长。由此可知，双重散列法探测下一个开放地址的公式为：(h1(key) + i × h2(key)) % m（1≤i≤m-1）。
定义 h2 的方法较多，但无论采用什么方法都必须使 h2(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个哈希表中，否则可能造成同义词地址的循环计算。
若 m 为素数，则 h2 取 1 至 m-1 之间的任何数均与 m 互素，因此可以简单地将 h2 定义为：h2(key) = key % (m-2) + 1。
开散列法的常见形式是将所有关键字为同义词的结点链接在同一个单链表中。
每个单链表中除了表头指针存储在哈希表数组中以外，所有元素都存储在数组以外的空间，哈希表没有“边界”，这也是“开散列法”名称的来源。
关键字为（12，19，23，28，39，51，56，76，84），哈希表长 m=13，哈希函数为 h(key)=key%11，如果使用开散列法进行存储，元素插入单链表时总是插在表头作为第一个结点。
设插入顺序为（12，28，19，23，39，56，76，51，84），其结果如图所示：地址 1 上挂 12、23、56 等结点，地址 6 上挂 28、39，地址 7 上挂 51、84，其余同义词各自成链。
与开放地址法相比，链地址法有如下优缺点。
C# 中实现了哈希表数据结构的集合类有：
前者为一般类型的哈希表，后者是泛型版本的哈希表。Dictionary 和 Hashtable 之间并非只是简单的泛型和非泛型的区别，两者使用了完全不同的哈希冲突解决办法。
object 类中定义了一个 GetHashCode() 方法，这个方法默认的实现是返回一个唯一的整数值以保证在 object 的生命期中不被修改。
GetHashCode() 方法使得 C# 中的所有类型都能以唯一的数字值来表示。
由于 GetHashCode() 方法是一个虚方法，可以通过重写这个方法来构造自己的哈希函数。
Hashtable 使用了闭散列法来解决冲突，它通过一个结构体 bucket 来表示哈希表中的单个元素，这个结构体中有三个成员：
Hashtable 解决冲突使用了双重散列法，但又跟前面所讲的双重散列法稍有不同。它探测地址的方式为：h(key, i) = h1(key) + i × h2(key)。
其中哈希函数 h1 和 h2 的公式如下：
由于使用了二度哈希，最终的 h(key, i) 的值有可能会大于 hashsize，所以需要对 h(key, i) 进行模运算，最终计算的哈希地址为：哈希地址 = h(key, i) % hashsize。
Dictionary 的哈希地址求解较之 Hashtable 简单许多：哈希地址 = key.GetHashCode() % hashsize。
Dictionary 内有两个数组：
entries 中所存放的是 Entry 结构体，它由四个部分组成：
为了正确添加和删除元素，Dictionary 内部维护了三个成员变量：
其中 freeList 把删除后空出的位置串成一条空闲链表，freeCount 记录空闲位置的数量，添加元素时可优先复用这些位置。
本章介绍了哈希表及 C# 中实现了哈希表的两个集合类 Hashtable 和 Dictionary。两种哈希表的区别如下：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}