[电脑基础知识]第7章 有哪些信誉好的足球投注网站.ppt

6.5.2.哈希函数的构造方法 常用的哈希函数构造方法有： 1.除留余数法 2.直接定址法 3.数字分析法 4.折叠法 5.平方取中 函数设计目标:使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上，同时使计算过程尽可能简单以达到尽可能高的时间效率。 h(K) = K mod m 优点：计算简单，适用范围广 关键：选好哈希表长度m 技巧：哈希表长m取质数时效果最好,一般为一个4d+3的质数。 ①除留余数法 常见的冲突处理方法有： 一、闭散列（开放定址法） 二、开散列（链表法） 优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素； 缺点：容易产生“堆积” ，大大降低了查找效率。 1.线性探查法 6.5.3 处理冲突的闭散列方法 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 19 01 24 14 55 68 若采用线性探测再散列处理冲突 11 82 36 1 1 1 1 3 6 2 5 1 例如: 关键字集合 { 19, 01, 24, 14, 55, 68, 11, 82, 36 } 8 1 2 3 0 2 0 5 3 2.平方（二次）探查法 平方探查法的探查跨步很大，所以可避免出现堆积问题 若采用二次探测再散列处理冲突: 19 01 24 14 68 55 11 82 36 1 1 1 1 2 1 4 1 3 { 19, 01, 24, 14, 55, 68, 11, 82, 36 } 8 1 2 3 0 2 0 5 3 (若di0，则加m) 二次探测再散列处理冲突 练习：设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】A.8 B.3 C.5 D.9 计算步骤如下:15，38，61，84用哈希函数H(key)=key%11计算后得地址:4,5,6,749计算后为5,发生冲突,用二次探测再散列法解决冲突: 1:(key+1^2)%14=(49+1)%14=8,不再发生冲突.得出结果为A 练习：设一个含13个元素的Hash表（0~12），Hash函数是H（key）=key%13，其中%是求余运算。用二次探查法解决冲突，则对于序列（8、31、20、33、18、53、27），则下列说法正确的是（? ）。 A.27在1号格子中；? B.33在6号格子中；? C.31在5号格子中； D.20在7号格子中； E.18在4号格子中 （8、31、20、33、18、53、27） 8 5 7 7 5 1 1 8 31 20 33 18 53 27 平均查找长度： 1 2 3 1 3 1 1 12/7=1.7 6.5.4 处理冲突的开散列（链地址）方法 基本思想：如果没有发生哈希冲突，则直接存放该数据元素；如果发生了哈希冲突，则把发生哈希冲突的数据元素另外存放在单链表中。 例:建立数据元素集合a的哈希表。a = {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77, 66, 55}。要求哈希函数采用除留余数法，解决冲突方法采用链表法。 分析：数据元素集合a中共有13个数据元素，取哈希表的内存单元个数m=13。除留余数法的哈希函数为：h(K) = K mod m有： {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77, 66, 55} 3 9 8 4 2 12 7 5 3 10 12 1 3 {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77, 66, 55} 3 9 8 4 2 12 7 5 3 10 12 1 3 如下图所示: link data 下标 0 66 1 54 2 16 3 43 4 3