数据结构9剖析.ppt

9.2 动态查找表 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sqt root m=4 2 ? n ? 4 9.2 动态查找表 查找过程 在 B+ 树上，既可以进行缩小范围的查找(从根结点开始)，也可以进行顺序查找(从含最小关键字的结点开始) 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束 若在结点内查找时，给定值≤Ki， 则应继续在 Ai 所指子树中进行查找 插入和删除的操作 仅在叶子结点上进行 类似于B-树进行，即必要时，也需要进行结点的“分裂”或“合并” 9.3 哈希表 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同 对于频繁使用的查找表，希望 ASL =0 只有一个办法：预先知道所查关键字在表中的位置。即要求：记录在表中位置和其关键字之间存在一种确定的关系 9.3 哈希表 例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份) 若以下标为000 ~ 999 的顺序表表示之 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字 因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系 9.3 哈希表 哈希表的定义 以H(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数H(key) 为哈希函数 哈希(Hash)表查找，又称为散列表查找，是一种重要的查找技术。哈希表查找因使用哈希函数（又称为散列函数）而得名。哈希函数是一种把关键字映射成记录存储地址的函数 9.3 哈希表 哈希技术是一种基于尽可能的不通过比较操作而直接得到记录的存储位置的想法而提出的一种特殊查找技术。 基本思想是通过记录中关键字的值Key为自变量，通过某一种确定的函数H，计算出函数值H(key)作为存储地址，将相应关键字的记录存储到对应的位置上。 在查找时仍需要用这个确定的函数H进行计算，获得所要查找的关键字所在记录的存储位置。通过这种方法可以不需要或者很少的比较就可以查找到关键字所对应的记录。这里所用的函数H就称为哈希函数或散列函数 9.3 哈希表 利用哈希函数可以实现记录关键字和关键字所对应记录存储地址的转换或映像，这种映像过程称为哈希造表或散列，映像结果产生的哈希函数值H(key)作为存储位置称为哈希地址或散列地址，利用哈希函数映像哈希地址，所得到的存储表称为哈希表或散列表 有时候在向哈希表中存储关键字的时候，会出现一个待插入关键字的记录已经被占用的情况，这种不同的关键字具有相同地址的现象称为冲突（Collision）。具有相同哈希函数值的关键字对相应的哈希函数来说称为同义词，由同义词产生的冲突称为同义词冲突 哈希表中冲突的现象有时是一种很难避免的情况 9.3 哈希表 {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Du} 例 对于如下 9 个关键字 设 哈希函数 H(key) = ?(Ord(第一个字母) -Ord(A)+1)/2? 问题: 若添加关键字 Zhou , 怎么办？ 能否找到另一个哈希函数？ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Zhao Qian Sun Li Wu Chen Han Ye Du 9.3 哈希表 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的大小不超出允许范围即可 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1? key2，而 H(key1) = H(key2) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外; 还需要找到一种“处理冲突” 的方法 9.3 哈希表 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表” 构造哈希函数的方法 对数字的关键字可有下列构造方法 若是非数字关键字，则需先