第七章哈希表..docVIP

哈希表又称散列表,实际上就是一个数组。 哈希函数是一个用来求存储在哈希的关键字 在哈希表的地址下标的函数. 比如一个哈希表 int hashtable[5]; 现在有下面4个数要存入到哈希表中: （3，15，22，24） 给定一个哈希函数 : H(k)=k % 5 最终数据存储如下图： 理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突。 把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。 在大多数情况下，冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大，而对应的地址数则可能比较少。 对于哈希技术，主要研究两个问题： （1）如何设计哈希函数以使冲突尽可能少地发生。 （2）发生冲突后如何解决。 哈希函数的构造方法: 构造好的哈希函数的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。 1．直接定址法 直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)为： H(k)=k+c (c≥0) 这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。 2．除留余数法 (注意：这种方法常用) 取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即： H(k)=k％m 这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度m。使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明，在m取值为素数（质数）时，冲突可能性相对较少。 3．平方取中法 取关键字平方后的中间几位作为哈希函数地址（若超出范围时，可再取模）。 4．折叠法 这种方法适合在关键字的位数较多，而地址区间较小的情况。 将关键字分隔成位数相同的几部分。然后将这几部分的叠加和作为哈希地址（若超出范围，可再取模）。 例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加。即有5355+8101+1046+430=14932，舍去高位。 则有H(430104681015355)=4932 为该身份证关键字的哈希函数地址。 5．数值分析法 若事先知道所有可能的关键字的取值时，可通过对这些关键字进行分析，发现其变化规律，构造出相应的哈希函数。 若取最后两位作为哈希地址，则哈希地址的集合为下表所示： 冲突解决 开放地址法 处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突，则再求下一个，依次类推。直至新的哈希地址不再发生冲突为止。 用开放定址法处理冲突就是当冲突发生时，形成一个地址序列。沿着这个序列逐个探测，直到找出一个“空”的开放地址。将发生冲突的关键字值存放到该地址中去。 如 Hi=(H(k)+d（i）) % m, i=1，2，…k (km-1) 其中H(k)为哈希函数，m为哈希表长，d为增量函数，d(i)=dl，d2…dn-l。 增量序列的取法不同，可得到不同的开放地址处理冲突探测方法。 1.1线性探测法 线性探测法是从发生冲突的地址（设为d）开始，依次探查d+l，d+2，…m-1（当达到表尾m-1时，又从0开始探查）等地址，直到找到一个空闲位置来存放冲突处的关键字。 若整个地址都找遍仍无空地址，则产生溢出。 线性探查法的数学递推描述公式为： 注释:这里的di-1 为上一次哈希值 例题：已知哈希表大小11，哈希表名字为A, 给定关键字序列（20，30，70，15，8，12，18，63，19）。哈希函数为H(k)=k％ll，采用线性探测法处理冲突，则将以上关键字依次存储到哈希表中。试构造出该哈希表，并求出等概率情况下的平均查找长度。 本题中各元素的存放到哈希表 过程如下： H(20)=9，可直接存放到A[9]中去。 H(30)=8，可直接存放到A[8]中去。 H(70)=4，可直接存放到A[4]中去。 H(1