首页 > 代码库 > 数据结构中散列表的复习笔记
数据结构中散列表的复习笔记
散列函数是一种将键值映射为散列表中的存储位置的函数。对任意给定的动态查找表T，如果选定了某个“理想的”散列函数H及相应的散列表L，则对T中的每个数据元素X，函数值 H(X.key)就是X在散列表L中的存储位置。插入(或建表)时数据元素X将被安置在该位置上，并且查找X时也到该位置上去查找。
由散列函数决定的数据元素在散列表中的存储位置称为散列地址。因此，散列的基本思想是通过由散列函数决定的键值(X.key)与散列地址(H(X.key))之间的对应关系来实现存储组织和查找运算。
在理想的情况下，散列函数是一个一一对应，即每个键值对应于一个散列地址，且不同的键值对应不同的散列地址。但在实际应用中，这种情况很少出现。在大多数情况下，出现“同义词”并发生“冲突”是不可避免的。
设有散列函数H和键值k1、k2，若k1<>k2且H(k1)=H(k2)，则称k1、k2是（相对于H的）同义词。假如动态查找表中有两个数据元素X1、X2存入同一个散列表，而且它们的键值是同义词，这种情况称为冲突。
当然，我们希望同义词尽量少以便减少冲突。另一方面，由于冲突的不可避免性，又必须考虑在冲突发生时的处理办法。因此，采用散列技术时需要考虑的两个问题是：
①如何构造(选择)"均匀的"散列函数？
②用什么方法解决冲突？
当然，还需考虑散列表本身的组织方法。下面分别加以讨论。
一、散列函数的构造法
这里介绍几种常用的构造方法。按这些方法构造出来的散列函数计算简单而且比较"均匀"（即同义词较少）。以下假定散列地址是自然数。另外假定键值也都是自然数（事实上，键值通常总可以转换为自然数）。
⒈数字分析法
数字分析法又称为数字选择法,适用于下述场合:事先知道所有可能出现的键值,并且键值的位数比散列地址的位数多.在这种情况下可以对键值的各位进行分析,选择分布较均匀的若干位组成散列地址。假定已知可能出现的所有键值中的一部分如下：
0 0 1 3 1 9 4 2 1
0 0 1 6 1 8 3 0 9
0 0 1 7 3 9 4 3 4
0 0 1 6 4 1 5 1 6
0 0 1 8 1 6 3 7 8
0 0 1 1 4 3 3 9 5
0 0 1 2 4 2 3 6 3
0 0 1 9 1 5 4 0 9
……
不难看出，（左起）前三位分布不均匀，第5、7位亦有很多重复，故应将这五位丢弃。剩下的第4、6、8、9位都是分布较均匀的，可考虑它们或它们中的几位组合起来作为散列地址。至于到底选其中的几位，需进一步考虑动态查找表的容量（即其中数据元素的最大数目）以及散列表组织形式。
2.除余法
除余法是一种简单有效的构造法。这种方法不要求事先知道全部键值。其作法 ：选择一个适当的正整数P，以键值除以P所得的余数作为散列地址，即令散列函数H为H(key) ＝ key % p
这一方法的关键在于P 的选取。若选P为偶数，则所得的散列函数总是将奇数键值映射成奇数地址。偶数键值映射为偶数地址。因而增加了冲突的机会。若选P曾键值基数的幂，所得的散列地址实际上是键值的末几位，这也不好。通常选P为小于或等于散列表容量的最小素数。
3.平方取中法
一个数的平方的中间几位与这个数的每一位都有关。利用这一特点，平方限中法以键值平方的中间几位作为散列地址。这一方法计算简单且不需要事先掌握键值的分布情况。又因平方限中能扩大键值差别，所得散列地址比较均匀。4.基数转换法
将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。例如，对于十进制键值210485，先把它看成是十三进制的数，并转换为十进制数：21048513＝2×135+1×134+0×133+4×132+8×13+8＝77193510
然后从中选取几位作为散列地址。通常要求两个基数互素，且新基数比原基数大。
5.随机数法
选择一个随机函数random，以键值在该函数下的值作为散列地址：H（key）= random (key)
当各个键值的位数不同时采用此法较好。
二、动态查找表在开散列表上的实现
采用散列技术需考虑的第二个主要问题是如何解决冲突。而处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常有两类散列表：开散列表与闭散列表。一旦选定了散列函数和散列表的组织形式，就可以确定相应的解决冲突的方法，进而可以给出动态查找表的一个具体实现。本小节先讨论动态查找表在开散列表上的实现。开散列表的组织方式如下。设选定的散列函数为H ，H的值域（即散列地址的集合）这0..n-1。设置一个"地址向量"pointer HP[n],其中的每个指针HP[i]指向一上单链表，该单链表用于存储所有散列地址为 i的数据元素、即所有散列地址为 i的同义词。每一个这样的单链表称为一个同义词子表。由地址向量以及向量中的每个指针所指的同义词子表构成的存储结构称为开散列表。
在开散列表中，所有键值为同义词的数据元素存在同一个同义词子表中，而地址向量中的元素是些同义词子表的表头指针。这就是开散列表解决冲突的方法。这一方法有时称为“拉链法”。具体的散列函数、散列表和处理冲突的方法这三个密相关的部分或方面确定了动态查找表的一个具体的散列存储结构。在此基础之上，可以进一步考虑动态查找表基本运算的实现。
三、开散列表与闭散列表的比较
开散列表与闭散列表的差别类似于单链表与顺序表的差别。开散列表利用链接方法存储同义词，不产生堆积现象，且使得动态查找的基本运算特别是查找、播入和删除易于现实。但由于附加指针域而增加了存储开销。闭散列表无需附加指针域，因此存储效率较高。但由此带来的问题是容易产生堆积，而且某些基本运算不易实现。由于空闲位置是查找不成功的条件，实现删除运算时不能简单地将待删结点置空，否则将截断该后继散列地址序列的查找路径。因此闭散列表上的删除只能在待删结点上做标记。仅当运行到一定阶段进，经过整体考虑和整理，才能真正删除有标记的结点。散列技术的原始动机是无需键值比而完成查找。由于同义词（及堆积现象）的存在，这个"理想"并未完全实现。对开散列表来说，仍需将给定值与同义词子表中各结点的键值比较；对于闭散列表，则需将给定值与后继散列地址序列中结点的键值比较。由于开散列表不产生堆积，其平均查找长度较短。
最后，由于开散列表中各同义词子表的表长是动态变化的，无需事先确定表的容量（开散列表由此得名）；而闭散列表却必须事先估计容量。因此，开散列表更适合于事先前难以估计容量的场合。
需要补充说明的是，线性探测法和二次探测法在本书中是作为闭散列表的解决冲突的方法而提出的。但在某些教科书上，这两种方法又称为"开放定址法"。注意不要将这种"开放"（其含义为散列地址对一切数据元素开放）与本书的"开散列表"（其含义为散列表的存储空间是开放的）相混淆。
数据结构中散列表的复习笔记