关于HashMap阿奋相信再面试的时候，很容易被问到，why？因为至少在JDK8出来之后，很容易被问到HashMap的知识点，而对于没有研究过他源码的同学来说，这可能只是其中的一部分，比如线程安全，链表+red还有blackTree，以及它的展开等等。今天阿芬就把面试中会问到的HashMap上的大部分内容总结一下。HashMap说到HashMap，想必大家脑子里直接复现了很多面试题。HashMapJDK7和JDK8HashMap的数据结构有什么区别？这个HashMap写了一道面试题。HashMap的数据结构HashMap的数据结构，面试官的问题，属于大的还是小的那种，大了就需要你把HashMap的所有内容都详细解释一遍，但是如果要说话不多说，介绍一下内部结构就够了。阿芬今天就来分析一下这个数据结构。HashMap中有几个重要的参数：//默认初始容量——必须是2的幂staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//当构造函数中没有指定加载因子时staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;//扩容阈值，等于CAPACITY*LOAD_FACTORstaticfinalintTREEIFY_THRESHOLD=8;//缩容阈值staticfinalintUNTREEIFY_THRESHOLD=6;//扩容的另一个参数staticfinalintMIN_TREEIFY_CAPACITY=64;我们已经看到了参数上面提到的内容，如果用通俗易懂的语言，如何描述这些参数呢？其实这就涉及到JDK8中HashMap的不同结构。我们也知道如果JDK8中的HashMap在水平方向上是一个数组，那么垂直方向上的每个元素就是一个单项链表，而这个链表会根据长度进行不合理的演化，而这个演化就是扩展为树结构和缩减为链表结构的键，这些键由这些参数定义。CAPACITY相当于HashMap中默认的初始容量。LOAD_FACTOR负载系数。TREEIFY_THRESHOLD树化的阈值，也就是说当表的节点中的链表长度超过这个阈值时，链表就会变成树。UNTREEIFY_THRESHOLD树被降级为链表的阈值（即当表的节点中树的长度低于该阈值时，树将变为链表）。MIN_TREEIFY_CAPACITY的另一个参数是当hashmap中的节点数大于这个值时，hashmap中的部分链表会变成树。transientNode[]tableHash表。有的朋友在面试的时候会说，当HashMap中的一个节点链表长度大于8时，HashMap中的链表就会变成一棵树。事实上，它不是。这也和MIN_TREEIFY_CAPACITY有关，也就是整个HashMap的节点数大于64，节点的链表长度大于8才能成为树。JDK7和JDK8有什么区别HashMapJDK7我们都知道，如果按照水平方向是一个数组，那么它的垂直方向上的每个元素都是一个单向链表，而在水平方向上，每个实体是等价的的Entry实例。每个Entry包含四个属性，keyvaluehash值用于单项列表的next，如下图：JDK7，所以JDK7的HashMap的数据结构是由数组+链表组成的。但是JDK8就不一样了，因为他们巧妙的在里面加了一棵红黑树，如下图所示：JDK8所以JDK8的HashMap的数据结构是由数组+链表+红黑树组成的。HashMap安全吗？说到这里，想必是一道很基础的面试题。我们都知道HashMap属于那种线程不安全的类。为什么不安全？不安全的时候会提到哪里？是不是仅仅说明它的内部不受synchronize关键字的控制？那么，说到HashMap的不安全性，就要从put和get方法说起。我们先看看内部实现。我们先看put方法，再分析put方法。publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;节点p;诠释n,我;//这里先哈希表初始化if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;//通过Hash值计算出在Hash表中的位置，并将该位置的元素赋值给P如果等于空则新建节点if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{节点e;Kk;//Hash表当前索引已经有一个元素，给这个元素添加一个链表if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);else{for(intbinCount=0;;++binCount){//新建接口，并追加到列表if((e=p.next)==null){p.next=newNode(hash,key,value,无效的）;if(binCount>=TREEIFY_THRESHOLD-1)//-1对于第一个treeifyBin(tab,hash);休息;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))中断；p=e;}}if(e!=null){//键VoldValue=e.value的现有映射；如果(!onlyIfAbsent||oldValue==null)e.value=value;节点访问后（e）；返回旧值；}}++模数；如果（++大小>阈值）调整大小（）；节点插入后（逐出）；返回空值；}看到源码后，我们猜猜会出现什么问题？比如此时有两个线程同时执行put，一个线程A执行put("1","A");一个线程B执行put("2","B");如果此时线程A和B都执行if((p=tab[i=(n-1)&hash])==null)但是，如果线程A执行tab[i]=newNode(hash,key,值，此时为空）；这时候里面就没有问题了，已经放进去了。这时候如果线程B执行tab[i]=newNode(hash,key,value,null);会导致线程A中的key为1元素A的丢失直接被线程B覆盖，这就是为什么有人说在JDK7中，扩容会导致环链或数据丢失，而在JDK8中，数据覆盖会发生。会出现null问题。这个问题，无论是JDK7还是JDK8，都有这个问题。如果面试的时候能从这个地方分析出来，至少这个线程是不安全的。你自己研究过，所以这个可以完美的解释HashMap的线程不安全。HashMap的扩展机制上面我们也列举了HashMap的一些关键参数。接下来我们分析一下它的扩展是如何实现的。publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity<0)thrownewIllegalArgumentException("非法初始容量："+initialCapacity);如果(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal:)loadfact;this.loadFactor=loadFactor;this.threshold=tableSizeFor(initialCapacity);}这段代码看起来很舒服write，指定初始容量和加载因子，下一个需要扩展的容量阈值由tableSizeFor方法获取outstaticfinalinttableSizeFor(intcap){intn=cap-1;//>>>:无符号右移，无论是正数还是负数，高位全部补0。n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16；返回（n<0）？1:(n>=MAXIMUM_CAPACITY)?最大容量：n+1；}tableSizeFor方法用于计算大于等于cap值的最大2次方值，当后续HashMap需要扩容时，每次将表数组的长度扩容到原来的两倍，所以长度表格数组的总是2的幂。为什么要使用移位操作而不是直接使用.pow？很明显，位运算的效率要比.pow高很多。下一步是严肃的扩展方法。finalNode[]resize(){Node[]oldTab=table;intoldCap=(oldTab==null)?0:旧标签长度；//旧容量intoldThr=threshold;//需要扩展的旧阈值intnewCap,newThr=0;if(oldCap>0){//如果不是第一次扩容if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;//如果容量大于最大值，将阈值设置为最大值，这样下一次扩展就不会发生returnoldTab;}//扩展容量是之前容量的两倍elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//下一次扩容阈值等于当前扩容阈值*2，因为扩容会把原来的容量翻倍，所以newThr=newCap*loadFactor}elseif(oldThr>0)//第一次扩容，用户指定了初始容量newCap=oldThr;//扩容容量为阈值else{//第一次扩容，初始容量和负载因子默认值newCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}if(newThr==0){//如果用户指定了初始容量，并且是第一次扩容floatft=(float)newCap*loadFactor;//下一个扩展阈值是newCap*loadFactornewThr=(newCap[]newTab=(Node[])newNode[newCap];//新数组表=newTab;if(oldTab!=null){for(intj=0;je;如果((e=oldTab[j])!=null){oldTab[j]=null;if(e.next==null)//如果不是链表或红黑树，则直接将数据移动到新数组中的相应位置newTab[e.hash&(newCap-1)]=e;elseif(einstanceofTreeNode)//在红黑树中移动数据((TreeNode)e).split(this,newTab,j,oldCap);else{//在链表中移动数据时//原key的hash值对应的数组位置可能会改变//因为做AND运算时，现有数组的长度是原来的两倍长，即,多一点和计算//所以链表或者红黑树中的元素可能在原来的位置，或者在原来位置+原来数组长度的位置NodeloHead=空，loTail=空；NodehiHead=null,hiTail=null;下一个节点；做{....省略}}}}returnnewTab;，扩容就是新建一个数组，数组的长度是原来的两倍，并且将下一次扩容的阈值设置为新数组的大小乘以加载因子，然后将原数组中的数据移动到新数组。如果数组中的元素不是链表和红黑树，则直接移动到原旧数组中的下标位置。否则，如果是链表或者红黑树，那么里面的数据可能在原来的位置，也可能在原来的位置+原来数组长度的位置。这时，将原来的链表或红黑树分成两个链表或红黑树，然后将数据移动到相应的位置。你明白吗？
