第八章+查找.ppt

* (1) 装填因子： 设散列表空间大小为n，填入表中的结点数为m,则称?=m/n为散列表的装填因子。 (2) 散列函数的选取原则： ①运算简单； ②函数值域不能超过表长； ③尽可能使关键字不同时，散列函数值也不同。 (3) 冲突与同义词 若H(k1)=H(k2),则称为冲突， 发生冲突的两个关键字k1和k2称为同义词。 哈希表的有关概念 8.3.1 什么是哈希表 * 直接定址法 8.3.2 哈希函数的构造方法 取关键字或关键字的某个线性函数值为哈希地址。 即：H(key)=key或H(key)=a*key+b 其中a、b为常数。又称H(key)为自身函数。 优点：没有冲突； 缺点：若关键字集合很大，浪费存储空间严重。 * 质数除余法 8.3.2 哈希函数的构造方法 如果表长为n，取小于或等于n的最大质数m作模，关键字通过m取模运算，所得值作为散列地址。 * 平方取中法 关键字 (关键字)2 地址 0100 0010000 100 0110 0012100 121 1010 1020100 201 1001 1002001 020 0111 0012321 123 int Hash(int key) { //假设key是4位整数 key*=key； //求平方 key=key/100； //去掉末尾的两位数 Key=key%1000; ? return key；} 8.3.2 哈希函数的构造方法 在不知道关键字的全部情况时，可通过求关键字的平方值扩大差别，然后取中间几位作为哈希地址： * 折叠法 数字分析法 基数转换法 8.3.2 哈希函数的构造方法 * 又叫开放地址，用于顺序存储； 开放地址指地址单元为空，对于数组来说，是指还没存入数据的数组单元，在顺序存储结构中用一定方法进行散列存取的方法称为开放定址法。 开放定址法的定义 8.3.3 处理冲突的方法 * 设散列表的长度为13，散列函数为: H(K)=K%13,给定的关键字序列为: 19,14,23, 1,68,20,84,27,54,11,10, 0 1 2 3 4 5 6 7 8 9 10 11 12 14 23 (1)线性探测再散列法：若H(key)=d的单元发生冲突，则按下述方法进行探查： hi(k)=(h(k)+i)%n,n是散列表的长度，1≤i≤n-1 1 68 20 19 27 54 H(K)=6, 1,10, 1, 3, 7, 6, 1, 2, 11,10, 11 10 84 开放定址法示例演示 8.3.3 处理冲突的方法 例 * 二次聚集的概念 8.3.3 处理冲突的方法 两个本来不发生冲突的非同义词，也就是散列地址不同的结点，发生争夺同一个散列地址的现象称为二次聚集或堆积。 * 查找分析：查11，查40。 1、利用散列函数计算出关键字为K的数据元素的地址：d=H(K)，如果F[d].key==K,查找成功，返回d; 2、如果F[d].key!=K,依次查找F[(d+i)%n].key, 直到找到某个F[(d+j)%n].key==K,返回(d+j)%n, 或者找到一个开放地址为止，此时显示没找到。 19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10, 0 1 2 3 4 5 6 7 8 9 10 11 12 14 23 1 68 20 19 27 54 H(K)=6, 1,10, 1, 3, 7, 6, 1, 2, 11,10, 11 10 84 开放定址法查找示例演示 8.3.3 处理冲突的方法 * 删除分析：如果删除68，查找27。 删除结点时不能简单地将被删结点的地址置空，否则将截断它之后填入散列表的同义词的查找路径。 19,14,23, 1,68,20,84,27,54,11,10, 0 1 2 3 4 5 6 7 8 9 10