数据结构(第九章 查找).pptVIP

9.2 动态查找表 B+树 B 树(上图)与B+树（下图）比较 B 树与B+树的随机查找、插入、删除的过程基本上与B树类似。只是在查找时，若非终端结点的关键字等于给定值，并不终止，而是继续向下直到叶子结点。 9.3 哈希表 哈希表的相关定义 哈希查找:又叫散列查找，利用哈希函数进行查找的过程。 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。 哈希函数:在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。 可写成，addr(ai)=H(ki) 其中： ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字 9.3 哈希表 哈希表的相关定义 哈希表 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。 9.3 哈希表 哈希表的相关定义 * 例 30个地区的各民族人口统计表 编号 地区 总人口 汉族 回族… 1 北京 2 上海 …... …... 以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2 以地区名作关键字，取地区 名称第一个拼音字母的序号 作哈希函数： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 9.3 哈希表 哈希表的相关定义 从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵 活，只要使任何关键字的哈希函数值都落在表长允 许的范围之内即可。 冲突：key1?key2，但H(key1)=H(key2)的现象 9.3 哈希表 哈希函数构造的方法 哈希函数构造的方法 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 9.3 哈希表 哈希函数构造的方法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a ? key + b 此法仅适合于：地址集合的大小 = = 关键字集合的大小 其中a和b为常数 直接定址法 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突. 缺点：要占用连续地址空间，空间效率低。 例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下： 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100 9.3 哈希表 哈希函数构造的方法 数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。 例 有80个记录，关键字为8位十进制数， 哈希地址为2位十进制数 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. ….. ?? ? ??? ?? 分析： ?只取8 ?只取1 ?只取3、4 ?只取2、7、5 ????数字分布近 乎随机 所以：取????任意两位 或两位 与另两位的叠加作哈 希地址 9.3 哈希表 哈希函数构造的方法 9.3 哈希表 哈希函数构造的方法 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 平方取中法 9.3 哈希表 哈希函数构造的方法 将关键字分割成若干部分，然后取它们的叠加和