第六章 Map和Set文章目录第六章 Map和Set前言一、搜索树1.搜索树是什么2.查找3.插入4.删除5.性能分析二、搜索1.场景2.基本模型三、Map1.概念2.常见用法3.注意事项4.使用案例四、Set1.概念2.常见用法3.注意事项4.使用案例五、哈希表1.概念2.哈希冲突2.1概念2.2如何避免冲突1哈希函数2负载因子调节3. 解决哈希冲突3.1 闭散列3.2 开散列重要4. 性能分析总结前言好久不见啊今天让我为大家讲解数据结构中最受瞩目的一对搭档——Map和Set.这乍一听有些抽象别急让我为你慢慢解答~首先让我们了解一下搜索树这个概念~一、搜索树1.搜索树是什么二叉搜索树又称二叉排序树它或者是⼀棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树举例arr[]{5,3,8,1,0,9,4}2.查找首先检查key是否何根节点key相等相等返回节点。其次得益于搜索树的性质如果不相等只需要比较它与根节点的大小小就去左边大就去右边。如此循环下来就可以轻松找到想要的key节点~否则返回null。privateNoderootnull;//查找publicNodesearch(inta){Nodeterroot;while(ter!null){if(ter.keya){returnter;}elseif(ater.key){terter.rigth;}else{terter.left;}}returnnull;}3.插入如果树为空树即根 null直接插入。如果树不是空树按照查找逻辑确定插入位置插入新结点也就是不断比较大的上右边小的上左边直到为空插入。//插入publicbooleaninsert(inta){if(rootnull){rootnewNode(a);returntrue;}intwa0;//rigthintwe0;//leftNodeterroot;Nodeparentroot;while(ter!null){if(ter.keya){returnfalse;}elseif(ater.key){parentter;terter.rigth;wa1;we0;}else{parentter;terter.left;wa0;we1;}}NodedernewNode(a);if(wa1){parent.rigthder;}else{parent.leftder;}returntrue;}这里用wa,we来判断左右子树似乎有点麻烦了动动脑筋有没有更好的办法呢结尾公布4.删除先查找这个key拿到Node如果Nodenull返回false检查Node是否有左右孩子1Node.left ! nullNode.right ! nulla. 需要使用替换法进行删除即在它的右子树中寻找中序下的第⼀个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题2只有左孩子a. cur 是 root则 root cur.leftb. cur 不是 rootcur 是 parent.left则 parent.left cur.leftc. cur 不是 rootcur 是 parent.right则 parent.right cur.left3只有右孩子a. cur 是 root则 root cur.rightb. cur 不是 rootcur 是 parent.left则 parent.left cur.rightc. cur 不是 rootcur 是 parent.right则 parent.right cur.right3左右孩子都没有a.直接删//删除publicbooleanremove(inta){Nodeparentnull;Nodeterroot;while(ter!null){if(ter.keya){break;}elseif(ater.key){parentter;terter.rigth;}else{parentter;terter.left;}}if(ternull){returnfalse;}Nodecurter;while(cur!null){if(cur.rigth!nullcur.left!null){parentcur;curcur.rigth;}elseif(cur.left!null){parentcur;curcur.left;}elseif(cur.rigth!null){parentcur;curcur.rigth;}else{break;}}ter.keycur.key;if(parent.leftcur){parent.leftnull;}else{parent.rigthnull;}returntrue;}5.性能分析最优情况下二叉搜索树为完全二叉树其平均比较次数为 O(logN)最差情况下二叉搜索树退化为单支树其平均比较次数为N读到这里你已经打败了50%的人也许你还在疑惑这搜索树和Map,Set有什么关系现在让我来偷偷告诉你——搜索树是引擎Map/Set 是车型搜索树是底层数据结构Map/Set 是基于它或哈希表实现的容器接口。ok,现在让我们正式进入MapSet的学习二、搜索1.场景试想一下现在我们要做一个根据姓名查询考试成绩的系统你会怎么实现查询功能直接遍历时间复杂度为O(N)元素如果比较多效率会非常慢二分查找时间复杂度为,但搜索前必须要求序列是有序的而且我们可能在查找时进行一些插入和删除的操作即动态查找那上述两种方式就不太适合了本节介绍的Map和Set是⼀种适合动态查找的集合容器。2.基本模型⼀般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对所以模型会有两种纯 key 模型比如有⼀个英文词典快速查找⼀个单词是否在词典中。Key-Value 模型比如常见的英语字典里面除了能查找到单词还能在对应的词后面看见它四级考试中出现的次数。Map中存储的就是key-value的键值对Set中只存储了Key提前预告一下在下面的讲解中出现Tree这一坨东西的地方需要让传入的key元素可比较而Hash不用接下来的举例我会大量使用Tree结尾会单独讲到Hash三、Map1.概念Map是⼀个接口类该类没有继承自Collection该类中存储的是K,V结构的键值对并且K⼀定是唯一的不能重复。2.常见用法方法解释V get(Object key)返回key对应的 valueV getOrDefault(Object key,VdefaultValue)返回key 对应的valuekey不存在返回默认值V put(K key,V value)设置key对应的valueV remove(Object key)删除key对应的映射关系Set keySet()返回所有key的不重复集合Collection values()返回所有value 的可重复集合SetentrySet()返回所有的key-value映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value3.注意事项Map是⼀个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMapMap中存放键值对的Key是唯⼀的value是可以重复的在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常value可以为空。但是HashMap的key和value都可以为空。Map中的Key可以全部分离出来存储到Set中来进行访问(因为Key不能重复)。Map中的value可以全部分离出来存储在Collection的任何⼀个子集合中(value可能有重复)。Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进行重新插入4.使用案例//这里用Tree来举例结尾会单独讲到HashpublicclassTreeMap{publicstaticvoidmain(String[]args){MapString,IntegerternewTreeMap();ter.put(你好,4);ter.put(我很好,9);ter.put(它好吗,14);//会得到对应的valueSystem.out.println(ter.get(你好));//不存在返回nullSystem.out.println(ter.get(我不好));//看key存不存在存在返回原本原本的value不存在返回我输入的默认值也就是第二个参数System.out.println(ter.getOrDefault(它好吗,0));System.out.println(ter.getOrDefault(我不好,7));//如果有过相同的key则对应的value会替换掉旧的value//value可以等于null,但是key不可以ter.put(我很好,56);System.out.println(ter.get(我很好));//移除对应的value会变成nullter.remove(你好);System.out.println(ter.get(你好));//打印所有的key,不会有重复的for(Stringa:ter.keySet()){System.out.println(a);}//打印所有value可以有重复的如果里面存在null,这里会报错for(inta:ter.values()){System.out.println(a);}//返回所有映射关系for(Map.EntryString,Integera:ter.entrySet()){System.out.println(a.getKey()--a.getValue());}//是否包含keySystem.out.println(ter.containsKey(它好吗));System.out.println(ter.containsValue(23));//打印当前ter里面的东西和组数System.out.println(ter);System.out.println(ter.size());}四、Set1.概念Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。2.常见用法方法解释V get(Object key)返回key对应的 valueV getOrDefault(Object key,VdefaultValue)返回key 对应的valuekey不存在返回默认值V put(K key,V value)设置key对应的valueV remove(Object key)删除key对应的映射关系Set keySet()返回所有key的不重复集合Collection values()返回所有value 的可重复集合SetentrySet()返回所有的key-value映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value3.注意事项Set是继承自Collection的⼀个接口类Set中只存储了key并且要求key一定要唯一TreeSet的底层是使用Map来实现的其使用key与Object的⼀个默认对象作为键值对插入到Map中的Set最大的功能就是对集合中的元素进行去重实现Set接口的常用类有TreeSet和HashSet还有⼀个LinkedHashSetLinkedHashSet是在HashSet的基础上维护了⼀个双向链表来记录元素的插入次序。Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入TreeSet中不能插入null的keyHashSet可以。4.使用案例publicstaticvoidmain(String[]args){SetStringternewTreeSet();//添加元素ter.add(你瞅啥);ter.add(瞅你咋地);ter.add(在干嘛);//添加成功返回true失败也就是是重复元素的时候返回falseSystem.out.println(ter.add(打电话));System.out.println(ter.add(你瞅啥));//判断原宿是否在集合中System.out.println(ter.contains(你瞅啥));System.out.println(------);//迭代器for(IteratorStringitter.iterator();it.hasNext();){Stringait.next();System.out.println(a);}//删除成功返回trueSystem.out.println(ter.remove(你瞅啥));//返回原宿个数System.out.println(ter.size());//看集合中的元素set里都存不存在都存在返回trueLinkedListStringarrnewLinkedList();arr.add(打电话);arr.add(在干嘛);System.out.println(ter.containsAll(arr));//Arrays里面有个.asList数组变列表试试//LinkedListStringcrrnewLinkedList();crr.add(打电话);crr.add(在上学);System.out.println(ter.addAll(crr));//将元素转换为数组返回Object[]errter.toArray();System.out.println(Arrays.toString(err));//清空ter.clear();//判断是否为空,为空返回trueSystem.out.println(ter.isEmpty());}五、哈希表1.概念在以往查找元素的过程中必须要经过关键码的多次比较需要耗费一定时间。那有没有一种理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素有的^ ^如果构造⼀种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一映射的关系那么在查找时通过该函数可以很快找到该元素现在让我们模拟创建一下向该结构中插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)举例arr{ 59 367}哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。排序后那么会不会有数字对应在同一个位置的时候呢2.哈希冲突2.1概念结合上面这张图假设数组arr{59327}那么当7遇到2的时候该怎么做这就是哈希冲突即不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。我们把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。2.2如何避免冲突1哈希函数引起哈希冲突的⼀个原因可能是哈希函数设计不够合理。那么如何设计呢哈希函数设计原则哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间就是函数计算完的地址数值必须在0~m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单常见哈希函数直接定制法(常用)取关键字的某个线性函数为散列地址HashKey A*Key B优点简单、均匀缺点需要事先知道关键字的分布情况使用场景适合查找比较小且连续的情况比如数组里有1100999这跨度就比较大了散列表开的比较大空间浪费除留余数法(常用)设散列表中允许的地址数为m取⼀个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突2负载因子调节散列表的载荷因子定义为α填入表中的元素个数/散列表的长度从图中就可以看出随着负载因子的增长冲突率不断升高所以当冲突率达到⼀个无法忍受的程度时我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的那我们能调整的就只有哈希表中的数组的大小。Java中当负载因子到达阈值0.75的时候就会扩容散列表了3. 解决哈希冲突解决哈希冲突两种常见方法是闭散列和开散列3.1 闭散列闭散列也叫开放地址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下⼀个” 空位置中去。可如何寻找下⼀个空位置呢线性探测结合图片当该放入44时通过函数得到的位置已经放了值为4的元素即发生哈希冲突。那么现在就需要线性探测从发生冲突的位置开始依次向后探测直到寻找到下⼀个空位置为止。插⼊◦ 通过哈希函数获取待插入元素在哈希表中的位置◦ 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素小问那么当我们采用闭散列处理哈希冲突时能不能直接删除元素呢答不能这会直接影响其他元素的搜索。比如删除元素4如果直接删除掉那么在查找44时该位置显示为空会直接判定没有44这个元素。因此线性探测采用标记的伪删除法来删除⼀个元素。二次探测线性探测的缺陷是产生冲突的数据堆积在一块(因为找空位置的方式就是挨着往后逐个去找)而二次探测为了避免该问题找下一个空位置的方法为H1 ( H0 i^2 ) % m, 或者 ( key - i^2 ) % m其中i是产生冲突的次数 m是表的大小。举例依旧44总结优点• 不需要额外的数据结构如链表空间利用率高。• 实现相对简单。• 缓存性能好因为数据都存储在连续的内存空间中。• 不需要存储指针节省空间。缺点• 容易产生聚集现象尤其是线性探测。• 删除操作复杂需要特殊处理以保持查找链的完整性。• 装载因子不能太大否则性能会急剧下降。• 二次聚集对于二次探测想不到吧有聚一块了~。3.2 开散列重要开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每⼀个子集合称为⼀个桶各个桶中的元素通过⼀个单链表链接起来各链表的头结点存储在哈希表中。代码演示publicclassHashBucket{publicstaticclassNode{intkey;Nodenext;intval;publicNode(intkey,intval){this.keykey;this.valval;}}Node[]arr;privatestaticfinaldoublefuzai0.75;intsize0;publicHashBucket(){arrnewNode[4];}//插入publicbooleanput(intkey,intval){intsitkey%arr.length;NodeternewNode(key,val);if(arr[sit]null){arr[sit]ter;}else{//没有重复if(repeat(key)){Nodetemarr[sit];while(tem.next!null){temtem.next;}tem.nextter;}else{//有重复returnfalse;}}size;if(figure()fuzai){resize();}returntrue;}//获取publicintget(intkey){intsitkey%arr.length;if(arr[sit]null){return-1;}else{Nodeterarr[sit];while(ter!null){if(ter.keykey){returnter.val;}else{terter.next;}}}return-1;}privatebooleanrepeat(intkey){intsitkey%arr.length;if(arr[key]null){returntrue;}else{Nodeterarr[key];while(ter!null){if(ter.keykey){returnfalse;}else{terter.next;}}}returntrue;}privatedoublefigure(){returnsize*1.0/arr.length;}//扩容privatevoidresize(){//这里要算新的哈希下标Node[]newarrnewNode[arr.length*2];for(inti0;iarr.length;i){Nodeterarr[i];while(ter!null){Nodenextter.next;ter.nextnull;intindexter.key%newarr.length;if(newarr[index]null){newarr[index]ter;}else{Nodecurnewarr[index];while(cur.next!null){curcur.next;}cur.nextter;}ternext;}}arrnewarr;}}4. 性能分析虽然哈希表总是和“冲突”这两字放在一起但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个数是可控的也就是每个桶中的链表的长度是⼀个常数所以通常意义下我们认为哈希表的插入/删除/查找时间复杂度是O(1)总结以上就是今天要讲的内容啦~ 除了对Map和Set的讲解还重点说了哈希表以及哈希冲突解决方法等等。那就祝大家好梦啦我们下期间~彩蛋公布直接将a与parent.key比较大了放右边小了方左边~