数据结构与算法分析第五章 散列.ppt

第5章 散列 本章纲要 1.散列基本概念 2.散列函数 3.分离链接法 4.开放定址法 5.再散列 6.可扩散列 1.散列基本概念 散列（hashing） 给定一个数据元素，其关键字为key，将key看成自变量，按一个确定的散列函数 hash 计算出hash(key)，把hash(key)作为关键字key对应元素的存储地址(或称 散列地址)，再进行数据元素的插入和检索操作。 散列表（hash table） 具有TableSize固定大小的数组 TableSize应为质数 1.散列基本概念 散列函数（hash function） 用于关键字与存储地址之间的一种映射。 冲突 两个关键字散列到同一个存储地址 1.散列基本概念 设散列函数 H(k)=k MOD 11，求： 60、17、29、38在散列表中的位置。 H(60)= 60 mod 11 = 5 H(17)= 17 mod 11 = 6 H(29)= 29 mod 11 = 7 H(38)= 38 mod 11 = 5 H(38+1) mod 11 = 6 H(38+2) mod 11 = 7 H(38+3) mod 11 = 8 1.散列基本概念 散列函数应具备的特点 函数的运算应尽可能地简单； 函数的值域必须在散列表的范围内； 关键字值的集合由散列函数映射得到的地址集合均匀分布在散列表范围内，即尽可能使存取结点在散列表中均匀分布； 尽可能减少冲突。 具有解决冲突统一的方法。 1.散列基本概念 负载因子 =数据元素数目m /存储空间的个数n 散列表的操作 支持常数时间的插入、删除和查找 不支持任何排序操作，如FindMin、FindMax 2.散列函数 关键字是整数的常用散列函数： 1.取模法 hash(Key)=Key mod TableSize TableSize为质数 2.线性变换法 hash(key) = a·key + b 其中：a和b为整型常数。 2.散列函数 3.数字分析法 设关键字是d位的以 r 为基的数（譬如以10为基的十进制数），共有n个。关键字的每个位可能有 r 个不同的数符出现（譬如0，1，2，…，9），但这r个数符在各个位上出现的频率不一定相同，可能在某些位上分布比较均匀，即每个数符出现的次数接近于n/r，而在另一些位上分布不均匀。 我们可选取其中分布比较均匀的某些位，重新组成新的数，拿来作为散列地址。当然，所选取的位数和散列地址的位数相同。 123，483，952，527，179，588，841，395，204，649，958，356，607，241，794，495，706，800，302，990. 2.散列函数 4.折叠法 设散列地址的位数为 t，则将关键字分成位数为 t 的若干段（最后一段的位数可能小于t），然后把各段按位对齐进行相加，将所得的和舍弃进位，留下t位作为散列地址。 当关键字位数很多，而且关键字中每位上数字分布大致均匀时，可采用这种折叠法。 TableSize=97，t=229+34+23+91?177 ?77 2.散列函数 5.平方取中法 平方取中法是一种合适的构造散列函数的方法。具体做法为：将关键字进行平方运算，然后从结果的中间取出若干位（位数与散列地址的位数相同），作为散列地址。 TableSize=97，t=2 345?3452?119025?90 2.散列函数 6.乘余取整法 将关键字乘上一个常数a（0a1），提取乘积的小数部分与整数n相乘，然后对结果向下取整，作为散列地址。其散列函数为： hash(key) = 其中：a * key % 1 表示取a * key 的小数部分。若散列地址有p位，就取n=2p。高纳德（Knuth）对常数a做过仔细的研究，认为可取任何值，但一般情况下取黄金分割（ -1）/2为最理想。 2.散列函数 7.基数转换法 首先将关键字看作为另一个数制上的数，然后把它转换成原来数制上的数，再按散列地址位数在其低位上取出数值，作为该结点的散列地址。例如，对于关键字值85624，首先把它看成是一个13进制的数85624（13），再把它转换成十进制的数，则 85624（13）= 8 * 134 + 5 * 133 + 6 * 132 + 2 * 13 + 4= 240517（10） 如果散列地址有三位，那么我们取517作为关键字为85624 的结点的散列地址。 2.散列函数 假设以地区名作关键字，地区名以汉语拼音的字符表示，可以取这样的散列函数 取关键字中第一个字母在字母表中的序号作为散列函数。BEIJING的散列数值为2 求关键字的第一个和最后一个字母在字母表中的序号之和，然后判别这个值，若比30（表长）大，