二插排序数的查找讲述.ppt

从以上结果可见： 哈希表的平均查找长度是 ? 的函数，而不是 n 的函数 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ? ，使得平均查找长度限定在某个范围内 —— 这是哈希表所特有的特点 哈希表也可以用来构造静态查找表 并且，对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的 ASL=0, 称此类哈希函数为理想（perfect）的哈希函数 * 以例示之，再总结出结论 * 首先要寻找结点A，即从插入结点开始，回逆上去，第一个不平衡的结点。本例中是4。 * 因此, 在插入一 个新结点后，首先要寻找结点A，即从插入结点开始，回逆上去，第一个不平衡的结点。 * 以LL型为例，右单旋转，即中间结点上升为根结点，原根结点，下降为中间结点右孩子，原中间结点的右孩子变为现右孩子的左孩子。其原则为：保持原来排序性不变的前提下，满足其平衡性。 * LR型，先左旋，再右旋，先左旋转化为一棵LL型树，再右旋即可。同理RL型先右旋，再左旋，先右旋转化为一棵RR型树，再左旋即可。多举一二个事例，讲清其本质，笔记2上有例。 * 即以结点C为旋转轴：即也不平衡的结点的孩子结点为转轴，左旋转也！左旋转以后，该孩子结点上升为根结点，原根结点下降为左孩子，原该孩子结点的左孩子，变为现左孩子的右孩子也。 * 即也不平衡的结点的孩子结点为转轴，右旋转也！右旋转以后，该孩子结点上升为根结点，原根结点下降为右孩子，原该孩子结点的右孩子，变为现右孩子的左孩子也。 * LR型：先左旋，变为LL型后，然后再右旋也。 * 先以不平衡的结点的左孩子的右孩子为支点左旋转，即E上升为B的位置，B下降为E的左孩子，F变为B的右孩子，变为LL型。 * 变为LL型后，再以不平衡结点的左孩子为支点，右旋转，该结点下升为根结点，原根结点下降为右孩子，原右孩子变为现右孩子的左孩子。妙也！ * 先右旋，变为RR型后，再左旋即可。 * 妙也！LR型，先左旋，14变为15的左孩子，即变为LL型，然后再右旋，16变为15的右孩子。 根据设定的哈希函数 H( key ) 和所选处理冲突的方法，将一组关键字映象到一个有限的、连续的地址集 ( 区间) 上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置，如此构造所得的查找表称为“哈希表”，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。 对数字的关键字可有下列构造方法 若是非数字关键字，则需先对其进行数字化处理 直接定址法 平方取中法 除留余数法 折叠法 随机数法 数字分析法 9.3.2 哈希函数的构造方法 对同一实际问题构造哈希表的方法很多，从而可以构造出很多的哈希函数，什么是好的哈希函数?P253均匀分布 数字分析法 此方法适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度 假设关键字是以r为基数的数，并且事先知道所有可能出现的关键字，每个关键字都是由 s 位数字组成 (u1, u2, …, us)，则可取关键字的若干位数组成哈希地址。讲解P254的例 平方取中法 取关键字平方后的中间几位为哈希地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 此方法适合于: 关键字中的每一位都有某些数字重 复出现频度很高的现象 折叠法 将关键字分割成位数相同的若干部分（最后一部分的位数可能不同），然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加（舍去进位） 此方法适合于: 关键字的数字位数特别多 直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即： H(key) = key 或者 H(key) = a ? key + b 其中a和b为常数。 直接定址法的优点：无冲突 此法适合于以下情形： 地址集合的大小 = = 关键字集合的大小 除留余数法 取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即，设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 一般要求：讲清为什么 p为不大于 m 的素数（避免同义词） 或是 不含 20 以下的质因子 （减少同义词） 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即，设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数