二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(18)

在散列表上进行查找的方法简称为散列法或哈希法 hash method ，它也是另一类较为特殊而又常用的查找方法。它的基本思想和前面讲述的查找方法完全不同，前面介绍的各种查找方法，无论是线性表上的查找，还是树表上的查找，它们的一个共同的特征是：都要根据给定值K，通过一系列的比较，才能确定是查找成功还是查找失败。所以统称为对关键字进行比较的查找方法。然而散列的方法却不同，它是在对关键字做某种运算后直接确定其元素相应的位置 地址 。所以，哈希法又称为散列地址编码法。用散列法存储的表叫作散列表。假设R是长度为n的表，Ri 1≤i≤n 为表中某一元素，Ki是其关键字，则在关键字Ki和表中元素Ri的地址 位置 之间存在着一定的函数关系，即：LOC Ri h Ki其中LOC Ri 是Ri在表中的地址 位置 ；h 称为散列 哈希 函数 hash function 。通过散列函数就可以把关键字集合的元素映像到地址集合中的元素。换句话说，通过关键字，建立了结点集合到地址集合的映射。因此，有了散列函数，便可根据关键字确定任一元素 结点 在表中的存放地址 位置 ，并将此结点存入此地址中，反之，查找时，可利用同一散列函数，求得给定关键字的对应地址，从而找到所需的结点。

若存放表的区域范围为0～m-1，则应确保关键字集合的任意元素都要映射到这个允许的区域之内，即：0 ≤h Ki ≤m-1 1≤i≤n散列法一般需要完成两项工作：一是建立散列表；二是在散列表上进行查找。而这两者通常是交替地同时进行的。下面通过例子来做进一步的说明。例9.18 假如有记录ABCD, BDEF, IJKL, 其相应的关键字为A, B, I。设散列函数为h Ki 关键字Ki的ASCII码 + 27 其中，A, B和I的ASCII码分别为065, 066, 073, 27用二进制数表示为 10000000 2，那么，散列后的地址编码如下：h A 065 + 27 1 000 001 2 + 10 000 000 2 11 000 001 2h B 066 + 27 1 000 010 2 + 10 000 000 2 11 000 010 2h I 073 + 27 1 001 001 2 + 10 000 000 2 11 001 001 2按照此散列函数h就可把以关键字Ki为自变量的记录映射到以散列函数值为h Ki 为地址的散列表中 详见图9-33 。此表建好后，就可根据此表查找出表中任一关键字的地址。

例如，若要查找关键字为B的记录，则用上述散列函数就可快速确定它的地址为11000010。对于静态的表，可以先生成散列表，然后在表上进行查找操作。而对于动态的表，则需查找和插入操作同时进行，即散列表是在不断地进行查找和插入的过程中逐步地形成的。例9.19 假设要建立一张全国34个地区的各民族人口统计表，每个地区为一个记录，记录的各字段为：编号 地区名 总人口 汉族 满族 朝 … 虽然可用一个一维数组table[0‥33] 来存放这张表，其中table[i] 是编号为i的地区的人口情况。显然，编号i可以作为记录的关键字，它能唯一确定记录的存贮位置table[i]。例如，假设北京市的编号为0，则要查看北京市的各民族人口情况，只要取出table[0] 的记录即可。如果要把这个数组视为散列表，则散列函数为h key key 。然而，用此散列函数形成的散列表却不易使用，因为这需要记住各地区的编号，查找起来就不太方便。如果关键字的集合很大，则更是一件很困难的事情。实际使用中，通常是选取地区名来作为关键字。假设地区名用汉语拼音符号来表示，则不能简单地取散列函数h key key，而是要把它们转化为数字，有时还要做一些其他的处理。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-18.html