数据结构第9章查找4哈希表.pptx

武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2011年3月12日第第9 9章章 查找查找查找的基本概念静态查找表动态查找表哈希表v哈希表哈希表(Hash Tables)9.3 哈哈希表希表 也被称为散列表，是普通数组概念的推广。因为可以对数组进行直接寻址，故可以在O(1)时间内访问到数组的任意元素。v哈希表哈希表(Hash Tables)9.3 哈哈希表希表 当关键字全域比较小的时候，利用数组(直接寻址表)是一种简单有效的技术。v哈希表哈希表(Hash Tables)9.3 哈哈希表希表直接寻址技术存在的问题：如果全域U很大，在计算机中存储大小为|U|的一张表T就有点不实际，甚至是不可能的。实际的应用中，要存储的关键字集合K，相对U来说很小，因此分配给T的大部分空间会被浪费。v哈希表哈希表(Hash Tables)9.3 哈哈希表希表 给定关键字，期望通过计算，即利用哈希函数h(x)计算出关键字在表T中的位置。v哈希表哈希表(Hash Tables)9.3 哈哈希表希表 在直接寻址方式下，具有关键字k的数据元素，存放在槽k中。在哈希方式下，具有关键字k的数据元素，存放在槽h(k)中。其中h(x)是散列函数。碰撞(collision)Z Zhao,Q Qian,S Sun,L Li,WWu,C Chen,H Han,Y Ye,D Dai 例如：对于如下 9 个关键字：设哈希函数 f(key)=(Ord(关键字首字母)-Ord(A)+1)/2 问题:若添加关键字 Zhou，会出现什么情况？0 1 2 3 4 5 6 7 8 9 10 11 12 13 Dai Chen Zhao Qian Sun Li Wu Han Ye 从这个例子可见：1)哈希函数是一个映像，即：将关键字的集合映射到某个地址 集合上。它的设置很灵活，只要使得关键字的哈希函数值都 落在表长允许的范围之内即可；2)由于哈希函数是一个压缩映像，因此，在一般情况下，很容 易产生“冲突”现象，即：key1 key2，而 f(key1)=f(key2)。这种具有相同函数值的关键字称为同义词。Zhou Zhou Zhou 3)很难找到一个不产生冲突的哈希函数。一般情况下，只能 选择恰当的哈希函数，使冲突尽可能少地产生。因此：在构造这种特殊的“查找表”时，除了需要选择一个“好”的哈希函数(其原则是尽可能地使任意一组关键字的哈希地址均匀地分布在整个地址空间中，即用任意关键字作为哈希函数的自变量其计算结果随机分布，以尽可能少产生冲突)；还需要找到一种“处理冲突”的方法。v哈希表哈希表(Hash Tables)9.3 哈哈希表希表哈希表的定义 根据设定的哈希函数H(key)和所选中的处理冲突的方法建立的查找表。其基本思想是：以记录的关键字为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。这一映像过程称为哈希造表或散列。v哈希表哈希表(Hash Tables)9.3 哈哈希表希表 当对记录进行查找时，再根据给定的关键字，用同一个哈希函数计算出给定关键字对应的存储地址，随后进行访问。所以哈希表既是一种存储形式，又是一种查找方法，通常将这种查找方法称为哈希查找。v哈希哈希函数的构造方法函数的构造方法 9.3 哈哈希表希表对数字关键字可有下列构造方法：对非数字关键字，常用字符串哈希函数有1.直接定址法 3.平方取中法 5.除留余数法 4.折叠法 6.随机数法 2.数字分析法 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等v哈希哈希函数的构造方法函数的构造方法 9.3 哈哈希表希表v直接直接定址法定址法 9.3 哈哈希表希表 取关键字或关键字的某个线性函数值为散列地址，即哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b (其中a、b为常数)例：关键码集合为 100，300，500，700，800，900，选取哈希函数为 Hash(key)=key/100，画初存储结构(哈希表)0 1 2 3 4 5 6 7 8 9900800700500300100v直接直接定址法定址法 9.3 哈哈希表希表特点：地址集合的大小=关键字集合的大小。优点：以关键码 key 的某个线性函数值为哈希地址，不会产生冲突。缺点：要占用连续地址空间，空间效率低。实际中能使用这种哈希函数的情况很少v数字数字分析法分析法9.3 哈哈希表希表选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。v数字数字分析法分析法9.3 哈哈希表希表3 4 7 0 5 2 4 3 4 9 1 4 8 73 4 8 2 6 9 63 4 8 5 2 7 03 4 8 6 3 0 53 4 9 8 0 5 83 4 7 9 6 7 13 4 7 3 9 1 9例：有一组（例如80个）关键码，其样式如下：讨论：第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。v平方平方取中法（较常用）取中法（较常用）9.3 哈哈希表希表构造：以关键字的平方值的中间几位作为哈希地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中 间各位又能受到整个关键字中各位的影响。此方法适合于：关键字中的每一位都有某些数字重复出现频度很高的现象。例：2589的平方值为6702921，可以取中间的029为地址。v折叠折叠法法9.3 哈哈希表希表 构造：将关键字分割成位数相同的几部分，然后取这几部分 的叠加和（舍去进位）做哈希地址。移位叠加：将分割后的几部分低位对齐相加。间界叠加：从一端沿分割界来回折叠，然后对齐相加。适于关键字位数很多，且每一位上数字分布大致均匀情况v折叠折叠法法9.3 哈哈希表希表例：关键字为：0442205864，哈希地址位数为 4。5 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加例：元素42751896,移位法：42751896=1041 间界叠加法：427 518 96 724+518+69=1311v除除留余数留余数法法(最常用最常用)9.3 哈哈希表希表 构造：取关键字被某个不大于哈希表表长 m 的数 p 除后所得 余数作哈希地址，即 H(key)=key MOD p，p m。特点：简单，可与上述几种方法结合使用。p 的选取很重要；p 选得不好，容易产生同义词。p 应为不大于 m 的素数或不含 20 以下的质因子的合数。v除除留余数留余数法法(最常用最常用)9.3 哈哈希表希表331224391821012345678910给定一组关键字：12,39,18,24,33,21，若取 p=11,则他们对应的哈希函数值将为v除除留余数留余数法法(最常用最常用)9.3 哈哈希表希表181224012345678910给定一组关键字：12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为393321 可见，若 p 中含质因子 3，则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。v随机数随机数法法 9.3 哈哈希表希表构造：取关键字的随机函数值作哈希地址，即：H(key)=Random(key)其中，Random是伪随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当v哈希哈希函数的构造方法函数的构造方法 9.3 哈哈希表希表 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况（包括关键字的范围和形态），总的原则是使产生冲突的可能性降到尽可能地小。选取哈希函数，考虑以下因素：1）计算哈希函数所需时间 2）关键字长度 3）哈希表长度（哈希地址范围）4）关键字分布情况 5）记录的查找频率v处理处理冲突的方法冲突的方法 9.3 哈哈希表希表 “处理冲突”的实际含义是：为产生冲突的地址寻找另一个哈希地址。1.开放地址法 (1)线性探测法 (2)二次探测法 (3)伪随机探测法2.链地址法3.再哈希法4.建立一个公共溢出区v开放开放地址法地址法 9.3 哈哈希表希表(1)线性探测法 设散列函数H(K)=K mod m(m为表长)，若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为：Hi=(H(K)+di)mod m (di=1,2,m-1)v开放开放地址法地址法 9.3 哈哈希表希表例：关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；拟用线性探测法处理冲突。建哈希表：0 1 2 3 4 5 6 7 8 9 10477291116922283v开放开放地址法地址法 9.3 哈哈希表希表线性探测法的优点：只要哈希表未被填满，保证能找到一 个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第 i+1个哈希地址，这样本应存入第i+1个哈希地址的元素 变成了第i+2个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。可采用二次探测法或伪随机探测法，以改善“堆积”问题v开放开放地址法地址法 9.3 哈哈希表希表(2)二次探测法 二次探测法对应的探查地址序列的计算公式为：Hi=(H(K)+di)mod m 其中di=12,-12,22,-22,j2,-j2 (jm/2)。v开放开放地址法地址法 9.3 哈哈希表希表0 1 2 3 4 5 6 7 8 9 101122347 92 167298例：关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；拟用二次探测法处理冲突。建哈希表如下：Hi=(H(K)+di)mod m 其中di=12,-12,22,-22,j2,-j2 (jm/2)。v开放开放地址法地址法 9.3 哈哈希表希表(3)伪随机探测法 伪随机探测法对应的探查地址序列的计算公式为：Hi=(H(K)+di)mod m 其中di=伪随机序列例：表长为 11 的哈希表中已填有关键字为 17，60，29 的记录，H(key)=key MOD 11，现有第 4 个记录，其关键字为 38，按三种处理冲突的方法，将它填入表中。0 1 2 3 4 5 6 7 8 9 1060 17 29(1)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5+2)MOD 11=7 冲突 H3=(5+3)MOD 11=8 不冲突 38(2)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5-1)MOD 11=4 不冲突 38(3)H(38)=38 MOD 11=5 冲突 设伪随机数序列为 9，则：H1=(5+9)MOD 11=3 不冲突 38 v链链地址法地址法9.3 哈哈希表希表优点：插入、删除方便。缺点：占用存储空间多。基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13，用链地址法处理冲突。0 1 2 3 4 5 6 7 8 9 10 11 12 14 68 192023 11 1 55 8410 27 79 v再再哈希法哈希法9.3 哈哈希表希表Hi=RHi(key)RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。v溢出溢出区法区法 9.3 哈哈希表希表 除基本的存储区外(称为基本表)，另外建立一个公共溢出区(称为溢出表)，当发生冲突时，记录可以存入这个公共溢出区。v哈希表的应用哈希表的应用 9.3 哈哈希表希表“冲突”是不是特别讨厌？答：不一定！正因为有冲突，使得文件加密后无法破译（不可逆，是单向散列函数，可用于数字签名）。利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。v哈希表的应用哈希表的应用 9.3 哈哈希表希表 哈希(Hash)函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。v哈希表的应用哈希表的应用 9.3 哈哈希表希表1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函数具备以下的性质：2、给定输入数据，很容易计算出它的哈希值；3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的单向性，在技术上称为抗原像攻击性；4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，(这种情况称为碰撞，Collision)，这很难，计算上不可行，在技术上称为抗碰撞攻击性；5、哈希值不表达任何关于输入数据的信息。v哈希表的应用哈希表的应用 9.3 哈哈希表希表 Hash算法在信息安全方面的应用主要体现在以下的3个方面：(1)文件校验(2)数字签名(3)鉴权协议 v哈希表的应用哈希表的应用 9.3 哈哈希表希表(1)文件校验第一是文件传送后的校验，将得到的目标文件计算MD5值，与源文件的MD5值比对。这可以检验文件传输过程中是否出现错误，更重要的是可以保证文件在传输过程中未被恶意篡改。v哈希表的应用哈希表的应用 9.3 哈哈希表希表(1)文件校验第二是用作保存二进制文件系统的数字指纹，以便检测文件系统和数据库是否未经允许的被修改。因为散列校验和的长度很小，它们可以方便的被存放在容量很小的存储介质上。此后，可以定期或根据需要，再次计算文件系统的校验和，一旦发现与原来保存的值有不匹配，说明该文件已经被非法修改，或者是被病毒感染，或者被木马程序替代。v哈希表的应用哈希表的应用 9.3 哈哈希表希表(2)数字签名发信者在发信前使用哈希算法求出待发信息的数字摘要，然后用私钥对这个数字摘要，而不是待发信息本身，进行加密而形成一段信息，这段信息称为数字签名。发信时将这个数字签名信息附在待发信息后面，一起发送过去。收信者收到信息后，一方面用发信者的公钥对数字签名解密，得到一个摘要H；另一方面把收到的信息本身用哈希算法求出另一个摘要H，再把H和H相比较，看看两者是否相同。如果两个摘要H和H完全符合，证明信息是完整的；如果不符合，就说明信息被人篡改了。v哈希表的应用哈希表的应用 9.3 哈哈希表希表v哈希表的应用哈希表的应用 9.3 哈哈希表希表(3)鉴权协议 如下的鉴权协议又被称作“挑战-认证模式”：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。需 要鉴权的一方，向将被鉴权的一方发送随机串(“挑战”)，被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后，返还鉴权方，鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较(“认证”)，如相同，则可在统计上认为对方拥有该口令字，即通过鉴权。v哈希表的应用哈希表的应用 9.3 哈哈希表希表(3)鉴权协议 POP3协议中就有这一应用的典型例子：S:+OK POP3 server ready C:APOP mrose c4c9334bac560ecc979e58001b3e22fb S:+OK maildrop has 1 message(369 octets)在上面的一段POP3协议会话中，双方都共享的对称密钥(鉴权口令字)是tanstaaf，服务器发出的挑战是，客户端对挑战的应答是MD5(tanstaaf)=c4c9334bac560ecc979e58001b3e22fb，正确的应答使其通过了认证。v哈希哈希表的查找及其分析表的查找及其分析9.3 哈哈希表希表 散列表的目的主要是用于快速查找。在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。v哈希哈希表的查找及其分析表的查找及其分析9.3 哈哈希表希表例：设有一组关键字 19,01,23,14,55,20,84,27,68,11,10,77，采用哈希函数为：H(k)=k mod 13。采用开放地址的线性探测法解决冲突，试在018的散列地址空间中，对该关键字序列构造哈希表。解：依题意 m=19，得到线性探测法对应的探查地址序列计算公式为：di=(H(k)+j)mod 19;j=1,2,18H(19)=19 mod 13=6H(01)=01 mod 13=1H(23)=23 mod 13=10H(14)=14 mod 13=1(冲突)H(14)=(1+1)mod 19=2H(55)=55 mod 13=3H(20)=20 mod 13=7H(84)=84 mod 13=6(冲突)H(84)=(6+1)mod 19=7(冲突)H(84)=(6+2)mod 19=8H(27)=27 mod 13=1（冲突）H(27)=(1+1)mod 19=2(冲突)H(27)=(1+2)mod 19=3(冲突)H(27)=(1+3)mod 19=40123456789 10 11 12 13 14 15 16 17 1819 19,01,23,14,55,20,84,27,68,11,10,77 012314 5520 842777101168 v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表 哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表1.线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H(x)及装填因子的值和该处理方法有关。这时的成功的平均查找长度为：ASL=(1+1/(1-)/2v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表2.链地址法查找的性能分析 由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。平均查找长度：ASL=1+/2v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表例：给定关键字序列11,78,10,1,3,2,4,21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。哈希函数H(k)=k mod 11。v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表顺序查找的顺序表(一维数组)由图可得：顺序查找的成功平均查找长度为ASL=(1+2+3+4+5+6+7+8)/8=4.511,78,10,1,3,2,4,21117810132421012345678910v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表折半查找的判定树二分查找的成功平均查找长度为ASL=(1*1+2*2+3*4+4*1)/8=2.62511,78,10,1,3,2,4,21178210211143v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表11,78,10,1,3,2,4,21 二叉排序树 平衡二叉树111078123421311122147810ASL=(1+2*2+3*2+4+5*2)/8=3.125ASL=(1+2*2+3*3+4*2)/8=2.75v哈希哈希查找的性能分析查找的性能分析9.3 哈哈希表希表11,78,10,1,3,2,4,21线性探查法解决冲突的哈希表如图所示由图可得：线性探查法的成功平均查找长度为ASL=(1+1+2+1+3+2+8+1)/8=2.375117813242110012345678910链地址法解决冲突的哈希表如图所示v哈希哈希查找的性能查找的性能分析分析9.3 哈哈希表希表11,78,10,1,3,2,4,21链地址法成功平均查找长度为 ASL=(1*6+2*2)/8=1.25117813242110012345678910/哈希表的查找分析 查找过程和造表过程一致。假设采用开放定址处理冲突，则 查找过程为：给定 k 值计算 H(k)此地址为空关键字=k 查找失败查找成功按处理冲突 方法计算 Hi YNYN哈希查找分析：哈希查找过程仍是一个给定值 与关键字进行比较的过程；评价哈希查找效率仍要用ASL；决定哈希表查找的ASL的因素：1)选用的哈希函数；2)选用的处理冲突的方法；3)哈希表饱和的程度，装载因子 =n/m 值的大小（n 表中填入的 记录数，m 哈希表的长度）一般情况下，可以认为选用的哈希函数是“均匀”的（即：对于关键字集合中的任一关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的），则在讨论 ASL 时，可以不考虑它的因素。因此，哈希表的 ASL 是处理冲突方法和装载因子的函数。可以证明：查找成功时平均查找长度有下列结果：线性探测再散列：链地址法：随机探测再散列：哈希表的平均查 找长度是 的函数，而不是 n 的函数。这是哈希表所 特有的特点。本章小结本章小结1.掌握查找的基本概念；2.数量掌握静态查找表的查找算法思想并灵活应用；3.熟练掌握动态查找表的特点以及二叉排序树的各种操作思想，了解平衡二叉树的概念及插入和删除方法；4.熟练掌握哈希表的基本概念、哈希函数的构造方法和、解决冲突的方法，并能计算平均查找长度。武汉科技大学Wuhan University of Science and Technology