《2021Java面试题合集-Java集合面试题52道.pdf》由会员分享，可在线阅读，更多相关《2021Java面试题合集-Java集合面试题52道.pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、集合容器概述1.什么是集合 集合就是一个放数据的容器，准确的说是放数据对象引用的容器 集合类存放的都是对象的引用，而不是对象的本身 集合类型主要有3种：set（集）、list例 表）和m叩（映射）。2.集合的特点集合的特点主要有如下两点：。集合用于存储对象的容器，对象是用来封装数据，对象多了也需要存储集中式管理。和数组对比对象的大小不确定。因为集合是可变长度的。数组需要提前定义大小3.集合和数组的区别 数组是固定长度的；集合可变长度的。数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。4.使用集合框
2、架的好处1.容量自增长；2.提供了高性能的数据结构和算法，使编码更轻松，提高了程序速度和质量;3.可以方便地扩展或改写集合，提高代码复用性和可操作性。4.通过使用JDK自带的集合类，可以降低代码维护和学习新API成本。5.常用的集合类有哪些？Map接口和Collection接口是所有集合框架的父接口：1.Collection接口的子接口包括：Set接口和List接口2.Map接口的实现类主要有：HashMap、TreeMap、Hashtable.ConcurrentHashMap以及Properties 等3.Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet
3、等4.List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等6.List,Set,Map三者的区别?Vector数组结构，线程安全ListArrayListCollection单列集合有 序，可重直 数组结构，非线程安全LinkedList链表结构，非线程安全HashSet LinkedHashSet哈希表结构 哈希表和链表结构无 序，唯一TreeSet红黑树结构HashTable 门-人 Properties哈布表R构，去程文全HashMapLinkedHashMap哈希表结构，非线程安全 哈希表和链表结构TreeMap红黑树结构 Java容器分为
4、Collection和Map两大类，Collection集合的子接口有Set、List、Queue三种子接口。我们比较常用的是Set、List,M叩接口不是collection的子接口。Col lection集合主要有List和Set两大接口。List:一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有ArrayList、LinkedList和Vector。Set:一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set接口常用实现类是HashSet、Linked
5、HashSet以及TreeSet,Map是一个键值对集合，存储键、值和之间的映射。Key无序，唯一；value不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。o Map 的常用实现类：HashM叩、TreeMap、HashTable、LinkedHashMap.ConcurrentHashMap7.集合框架底层数据结构 Collection1.List Arra ylist:Object数组o Vector:Object数组o LinkedList:双向循环链表2.Set Ha shSet（无序，唯一）:基 于Ha
6、 shMa p实现的，底层采用Ha shMa p来保存元素o LinkedHa shSet:LinkedHa shSet 继承与 Ha shSet,并 且 其 内 部 过 LinkedHa shMa p 来实现的。有点类似于我们之前说的LinkedHa shM叩其内部是基于Ha shm叩实现一样，不过还是有一点点区别的。TreeSet（有序，唯一）：红黑树（自平衡的排序二叉树。）Ma p。Ha shM叩：JDK1.8之前Ha shM叩由数组+链表组成的，数组是Ha shM叩的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长
7、度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。LinkedHa shMa p:LinkedHa shMa p继承自Ha shM a p,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHa shMa p在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。Ha shTa ble:数组+链表组成的，数组是Ha shMa p的主体，链表则是主要为了解决哈希冲突而存在的。TreeM a p:红 黑 树（自平衡的排序二叉树）8.哪些集合类是线程安全的？Vector:就比Ar
8、ra ylist多了个synchronized（线程安全），因为效率较低，现在已经不太建议使用。ha shTa ble:就比ha shM叩多了个synchronized（线程安全），不建议使用。ConcurrentHa shM叩：是Ja va 5中支持高并发、高吞吐量的线程安全Ha shMa p实现。它由Segment数组结构和Ha shEntry数组结构组成。Segment数组在ConcurrentHa shM叩里扮演锁的角色，Ha shEntry则用于存储键-值对数据。一个ConcurrentHa shMa p里包含一个Segment数组，Segment的结构和Ha shM叩类似，是一种数
9、组和链表结构；一个Segment里包含一个Ha shEntry数组，每个Ha shEntry是一个链表结构的元素；每个Segment守护着一个Ha shEntry数组里的元素，当对Ha sh Entry数组的数据进行修改时，必须首先获得它对应的Segment锁。（推荐使用）9.Java集合的快速失败机制faiLfast”？是ja va集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fa il-fa st 机制。例如：假设存在两个线程（线程1、线程2）,线程1通过Itera tor在遍历集合A中的元素，在某个时候线程2修改了集合A的 结 构（是结构上面的修改，而不是
10、简单的修改集合元素的内容），那么这个时候程序就会抛出ConcurrentModifica tionException异常，从而产生fa il-fa st机制。原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值.每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。解决办法：1.在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。2.使用
11、CopyOnWriteArrayList 来替换ArrayList10.怎么确保一个集合不能被修改？可以使用Collections.unmodifiableCollection(Collection c)方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java.lang.UnsupportedOperationException 异常。示例代码如下：List lis t=new A rra y L is t();lis t.a ddCx)；Col 1ection c lis t=C o lle ctio n s,unm odifia bleCol 1e ctio n(1i s t);c
12、 lis t.a d d(y);/运行时此行报错System,o u t.p rin tln(lis t.s iz e();Collection 接口List 接口11.迭代器Iterator是什么？Iterator接口提供遍历任何Collection的接口。我们可以从f Collection中使用迭代器方法来获取迭代器实例。迭代器取代了 Java集合框架中的Enumeration,迭代器允许调用者在迭代过程中移除元素。因为所有Collection接继承了 Iterator迭代器p u b lic in te rfa ce C o lle ctio n extends Itera ble /Q
13、uery O pera tions12.Iterator怎么使用？有什么特点？Iterator使用代码如下：List lis t=new A rra y L is t();Ite ra to r i t =lis t.ite rato r();w h ile(it.h a sNe xt()S trin g obj=i t.n e x t();System,o u t.p rin tln(o b j);)Iterator的特点是只能单向遍历，但是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时4笑，就会抛出 ConcurrentModificationException 异常。13.如何
14、边遍历边移除Collection中的元素？边遍历边修改Collection的唯一正确方式是使用lterator.remove()方法，如下:lte ra to r i t =1i s t.ite rato r();w h ile(it.h a sNext()*/do somethi ng*it.re m o ve();)一种最常见的错误代码如下：fo r(ln te g e r i:lis t)lis t.re m o v e(i)运行以上错误代码会报Co n c u r r e n t M o d i f i c a t i o n E x c e p t i o n 异常。这是因为当使用f
15、oreach(for(lnteger i:list)语句时，会自动生成一个iterator来遍历该list,但同时该list正在被lterator.remove()修改。Java 一般不允许一线程在遍历Collection时另一 线程修改它。14.Iterator 和 Listiterator 有什么区别？Iterator可以遍历Set和List集合，而Listiterator只能遍历List。Iterator只能单向遍历，而Listiterator可以双向遍历(向前/后遍历)。Listiterator实现Iterator接口，然后添加了一些额外的功能，比如添加一个元素、替换一元素、获取前面或
16、后面元素的索引位置。15.遍历一介List有哪些不同的方式？每种方法的实现原理是什么？Java中 List遍历的最佳实践是什么？遍历方式有以下几种：1.for循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。2.迭代器遍历，Iterator。Iterator是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java在Collections中支持了 Iterator模式。3.foreach循环遍历。foreach内部也是采用了 Iterator的方式实现，使用时不需要显式声明Iterator或计数器。优点是代码简洁
17、，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。最佳实践：Java Collections框架中提供了一个RandomAccess接口，用来标记List实现是否支持 Random Access,。如果一个数据集合实现了该接口，就意味着它支持Random Access,按位置读取元素的平均时间复杂度为。，如ArrayList。如果没有实现该接口，表示不支持Random Access,如LinkedList。推荐的做法就是，支持Random Access的列表可用for循环遍历，否则建议用Iterator或foreach 遍历。16.说一下ArrayList的优缺
18、点 ArrayList的优点如下：。ArrayList底层以数组实现，是一种随机访问模式。ArrayList实现了 RandomAccess接口，因此查找的时候非常快。ArrayList在M序添加一个元素的时候非常方便。ArrayList的缺点如下：。删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。插入元素的时候，也需要做一次元素复制操作，缺点同上。ArrayList匕啜适合顺序添加、随机访问的场景。17.如何实现数组和List之间的转换？数组转List:使用Arrays.asList(array)进行转换。List转数组：使用List自带的toArrayO
19、方法。代码示例：/l i s t t o a r r a yL i s t l i s t =n e w A r r a y L i s t ();l i s t.a d d C l Z S 1);H s t.a d d(“45 6“)；l i s t.t o A r r a y O;/a r r a y t o l i s tS t r i n g a r r a y =n e w S t r i n g 123,45 6);A r r a y s.a s L i s t(a r r a y);18.ArrayList 和 LinkedList 的区别是什么？数据结构实现：ArrayList
20、是动态数组的数据结构实现，而LinkedList是双向链表的数据结构实现。随机访问效率：ArrayList比LinkedList在随机访问的时候效率要高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次直找。增加和删除效率：在非首尾的增加和删除操作，LinkedList要比ArrayList效率要高，因为ArrayList增删操作要影响数组内的其他数据的下标。内存空间占用：LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。线程安全：ArrayList和LinkedLi
21、st都是不同步的，也就是不保证线程安全；综合来说，在需要频繁读取集合中的元素时，更推荐使用ArrayList,而在插入和删除操作较多时，更推荐使用LinkedList.LinkedList的双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。19.ArrayList和 Vector的区别是什么？这两个类都实现了 List接 口（List接口继承了 Collection接口），他们都是有序集合。线程安全：Vector使用了 Synchronized来实现线程同步，是线程安全的
22、，而ArrayList是非线程安全的。性能：ArrayList在性能方面要优于Vector。扩容：ArrayList和Vector都会根据实际的需要动态的调整容量，只不过在Vector扩容每次会增加1倍，而ArrayList只会增加50%。Vector类的所有方法都是同步的.可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。20.插入数据时，ArrayList.LinkedList.Vector谁速度较快？阐述ArrayList、Vector、Li
23、nkedList 的存储性能和特性？ArrayList和Vector底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。Vector中的方法由于加了 synchronized修饰，因此Vector是线程安全容器，但性能上较ArrayList 差。LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList插入速度较快。21.多线程场景下如何使用ArrayList?ArrayLi
24、st不是线程安全的，如果遇到多线程场景，可以通过Collections的synchronizedList方法将其转换成线程安全的容器后再使用。例如像下面这样：List synchronizedList=Col1 e ction s.synchronizedList(1is t);synchronizedLi s t.a ddCa a a);synchronizedLi st.a d d(b b b);fo r(in t i=0;i synchronizedList.size();i+)System.o u t.p ri ntln(synch roni zedLi s t.g e t(i);)2
25、2.为什么 ArrayList 的 elementData 力 口 上 transient 修饰？ArrayList中的数组定义如下：private transient Object elementData;再看一下ArrayList的定义：pub lic cla ss Arra yList extends Abstra ctListimplements Li st,Ra ndomAccess,Clonea ble,j a va.i o.Se ri ali za ble可以看到ArrayList实现了 Serializable接口，这意味着ArrayList支持序列化。transient的作用
26、是说不希望elementData数组被序列化，重写了 writeObject实现：p riva te void w rite o b je ct(ja va.io.O bjectO utputstrea m s)throwsj a va.io.lO E xception*/w rite out element count,a nd a ny hidden s tu ff*in t expectedModCount=modCount;s.d efa ultw rite O b je ct();*/w rite out a rra y leng th*s.w rite ln t(e lem en
27、tD a ta.le n g th);*/w rite out all elements in the proper ord er.*fo r(in t i=0;i size;i+)s.w rite O b ject(e le m e ntD a ta i);i f (modCount!=expectedModCount)throw new C oncurrentM odifica tionE xception();)每次序列化时，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，然后遍历elementData,只序列化已存入的元素，这样既
28、加快了序列化的速度，又减小了序列化之后的文件大小。23.List和Set的区别 List,Set 都是继承自Collection 接口 List特点：一个有序(元素存入集合的顺序和取出的顺序一致)容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有ArrayList、LinkedList和Vector。Set特点：一个无序(存入和取出顺序有可能不一致)容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set接口常用实现类是HashSet、LinkedHashSet以及TreeSet.另 外List支持for循环，也就是通过下标来遍历，也可以用迭代器
29、，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。Set和List对比。Set:检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。List:和数组类似，List可以动态增长，杳找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变Set 接口24.说一下HashSet的实现原理？HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为present,因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，HashSet不允许重复
30、的值。25.HashSet如何检查重复？Hash Set是如何保证数据不可重复的？向HashSet中add()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles方法比较。HashSet中的add()方法会使用HashMap的put()方法。Hash Map的key是唯一的，由源码可以看出HashSet添加进去的值就是作为HashMap的key,并且在HashM叩中如果K/V相同时，会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复(HashMap比较key是否相等是先比较hashcode再比较equals)。以下是HashSet部分源码：p riva te s t
31、atic fin al O bject PRESEN T=new O b je ctO;p riva te tra n s ie n t Ha shMa p ma p;p u b lic Ha shSet()ma p=new Ha shMa p();)p u b lic boolea n a dd(E e)/调用Ha shMa p的p u t方法，PRESEN T是一个至始至终都相同的虚值re tu rn m a p.put(e,PRESEN T)=null;hashCode()与equals()的相关规定：1.如果两个对象相等，则hashcode一定也是相同的 hashCode是jdk根据对
32、象的地址或者字符串或者数字算出来的int类型的数值2.两个对象相等，对两个equals方法返回true3.两个对象有相同的hashcode值，它们也不一定是相等的4.综上，equals方法被覆盖过，则hashCode方法也必须被覆盖5.hashCode。的默认行为是对堆上的对象产生独特值。如果没有重写hashCode。，则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。=Vequals的区别1.=是判断两个变量或实例是不是指向同一个内存空间equals是判断两个变量或实例所指向的内存空间的值是不是相同2.=国旨对内存地址进行比较equals。是对字符串的内容进行比较2
33、6.HashSet与HashMap的区别HashMapHashSet实现了 M叩接口实现Set接口存储键值对仅存储对象调用put()向map中添加元素调用add()方法向Set中添加元素HashMap使用键(Key)计算HashcodeHashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals。方法用来判断对象的相等性，如果两个对象不同的话，那么返回falseHashM叩相对于HashSet较快，因为它是使用唯一的键获取对象HashSet较HashM叩来说比较慢Map 接口27.什么是Hash算法哈希算法是指把任意长度的二进制映射为固定长度的
34、较小的二进制值，这个较小的二进制值叫做哈希值。28.什么是链表链表是可以将物理地址上不连续的数据连接起来，通过指针来对物理地址进行操作，实现增删改查等功能。链表大致分为单链表和双向链表1.单链表:每个节点包含两部分，一部分存放数据变量的da ta,另一部分是指向下一节点的next指针单链表结构图2.双向链表:除了包含单链表的部分，还增加的pre前一个节点的指针链表的优点。插入删除速度快（因为有next指针指向其下一个节点，通过改变指针的指向可以方便的增加删除元素）。内存利用率高，不会浪费内存（可以使用内存中细小的不连续空间（大于node节点的大小），并且在需要空间的时候才创建空间）。大小没有固
35、定，拓展很灵活。链表的缺点。不能随机查找，必须从第一个开始遍历，查找效率低29.说一下HashMap的实现原理？Ha shM叩概述：Ha shM叩是基于哈希表的M叩接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。Ha shM叩的数据结构：在Ja va 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟 指 针（引用），所有的数据结构都可以用这两个基本结构来构造的，Ha shMa p也不例外。Ha shM叩实际上是一个“链表散列”的数据结构，即数组和链表的结合体。Ha shMa p基于Ha sh算法实
36、现的1.当我们往Ha shMa p中put元素时，利用key的ha shCode重新ha sh计算出当前对象的元素在数组中的下标2.存储时，如果出现ha sh值相同的k e y,此时有两种情况。（1）如果key相同，则覆盖原始值；（2）如果key不 同（出现冲突），则将当前的key-va lue放入链表中3.获取时，直接找到ha sh值对应的下标，在进一步判断key是否相同，从而找到对应值。4.理解了以上过程就不难明白Ha shM叩是如何解决ha sh冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。需要注意Jdk 1.8中对H
37、a shMa p的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的0（n）到O（logn）30.HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现在Ja va 中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。HashMapJDK1.8 之前JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。
38、若遇到哈希冲突，则将冲突的值加到链表中即可。ta ble数组锥表HashMapJDK1.8 之后相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。E ntryQ 数组JDK1.7 VSJDK1.8 比较 JDK1.8主要解决或优化了一下问题:1.resize扩容优化2.引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考3.解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。不同JDK1.7JDK 1.8存储结构数组+链表数组+链表+红黑树初始化方式单独函数：in fla
39、te T a b le()直接集成到了扩容函数re s iz e Q 中ha sh 值计算方式扰动处理=9次扰动=4次位运算+5次异或运算扰动处理=2次扰动=1次位运算+1次异或IE算存放数据的规则无冲突时，存放数组；冲突时，存放链表无冲突时，存放数组；冲突&链表长度8：存放单链表；冲突&链表长度8：树化并存放红黑树插入数据方式头 插 法（先讲原位置的数据移到后1位，再插入数据到该位置）尾 插 法（直接插入到链表尾部/红黑树）扩容后存储位置的计算方式全部按照原来方法进行计算（gpha shCode-扰动函数-（h&length-1）按照扩容后的规律计算（即扩容后的位置=原位置o r原位置+旧容
40、量）31.什么是红黑树说道红黑树先讲什么是二叉树二叉树简单来说就是每一个节上可以关联俩个子节点。大概就是这样子:红黑树 红黑树是一种特殊的二叉查找树。红黑树的每个结点上都有存储位表示结点的颜色，可以是红（Red）或黑（Bla ck）。三 红黑树的每个结点是黑色或者红色。当是不管怎么样他的根结点是黑色。每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色 注意：这里叶子结点，是指为空（N IL或N ULL）的叶子结点！.如果一个结点是红色的，则它的子结点必须是黑色的。每个结点到叶子结点N IL所经过的黑色结点的个数一样的。确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！
41、红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转和变色的目的是让树保持红黑树的特性。32.HashMap的put方法的具体流程？当我们put的时候，首 先 计 算key的ha sh值，这里调用了 ha sh方法，ha sh方法实际是让key.ha shcode()与key.ha shcode()16进行异或操作，高16bit补0,一个数和。异或不变，所 以ha s
42、h函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幕，计算下标index=(ta b le.le n g th -1)&h a s h,如果不做ha sh处理，相当于散列生效的只有几个低b it位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度。(lo g n)的树结构来提升碰撞下的性能。putVa l方法执行流程图p ublic V put(K key,V va lue)return putva l(ha sh(k
43、ey),key,va lue,fa ls e,tru e);)s ta tic fin a l in t ha sh(Object key)in t h;return(key=n u ll)?0:(h=key.ha shCodeO)A(h 16);/实现Ma p.put和相关方法fin a l V p u tva l(in t ha sh,K key,V va lue,boolea n onlylfA b sent,boolea n e vict)N ode ta b;N ode p;in t n,i;/步骤：ta b为空则创建/ta b le未初始化或者长度为0,进行扩容i f (ta b
44、=ta b le)=n u ll|(n=ta b.le ng th)=0)n=(ta b=re s iz e f).le n g th;/步骤：计算in d e x,并对n u ll做处理/(n-1)&h a sh确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)i f (p=ta b i=(n-1)&ha sh)=n u ll)ta b i=newN ode(ha sh,key,va lue,n u ll);/桶中己经存在元素else N ode e;K k;/步骤：节点key存在，直接覆盖va lue/比较桶中第一个元素(数组中的结点)的ha sh值相等，ke
45、y相等i f (p.ha sh=ha sh&(k=p.key)=key|(key!=n u ll&key.equa ls(k)/将第一个元素赋值给e,用e来记录e=p;/步骤：判断该链为红黑树/ha sh值不相等，即key不相等；为红黑树结点/如果当前元素类型为TreeNode,表示为红黑树，putTreeVa l返回待存放的node,e可能为n ullelse i f (p insta nceof TreeN ode)/放入树中e=(TreeNode)p).putTreeva l(this,ta b,ha sh,key,va lu e);/步骤：该链为链表/为链表结点else/在链表最末插入
46、结点fo r(in t bincount=0;+binCount)/到达链表的尾部/判断该链表尾部指针是不是空的i f (e=p.next)=n u ll)/在尾部插入新结点p.next=newN ode(ha sh,key,va lue,n u ll);/判断链表的长度是否达到转化红黑树的临界值，临界值为8i f (bincount=TREEIFY_THRESHOLD-1)/-1 fo r 1st/链表结构转树形结构tre e ifyB in(ta b,ha sh);/跳出循环brea k;/判断链表中结点的key值与插入的元素的key值是否相等i f (e.ha sh=ha sh&(k=e
47、.key)=key|(key!=n u ll&key.equa l/相等，跳出循环brea k;/用于遍历桶中的链表，与前面的e=p.next组合，可以遍历链表P=e;)/判断当前的key已经存在的情况下，再来一个相同的ha sh值、key值时，返回新来的va lue这个值i f (e!=n u ll)/记录R va lu ev oldva lue=e.va lue;/only工fAbsent为fa ls e或者旧值为n ulli f (!onlylfA b sent|oldva lue=n u ll)/用新值替换旧值e.va lue=va lue;/访问后回调a fterNodeAccess
48、(e);/返回旧值return oldva lue;/结构性修改+modcount;/步骤：超过最大容量就扩容/实际大小大于阈值则扩容i f (+size threshold)re siz e O;/插入后回调a fte rNo d e ln se rtio n(e vict);return n u ll;1.判断键值对数组ta ble。是否为空或为n u ll,否则执行resize。进行扩容；2.根据键值key计算ha sh值得到插入的数组索引i,如果ta blei=null,直接新建节点添加，转向如果ta ble。不为空，转向；3.判断ta bled的首个元素是否和key一样，如果相同直接
49、覆盖va lu e,否则转向，这里的相同指的是 ha shCode 以及 equa ls;4.判断ta ble。是否为tre eNod e,即ta ble。是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5;5.遍历tab le d,判断链表长度是否大于8,大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖va lue即可；6.插入成功后，判断实际存在的键值对数量size是否超多了最大容量th re sh o ld,如果超过，进行扩容。33.HashMap的扩容操作是怎么实现的？1.在jdk1.8中，resize方法
50、是在ha shm叩中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；2.每次扩展的时候，都是扩展2倍；3.扩展后N ode对象的位置要么在原位置，要么移动到原偏移量两倍的位置。在putVa l()中，我们看到在这个函数里面使用到了2次resize。方法，resize。方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Ha sh值，根据Ha sh值对其进行分发，但在1.8版本中，则是根据在同一个桶的位