etc卡的正确插法图,etc卡的正确插法图片芯片方向

首页 > 经验 > 作者:YD1662022-11-03 05:45:02

集合有两个大接口:Collection 和 Map,本文重点来讲解集合中另一个常用的集合类型 Map。

以下是 Map 的继承关系图:

etc卡的正确插法图,etc卡的正确插法图片芯片方向(1)

Map 简介

Map 常用的实现类如下:

Map 常用方法

常用方法包括:put、remove、get、size 等,所有方法如下图:

etc卡的正确插法图,etc卡的正确插法图片芯片方向(2)

使用示例,请参考以下代码:

MaphashMap=newHashMap(); //增加元素 hashMap.put("name","老王"); hashMap.put("age","30"); hashMap.put("sex","你猜"); //删除元素 hashMap.remove("age"); //查找单个元素 System.out.println(hashMap.get("age")); //循环所有的key for(Objectk:hashMap.keySet()){ System.out.println(k); } //循环所有的值 for(Objectv:hashMap.values()){ System.out.println(v); }

以上为 HashMap 的使用示例,其他类的使用也是类似。

HashMap 数据结构

HashMap 底层的数据是数组被成为哈希桶,每个桶存放的是链表,链表中的每个节点,就是 HashMap 中的每个元素。在 JDK 8 当链表长度大于等于 8 时,就会转成红黑树的数据结构,以提升查询和插入的效率。

HashMap 数据结构,如下图:

etc卡的正确插法图,etc卡的正确插法图片芯片方向(3)

HashMap 重要方法

1)添加方法:put(Object key, Object value)

执行流程如下:

源码及说明:

publicVput(Kkey,Vvalue){ //对key进行hash() returnputVal(hash(key),key,value,false,true); } staticfinalinthash(Objectkey){ inth; //对key进行hash()的具体实现 return(key==null)?0:(h=key.hashCode())^(h›››16); } finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent, booleanevict){ Node‹K,V›[]tab;Node‹K,V›p;intn,i; //tab为空则创建 if((tab=table)==null||(n=tab.length)==0) n=(tab=resize()).length; //计算index,并对null做处理 if((p=tab[i=(n-1)&hash])==null) tab[i]=newNode(hash,key,value,null); else{ Node‹K,V›e;Kk; //节点存在 if(p.hash==hash&& ((k=p.key)==key||(key!=null&&key.equals(k)))) e=p; //该链为树 elseif(pinstanceofTreeNode) e=((TreeNode‹K,V›)p).putTreeVal(this,tab,hash,key,value); //该链为链表 else{ for(intbinCount=0;; binCount){ if((e=p.next)==null){ p.next=newNode(hash,key,value,null); if(binCount›=TREEIFY_THRESHOLD-1)//-1for1st treeifyBin(tab,hash); break; } if(e.hash==hash&& ((k=e.key)==key||(key!=null&&key.equals(k)))) break; p=e; } } //写入 if(e!=null){//existingmappingforkey VoldValue=e.value; if(!onlyIfAbsent||oldValue==null) e.value=value; afterNodeAccess(e); returnoldValue; } } modCount; //超过loadfactor*currentcapacity,resize if( size›threshold) resize(); afterNodeInsertion(evict); returnnull; }

put() 执行流程图如下:

etc卡的正确插法图,etc卡的正确插法图片芯片方向(4)

2)获取方法:get(Object key)

执行流程如下:

源码及说明:

publicVget(Objectkey){ Node‹K,V›e; return(e=getNode(hash(key),key))==null?null:e.value; } /** *该方法是Map.get方法的具体实现 *接收两个参数 *@paramhashkey的hash值,根据hash值在节点数组中寻址,该hash值是通过hash(key)得到的 *@paramkeykey对象,当存在hash碰撞时,要逐个比对是否相等 *@return查找到则返回键值对节点对象,否则返回null */ finalNode‹K,V›getNode(inthash,Objectkey){ Node‹K,V›[]tab;Node‹K,V›first,e;intn;Kk;//声明节点数组对象、链表的第一个节点对象、循环遍历时的当前节点对象、数组长度、节点的键对象 //节点数组赋值、数组长度赋值、通过位运算得到求模结果确定链表的首节点 if((tab=table)!=null&&(n=tab.length)›0&& (first=tab[(n-1)&hash])!=null){ if(first.hash==hash&&//首先比对首节点,如果首节点的hash值和key的hash值相同,并且首节点的键对象和key相同(地址相同或equals相等),则返回该节点 ((k=first.key)==key||(key!=null&&key.equals(k)))) returnfirst;//返回首节点 //如果首节点比对不相同、那么看看是否存在下一个节点,如果存在的话,可以继续比对,如果不存在就意味着key没有匹配的键值对 if((e=first.next)!=null){ //如果存在下一个节点e,那么先看看这个首节点是否是个树节点 if(firstinstanceofTreeNode) //如果是首节点是树节点,那么遍历树来查找 return((TreeNode‹K,V›)first).getTreeNode(hash,key); //如果首节点不是树节点,就说明还是个普通的链表,那么逐个遍历比对即可 do{ if(e.hash==hash&& ((k=e.key)==key||(key!=null&&key.equals(k))))//比对时还是先看hash值是否相同、再看地址或equals returne;//如果当前节点e的键对象和key相同,那么返回e }while((e=e.next)!=null);//看看是否还有下一个节点,如果有,继续下一轮比对,否则跳出循环 } } returnnull;//在比对完了应该比对的树节点或者全部的链表节点都没能匹配到key,那么就返回null

相关面试题

1.Map 常见实现类有哪些?

答:Map 的常见实现类如下列表:

2.使用 HashMap 可能会遇到什么问题?如何避免?

答:HashMap 在并发场景中可能出现死循环的问题,这是因为 HashMap 在扩容的时候会对链表进行一次倒序处理,假设两个线程同时执行扩容操作,第一个线程正在执行 B→A 的时候,第二个线程又执行了 A→B ,这个时候就会出现 B→A→B 的问题,造成死循环。解决的方法:升级 JDK 版本,在 JDK 8 之后扩容不会再进行倒序,因此死循环的问题得到了极大的改善,但这不是终极的方案,因为 HashMap 本来就不是用在多线程版本下的,如果是多线程可使用 ConcurrentHashMap 替代 HashMap。

3.以下说法正确的是?

A:Hashtable 和 HashMap 都是非线程安全的B:ConcurrentHashMap 允许 null 作为 keyC:HashMap 允许 null 作为 keyD:Hashtable 允许 null 作为 key答:C题目解析:Hashtable 是线程安全的,ConcurrentHashMap 和 Hashtable 是不允许 null 作为键和值的。

4.TreeMap 怎么实现根据 value 值倒序?

答:使用 Collections.sort(list, new Comparator‹Map.Entry‹String, String››() 自定义比较器实现,先把 TreeMap 转换为 ArrayList,在使用 Collections.sort() 根据 value 进行倒序,完整的实现代码如下。

TreeMap‹String,String›treeMap=newTreeMap(); treeMap.put("dog","dog"); treeMap.put("camel","camel"); treeMap.put("cat","cat"); treeMap.put("ant","ant"); //map.entrySet()转成List List‹Map.Entry‹String,String››list=newArrayList‹›(treeMap.entrySet()); //通过比较器实现比较排序 Collections.sort(list,newComparator‹Map.Entry‹String,String››(){ publicintcompare(Map.Entry‹String,String›m1,Map.Entry‹String,String›m2){ returnm2.getValue().compareTo(m1.getValue()); } }); //打印结果 for(Map.Entry‹String,String›item:list){ System.out.println(item.getKey() ":" item.getValue()); }

程序执行结果:

dog:dogcat:catcamel:camelant:ant

5.以下哪个 Set 实现了自动排序?

A:LinedHashSetB:HashSetC:TreeSetD:AbstractSet

答:C

6.以下程序运行的结果是什么?

Hashtablehashtable=newHashtable(); hashtable.put("table",null); System.out.println(hashtable.get("table"));

答:程序执行报错:java.lang.NullPointerException。Hashtable 不允许 null 键和值。

7.HashMap 有哪些重要的参数?用途分别是什么?

答:HashMap 有两个重要的参数:容量(Capacity)和负载因子(LoadFactor)。

8.HashMap 和 Hashtable 有什么区别?

答:HashMap 和 Hashtable 区别如下:

9.什么是哈希冲突?

答:当输入两个不同值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。

10.有哪些方法可以解决哈希冲突?

答:哈希冲突的常用解决方案有以下 4 种。

11.HashMap 使用哪种方法来解决哈希冲突(哈希碰撞)?

答:HashMap 使用链表和红黑树来解决哈希冲突,详见本文 put() 方法的执行过程。

12.HashMap 的扩容为什么是 2^n ?

答:这样做的目的是为了让散列更加均匀,从而减少哈希碰撞,以提供代码的执行效率。

13.有哈希冲突的情况下 HashMap 如何取值?

答:如果有哈希冲突,HashMap 会循环链表中的每项 key 进行 equals 对比,返回对应的元素。相关源码如下:

do{ if(e.hash==hash&& ((k=e.key)==key||(key!=null&&key.equals(k))))//比对时还是先看hash值是否相同、再看地址或equals returne;//如果当前节点e的键对象和key相同,那么返回e }while((e=e.next)!=null);//看看是否还有下一个节点,如果有,继续下一轮比对,否则跳出循环

14.以下程序会输出什么结果?

classPerson{ privateIntegerage; publicbooleanequals(Objecto){ if(o==null||!(oinstanceofPerson)){ returnfalse; }else{ returnthis.getAge().equals(((Person)o).getAge()); } } publicinthashCode(){ returnage.hashCode(); } publicPerson(intage){ this.age=age; } publicvoidsetAge(intage){ this.age=age; } publicIntegergetAge(){ returnage; } publicstaticvoidmain(String[]args){ HashMap‹Person,Integer›hashMap=newHashMap‹›(); Personperson=newPerson(18); hashMap.put(person,1); System.out.println(hashMap.get(newPerson(18))); } }

答:1题目解析:因为 Person 重写了 equals 和 hashCode 方法,所有 person 对象和 new Person(18) 的键值相同,所以结果就是 1。

15.为什么重写 equals() 时一定要重写 hashCode()?

答:因为 Java 规定,如果两个对象 equals 比较相等(结果为 true),那么调用 hashCode 也必须相等。如果重写了 equals() 但没有重写 hashCode(),就会与规定相违背,比如以下代码(故意注释掉 hashCode 方法):

classPerson{ privateIntegerage; publicbooleanequals(Objecto){ if(o==null||!(oinstanceofPerson)){ returnfalse; }else{ returnthis.getAge().equals(((Person)o).getAge()); } } //publicinthashCode(){ //returnage.hashCode(); //} publicPerson(intage){ this.age=age; } publicvoidsetAge(intage){ this.age=age; } publicIntegergetAge(){ returnage; } publicstaticvoidmain(String[]args){ Personp1=newPerson(18); Personp2=newPerson(18); System.out.println(p1.equals(p2)); System.out.println(p1.hashCode() ":" p2.hashCode()); } }

执行的结果:

true21685669:2133927002

如果重写 hashCode() 之后,执行的结果是:

true18:18

这样就符合了 Java 的规定,因此重写 equals() 时一定要重写 hashCode()。

16.HashMap 在 JDK 7 多线程中使用会导致什么问题?

答:HashMap 在 JDK 7 中会导致死循环的问题。因为在 JDK 7 中,多线程进行 HashMap 扩容时会导致链表的循环引用,这个时候使用 get() 获取元素时就会导致死循环,造成 CPU 100% 的情况。

17.HashMap 在 JDK 7 和 JDK 8 中有哪些不同?

答:HashMap 在 JDK 7 和 JDK 8 的主要区别如下。

总结

通过本文可以了解到:

HashMap 在 JDK 7 可能在扩容时会导致链表的循环引用而造成 CPU 100%,HashMap 在 JDK 8 时数据结构变更为:数组 链表 红黑树的存储方式,在没有冲突的情况下直接存放数组,有冲突,当链表长度小于 8 时,存放在单链表结构中,当链表长度大于 8 时,树化并存放至红黑树的数据结构中。

在公众号【架构师修炼】菜单中可自行获取专属架构视频资料,无套路分享,包括不限于 java架构、python系列、人工智能系列、架构系列,以及最新面试、小程序、大前端均无私奉献,你会感谢我的哈

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.