石河子大学信息科学与技术学院数据结构课件第九章 查找.ppt

9.3 哈希表 除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，p?m。特点：简单、常用，可与上述几种方法结合使用。p的选取很重要；p选的不好，容易产生同义词。 哈希查找过程： ⑷所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，…，Kn，An） ⑸所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。 2 3 7 2 20 25 3 79 84 93 4 35 41 51 53 2 66 68 2 71 76 2 12 30 2 69 78 1 54 t F F F F F F F F F F F F F F F F F F F F F a b c d e g h f i 一棵5阶的B-树 例如： B-树的操作 要查找关键字为k的记录，首先从根结点开始，若相等则找所对应的记录，否则沿P所指结点的子树继续查找，其中： A0 kK1 P = An kKn Ai KikKi+1 若直到叶子结点还未找到，则查找失败。 1）查找： 设要插入关键字为k的记录，指向k所在记录的指针为p。首先找到k应插入的叶子结点，将 p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个。方法是： 申请一个新结点，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则类似处理。 2）插入： 45 24 3 12 37 50 53 90 61 70 95 插入30 37 30 插入85 85 61 85 70 53 90 70 9.3.1 什么是哈希表 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，直接就能得到所查元素的查找方法。 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找：又叫散列查找，利用哈希函数进行查找的过程。 以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2 以地区名作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 例：各民族人口统计表 编号 地区名 总人口 汉族 回族…... 1 北京 2 上海 …... …... 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。 散列表的理想情形：每一个关键字对应一个唯一的地址。 但是实际有可能出现这样的情形：两个不同的关键字有可能对应同一个存储地址，这样，将导致后放的关键字无法存贮，即 key1?key2，但H(key1)=H(key2)，这种现象叫冲突。具有相同函数值的两个关键字，叫该哈希函数的同义词。冲突不可避免，只能尽量减少；因此冲突发生后，应该有处理冲突的方法。 9.3.2 哈希函数的构造方法 数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。适用于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b。特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。实际中能用这种哈希函数的情况很少。 例：有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 ?