数据基础教程19

9.4.1哈希表的基本概念9.4哈希表查找设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存单元。以每个元素的关键字ki（0≤i≤n-1）为自变量，通过一个哈希函数h把ki映射为内存单元的地址（或相对地址）h(ki)。并把该元素存储在这个内存单元中。哈希表1/54哈希函数h存储地址存储地址=h(key)n个对象个数m（m≥n）的连续内存单元2/54学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82学号姓名分数哈希地址2018001王华9002018010刘丽6292018006陈明5452018009张强9582018007许兵7662018012李萍88112018005李英824123710n=7m=12h(学号)=学号-2018001查找学号为2018010的学生分数：先计算h(2018010)=2018010-2018001=9。再取ha[9]元素的分数62即可。对应的查找时间为O(1)。哈希表ha3/54对于两个不同的关键字ki和kj（i≠j）出现h(ki)=h(kj)，这种现象称为哈希冲突。将具有不同关键字而具有相同哈希地址的元素称为“同义词”，这种冲突也称为同义词冲突。需要解决哈希冲突4/549.4.2哈希函数构造方法构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布的不同，有多种构造哈希函数的方法。

5/54以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。即h(k)=k+c。

这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可用直接定址法的哈希函数；否则，若关键字分布不连续将造成内存单元的大量浪费。1.直接定址法6/54学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82学号姓名分数哈希地址2018001王华9002018010刘丽6292018006陈明5452018009张强9582018007许兵7662018012李萍88112018005李英824123710n=7m=12h(学号)=学号-2018001哈希表ha7/54用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：h(k)=kmodp

(mod为求余运算，p≤m)p最好是质数（素数）。2.除留余数法8/54012⁞m-1哈希表hakh(k)=kmodpp≤m

保证地址有效p为质数

保证冲突尽可能小9/54提取关键字中取值较均匀的数字位作为哈希地址的方法。适合于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。3.数字分析法10/54位序123456789231760292326875927396289234363492706816927746389238126292394220哈希地址的集合为{2，75，28，34，16，38，62，20}11/549.4.3哈希冲突解决方法在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关：与装填因子有关。所谓装填因子α是指哈希表中已存入的元素数n与哈希地址空间大小m的比值，即α=n/m。α越小，冲突的可能性就越小；但α越小，存储空间的利用率就越低。与所采用的哈希函数有关。与解决冲突的哈希冲突函数有关。12/54解决哈希冲突方法有许多，可分为开放定址法和拉链法两大类。1.开放定址法发生冲突时查找周围一个空位置存放记录。设置一个查找周围一个空位置的函数。13/54从发生冲突的地址（设为d）开始，依次循环探测d的下一个地址（当到达下标为m-1的哈希表表尾时，下一个探测的地址是表首地址0），直到找到一个空闲单元为止。描述公式为：d0=h(k)，di=(di-1+1)modm

(1≤i≤m-1)（1）线性探测法0123456789********14/54问题：可能出现堆积现象：0123456789101112n=6,m=10,关键字为（10,11,12,19,20,21）哈希函数：h(key)=key%910，11，1219

h(19)=19%9=1（冲突）d0=1，d1=(1+1)%10=2（冲突）d2=(2+1)%10=3（冲突）d3=(3+1)%10=4（将19放在4位置）01234567891011121920

h(20)=20%9=2（冲突）d0=2，d1=(2+1)%10=3（冲突）d2=(3+1)%10=4（冲突）d3=(4+1)%10=5（将20放在5位置）哈希函数值不相同的多个记录争夺同一个后继哈希地址称为非同义词冲突15/54发生冲突时前后查找空位置。描述公式为：d0=h(k)，

di=(d0±i2)modm(1≤i≤m-1)0123456789********（2）平方探测法16/54平方探测法可以避免出现堆积问题。缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。17/54

【例9.18】假设哈希表ha长度m=13，采用除留余数法和线性探测法解决冲突建立关键字集合{16，74，60，43，54，90，46，31，29，88，77}的哈希表。

n=11，m=13，除留余数法的哈希函数为：

h(k)=kmodp

p应为小于等于m的素数，假设p取值13。18/54哈希函数：h(k)=kmod13解决冲突方法：线性探测法h(16)=3 ha[3]=16,共1次探测h(74)=9 ha[9]=74,共1次探测h(60)=8 ha[8]=60,共1次探测h(43)=4 ha[4]=43,共1次探测h(54)=2 ha[2]=54,共1次探测h(90)=12 ha[12]=90,共1次探测h(46)=7 ha[7]=46,共1次探测h(31)=5 ha[5]=31,共1次探测19/54h(29)=3 有冲突

d0=3，d1=(3+1)%13=4 仍有冲突

d2=(4+1)%13=5 仍有冲突

d3=(5+1)%13=6 ha[6]=29,共4次探测h(88)=10 ha[10]=88,共1次探测h(77)=12 有冲突

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次探测下标0123456789101112k7754164331294660748890探测次数21111411111哈希表ha[0..12]20/542.拉链法拉链法是把所有的同义词用单链表链接起来的方法。哈希函数为h(k)=k%m（哈希空间为0～m-1）。21/54i哈希表地址空间kx的元素ky的元素…h(kx)=h(ky)=…=ijks的元素kt的元素…h(ks)=h(kt)=…=j┇┇…0┇…m-1┇┇┇22/54

【例9.19】假设哈希表长度m=13，采用除留余数法和拉链法解决冲突建立关键字集合{16，74，60，43，54，90，46，31，29，88，77}的哈希表。23/54h(16)=3h(74)=9h(60)=8h(43)=4h(54)=2h(90)=12h(46)=7h(31)=5h(29)=3h(88)=10h(77)=12

n=11，m=13，除留余数法的哈希函数为h(k)=kmodm，当出现哈希冲突时采用拉链法解决冲突。h(54)=2h(16)=3h(29)=3h(43)=4h(31)=5h(46)=7h(74)=9h(60)=8h(88)=10h(90)=12h(77)=1224/54采用拉链法解决冲突建立的链表如下图所示。23∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧25/54开放地址法和拉链法哈希表的不同23∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧存放的不再是元素本身下标0123456789101112k7754164331294660748890探测次数21111411111h(k)=k%p存放的是元素本身h(k)=k%m由于单链表中可插入任意多个结点，所以此时装填因子α根据同义词的多少既可以设定为大于1，也可以设定为小于或等于1，通常取α=1。α=0.6～0.926/549.4.4哈希表查找及性能分析1.采用开放定址法建立的哈希表的查找

假设有元素类型为HashNode的哈希表ha[0..m-1]，哈希函数为h(k)=k%p，采用开放定址法中的线性探测法解决冲突，哈希表中空元素的关键字为常量NULLKEY。intSearchHT(HashNode[]ha,intp,intm,intk){//在哈希表ha中查找关键字kintd;d=k%p; //求哈希函数值while(ha[d].key!=NULLKEY&&ha[d].key!=k)d=(d+1)%m; //找到的位置不空闲if(ha[d].key==k) //查找成功返回ha的序号returnd;else //查找失败返回-1return-1;}27/54下标0123456789101112k7754164331294660748890探测次数21111411111ASLsucc=9×1+1×2+4×111=1.364成功的查找：在ha中找到对应的关键字h(77)=12 ha[12]=90≠77

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次比较比较的次数=探测次数示例28/54下标0123456789101112k7754164331294660748890哈希表ha[0..12]不成功的查找：在ha中找不到对应的关键字xh(x)=12 ha[12]≠x

d0=12，d1=(12+1)%13=0 ha[0]≠x

d2=(0+1)%13=1 ha[1]为空，表示查找失败，共3次比较确定查找失败，一定有比较到空为止！29/54哈希表ha中查找失败的所有情况的探测次数ASLunsucc=2+1+10+9+8+7+6+5+4+3+2+1+313=4.692下标0123456789101112k7754164331294660748890探测次数2110987654321330/54

【例9.20】

将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key×3)mod7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。（1）请画出所构造的散列表。（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。

说明：本题为2010年全国考研题。31/54（1）n=7，α=0.7=n/m，则m=n/0.7=10。计算各关键字存储地址的过程如下：

H(7)=7×3mod7=0

H(8)=8×3mod7=3

H(30)=30×3mod7=6

H(11)=11×3mod7=5

H(18)=18×3mod7=5 冲突

d1=(5+1)mod10=6 仍冲突

d2=(6+1)mod10=7

H(9)=9×3mod7=6 冲突

d1=(6+1)mod10=7 仍冲突

d2=(7+1)mod10=8

H(14)=14×3mod7=0 冲突

d1=(0+1)mod10=132/54构造的哈希表：下标0123456789关键字71481130189探测次数1211133（2）在等概率情况下：ASL成功=(1+2+1+1+1+3+3)/7=12/7=1.7133/54不成功的情况下所有探测次数：下标0123456789关键字71481130189探测次数3212154---所以有：ASL不成功=(3+2+1+2+1+5+4)/7=18/7=2.5734/54平均情况下的平均查找长度：解决冲突的方法平均查找长度ASL成功的查找不成功的查找线性探测法平方探测法拉链法n个关键字的构造顺序不同得到的哈希表不同平均查找长度ASL也不同考虑所有顺序构造哈希表的平均情况一般情况的ASL35/542.采用拉链法建立的哈希表的查找

假设哈希表元素类型为HNode的哈希表，单链表结点类型为SNode，哈希函数为h(k)=k%m，采用拉链法解决冲突。SNodeSearchHT(HNode[]ha,intm,intk){//在哈希表中查找关键字kintd;SNodep;d=k%m;p=ha[d].next; //p指向ha[d]单链表的首结点while(p!=null&&p.key!=k) //在ha[d]的单链表中查找p=p.next;if(p==null) //查找失败返回nullreturnnull;else //查找成功返回对应的结点returnp;}36/5423∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧成功的查找：在ha中找到对应的关键字ASLsucc=1×9+2×211=1.18h(77)=12，在ha[12]的单链表中共1次比较比较次数=对应结点在单链表中的序号（从1开始）示例37/5423∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧ASLunsucc=7×1+2×213=0.846h(x)=3，在ha[3]的单链表中共2次比较比较的次数=对应单链表中的结点个数不成功的查找：在ha中找不到对应的关键字x=α38/54平均情况下的平均查找长度：解决冲突的方法平均查找长度ASL成功的查找不成功的查找线性探测法平方探测法拉链法n个关键字的构造顺序不同得到的哈希表不同平均查找长度ASL也不同考虑所有顺序构造哈希表的平均情况一般情况的ASL39/549.4.5*Java中的HashMap和HashSet集合HashMap集合中的元素是<key，value>键值映射关系。HashSet集合中的元素是关键字，两者中的关键字不重复（主要讨论）HashMap集合。40/54HashMap采用数组+链表+红黑树的数据结构。数组(位桶)h(k1)key1,value1h(k2)key2,value2h(k3)key3,value3h(k4)key4,value4h(k5)key5,value5h(k6)key6,value6key11,value11key12,value12key61,value61key63,value63key64,value64key67,value67key62,value62key65,value65key66,value66红黑树（超过8个）链表key68,value68key69,value69一个Map.Entry41/54HashMap的主要构造方法HashMap(int

initialCapacity,float

loadFactor)：用指定的初始大小和装填因子构造一个空的HashMap。HashMap(int

initialCapacity)：用指定的初始大小和默认装填因子（0.75）构造一个空的HashMap。HashMap()：用指定的默认初始大小（16）和默认装填因子（0.75）构造一个空的HashMap。42/54HashMap的主要方法

（1）int

size()：返回HashMap中键值映射的个数。

（2）boolean

isEmpty()：若HashMap中没有任何键值映射时返回true。

（3）V

get(Object

key)：返回HashMap中指定键key对应的值，不存在key的键值映射时返回null。

（4）boolean

containsKey(Object

key)：若HashMap中包含指定键key的键值映射时返回true。

（5）V

put(K

key,V

value)：将键值映射<key，value>插入到HashMap中，如果之前存在该键key，用新value替换原来的值。43/54

（6）V

putIfAbsent(K

key,V

value)：如果当前HashMap

中指定键key尚未与值关联（或映射为null），则将key与给定值value关联并返回null（与执行put相同），否则返回当前值（不执行put）。例如，以下代码说明了put和putIfAbsent的差别：HashMap<String,String>map=newHashMap<>();map.put("a","A");map.put("b","B");Stringv=map.putIfAbsent("b","v"); //注意已存在关键字"b"的映射System.out.println(v); //输出BStringv1=map.putIfAbsent("c","v");//注意不存在关键字"c"的映射System.out.println(v1); //输出null44/54

（7）V

remove(Object

key)：在HashMap中删除指定键key的键值映射（若存在）。

（8）void

clear()：删除HashMap中的所有键值映射，变为空集。

（9）boolean

containsValue(Object

value)：若HashMap中存在指定值value的一个或者多个键，返回true。

（10）Set<K>

keySet()：返回HashMap中所有键的Set视图。该视图由HashMap支持，因此对视图的更改会反映到HashMap中，反之亦然。

（11）Collection<V>

values()：返回HashMap中所有值的Collection视图。

（12）Set<Map.Entry<K,V>>

entrySet()：返回HashMap中包含的映射关系的Set视图。

（13）V

getOrDefault(Object

key,V

defaultValue)：返回HashMap中指定键key关联的值，如果不存在key的映射，则返回defaultValue。

（14）boolean

remove(Object

key,Object

value)：仅当HashMap

中存在<key,value>键值映射时才删除它。45/54

（15）boolean

replace(K

key,V

oldValue,V

newValue)：若HashMap

中存在键key的关联值oldValue，用newValue替代它。

（16）V

replace(K

key,V

value)：若HashMap

中存在键key的关联某个值，用value替代它。

（17）V

compute(K

key,BiFunction<?superK,?superV,?extends>

remappingFunction)：返回更新后的该key映射的value值，若key没有映射的value值，则返回null。

（18）V

computeIfAbsent(K

key,Function<?superK,?extendsV>

mappingFunction)：如果HashMap

中指定键key尚未与值关联（或映射为null），则尝试使用给定的映射函数mappingFunction计算其值，并插入此映射（除非为null）。最常见的用法是构造一个新对象用作初始映射值或记忆结果，如puteIfAbsent(key,k->newValue(f(k)))。46/54HashMap元素遍历的方法与TreeMap类似。用for语句输出所有元素（映射）：HashMap<Integer,Integer>map;for(Map.Entry<Integer,Integer>entry1:map.entrySet())System.out.println("<"+entry1.getKey()+","+entry1.getValue()+">");47/54可以用以下for语句输出所有元素（映射）：HashMap<Integer,Stack<Integer>>map；for(Map.Entry<Integer,Stack<Integer>>entry2:map.entrySet()){System.out.print(entry2.getKey()+":");//输出关键字Stack<Integer>s=entry2.getValue();while(!s.empty()) //输出关键字对应的所有栈元素System.out.print(s.pop()+"");System.out.println();}48/54

【例9.21】给定一个仅由小写字母组成的字符串s，设计一个算法判断是否其中所有字母都唯一出现。staticbooleanunique(Strings){ //判断s中所有字母是否都唯一

HashMap<Character,Integer>map= newHashMap<Character,Integer>();for(inti=0;i<s.length();i++){charc=s.charAt(i);if(map.containsKey(c)) //字母c不唯一返回falsereturnfalse;else //字母c第一次出现，插入<c,1>map.put(c,1);}returntrue; //所有字母唯一返回true}49/54

【例9.22】给定一个abc.in文本文件，由若干行组成，每行为一个学生姓名和分数（用空格分隔），假设同一个学生的分数均不同，例如，abc.in文件如下：Mary90Smith86Mary85John78Mary92Smith88

编写一个程序，读取该文件数据，按姓名输出所有学生分数，姓名顺序不作要求，但每个学生的分数按递增顺序。并且将结果存放在abc.out文件中。例如，abc.in对应的abc.out文件如下：Smith:8688John:78Mary:85909250/54

采用