前言HashMap应该算是Java后端工程师面试的必考题了，因为里面的知识点太多了，很适合考Java基础面试官。开场面试官：请先自我介绍一下！Angela：我是Angela，草丛三婊之一，最强中单（钟馗反对）！哦，不对，我路过，我是**，目前在公司做系统开发。面试官：根据你的简历，你对Java集合比较熟悉，有没有用过HashMap？安吉拉：用过。（还是熟悉的味道）面试官：那说说HashMap的内部数据结构？Angela：目前我使用的是JDK1.8版本，内部使用数组+链表/红黑树；Angela：方便给你画个数据结构图：面试官：那你知道HashMap的数据插入原理吗？安吉拉：呃[沉思]。我觉得画个图应该更清楚，如下：判断数组是否为空，为空则初始化；如果不为空，则计算k的hash值，通过(n-1)&hashindex计算数组中应该存入的下标；检查table[index]中是否有数据，如果没有数据，则构造一个Node节点存入table[index]中；如果有数据，说明发生了hash冲突，继续判断key是否相等，用新值替换原数据（onlyIfAbsent为false）；如果不相等，则判断当前节点类型是否为树节点，如果是树节点，则创建一个树节点并插入到红黑树中；如果不是树节点，则创建一个普通的Node并加入到链表中；判断链表的长度是否大于8，如果大于，则将链表转为红黑树；插入完成后，判断当前节点数是否大于阈值，如果大于则开始扩容到原数组的2倍大小。面试官：刚才您提到了HashMap的初始化，如何设置HashMap的初始容量？安吉拉：【有问题吗？?]一般newHashMap()如果不传值，默认大小为16，加载因子为0.75。如果传入初始大小k，则初始大小为大于k的2的整数次方。例如，如果传递10，则大小为16。（补充说明：实现代码如下）staticfinalinttableSizeFor(intcap){intn=cap-1;n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16;return(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;}补充说明：下图是详细过程，该算法是让初始的二进制分别右移1、2、4、8、16位，并与自身异或，将高位为1的数连续右移，而111111+1=1000000=（意思是大于50，2的整数次方）面试官：你提到了哈希函数，你知道HashMap的哈希函数是怎么设计的吗？Angela：【问题挺详细的】hash函数是先获取key传过来的hashcode，是一个32位的int值，然后对hashcode的高16位和低16位进行异或运算.采访者：那你知道为什么要这样设计吗？Angela：【这个还要问】，这个也叫扰动函数，这样设计有两个原因：hash碰撞要尽可能的减少，越分散越好；算法必须尽可能高效，因为这是一个高频操作，所以使用位操作；面试官：为什么hashcode的高16位和低16位异或可以减少hash冲突？hash函数可以直接使用key的hashcode吗？【这道题有点刁钻】，安吉拉差点停在原地，恨不得做biubiubiu二一三连击。Angela：因为key.hashCode()函数调用了key键值类型自带的hash函数，返回的是一个int类型的hash值。int值的范围是**-2147483648~2147483647**，加起来大概有40亿个映射空间。只要哈希函数映射均匀松散，在一般应用中就很难发生碰撞。但是问题是一个长度为40亿的数组内存是放不下的。你想，如果HashMap数组的初始大小只有16，那么在使用之前需要对数组的长度进行取模运算，余数可以用来访问数组下标。源码中的取模运算是对哈希值和数组长度-1进行“与”运算，位运算比%运算快。bucketIndex=indexFor(hash,table.length);staticintindexFor(inth,intlength){returnh&(length-1);}顺便说一句，这也解释了为什么HashMap的数组长度应该是2的整数次方。因为这（数组长度-1）完全等同于“低位掩码”。“与”运算的结果是哈希值的高位全部清零，只保留低位用于数组下标访问。以初始长度16为例，16-1=15。二进制表示为000000000000000000001111，与某一个哈希值进行“与”运算如下，结果是截取最低的四位数值。101001011100010000100101&0000000000000000000001111----------------------------------------00000000000000000000000001//所有高位清零，只有最后一位清零fourbitsarekeepedbut那么问题就来了，所以即使我的hash值分布比较松散，如果只取最后几位的话，碰撞也会很严重。更要命的是，如果hash本身没有做好，等差数列分布的漏洞，如果有规律地重复最后几个低位，那将是极其痛苦的。这个时候hash函数（“扰动函数”）的值就体现出来了，到这里大家应该也猜到了。看下图，右移16位，刚好是32bit的一半，将自己区域的高半位和低半位异或，将原哈希码的高位和低位混合，从而增加低位的随机性。而且，混合的低位掺杂了高位的一些特征，这样也变相的保留了高位的信息。最后，我们看一下PeterLawley的专栏《An introduction to optimising a hashing strategy》中的一个实验：他随机选取了352个字符串，在它们的哈希值完全没有冲突的前提下为它们做了一个低位掩码,取数组下标。结果表明，当HashMap数组长度为512()，即低9位被掩码取走时，不加扰动函数的碰撞次数为103次，接近30%。应用扰动函数后，只有92次碰撞。碰撞减少了近10%。看来扰动函数确实有效。另外，Java1.8相对于1.7也做了一些调整。1.7做了四次移位和四次异或，但显然Java8认为一次扰动就够了。如果做四次，做多了可能边际效用也不会很大。所谓为效率而改一次。下面是1.7的哈希码：staticinthash(inth){h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}面试官：看来是做了功课，有点素材了！偷偷看了Angela的博文公众号，你刚才说1.8优化了hash函数，请问1.8还有其他优化吗？Angela：1.8主要有3个优化：数组+链表改成了数组+链表或者红黑树；链表的插入方式由头插入法改为尾插入法。简单的说，插入时，如果数组位置已经有元素，1.7将新元素放入数组，原节点作为新节点的后继节点，1.8遍历链表，将元素放在链表的结尾；扩容时，1.7需要对原数组中的元素重新hash，以定位到新数组的位置，1.8采用了更简单的判断逻辑，位置不变或者索引+旧容量；插入时，1.7先判断是否需要扩容，然后插入，1.8先插入，插入完成后再判断是否需要扩容；面试官：分别说说你为什么要优化这几个点；Angela：【咳咳，果然是连环枪】为防止hash冲突，链表长度过长，时间复杂度从O(n)降低为O(logn)；因为1.7头插入方式在扩容的时候会把链表反转，在多线程环境下会产生环；线程A正在插入节点B，线程B也在插入，当容量不够时开始扩容，重新哈希，放置元素，使用头部插入的方式，将遍历的B节点放入头部，这样就形成了ring，如下图：1.7扩展调用转移代码，如下图：voidtransfer(Entry[]newTable,booleanrehash){intnewCapacity=newTable.length;for(Entrye:table){while(null!=e){Entrynext=e.next;if(rehash){e.hash=null==e.key?0:hash(e.key);}inti=indexFor(e.hash,newCapacity);e.next=newTable[i];//如果A线程执行到这一行就挂了，线程B开始扩容newTable[i]=e;e=next;}}}3.为什么扩容？1.8是否可以不用重新哈希直接定位到新数据中原节点的位置？这是因为扩容是扩容到原数组的两倍大小，而用来计算数组位置的掩码只是多了一位高位。例如：扩容前的长度为16，用于计算(n-1)&hash的二进制n-1为00001111，扩容后的二进制数为32高1，============>is000111114.因为是&运算，1和任意数&都是它本身，所以有两种情况，如下图：原先第4高位的情况数据hashcode为0，高位为1；第四个高位为0，re-hash值不变，第四位为1，re-hash值比原来大16（旧数组的容量）面试官：HashMap是线程安全的吗？Angela：不会，在多线程环境下，1.7会出现死循环、数据丢失、数据覆盖的问题，1.8会出现数据覆盖的问题。以1.8为例，当线程A执行到下面代码第6行，判断索引位置为空时，直接挂掉，线程B开始执行第7行，向索引位置写入节点数据。此时线程A恢复场景，执行赋值操作覆盖线程A的数据；而38行的++size也会造成多线程同时扩容等问题。finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)//这里多线程执行tab[i]=newNode(hash,key,value,null);else{Nodee;Kk;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,null);if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}if(e!=null){//existingmappingforkeyVoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size>threshold)//多线程过来，可能会重复resize()resize();afterNodeInsertion(evict);returnnull;}面试官：你平时做什么？如何解决这个线程不安全问题？Angela：Java中有HashTable、Collections.synchronizedMap、ConcurrentHashMap可以实现线程安全的Map。HashTable直接在操作方法中加上synchronized关键字，锁住整个数组，粒度比较大；Collections.synchronizedMap使用了Collections集合工具的内部类，通过传入一个Map封装了一个SynchronizedMap对象，在里面定义了一个对象锁，通过方法中的对象锁来实现；ConcurrentHashMap使用了段锁，降低了锁的粒度，大大提高了并发性。面试官：你知道ConcurrentHashMap的段锁的实现原理吗？安吉拉：【我的天啊！套娃，一套一套】ConcurrentHashMap成员变量用volatile修饰，避免指令重排序，保证内存可见性。另外，通过CAS操作和synchronized的结合，实现了赋值操作和多线程操作，只有当前操作索引的节点才会被锁定。如下图所示，线程A锁定了节点A所在的链表，线程B锁定了节点B所在的链表，操作互不干扰。面试官：您刚才提到链表到红黑树的转换是链表长度达到一个阈值的时候。门槛是多少？Angela：门槛是8，红黑树转链表的门槛是6。面试官：为什么是8，不是16、32甚至7？还有为什么红黑树到链表的阈值是6而不是8？安琪拉：【去问作者吧！我的天，biubiubiu真的要连续走213步】因为作者是这样设计的，哦，不对，因为经过计算，在哈希函数设计合理的情况下，8次哈希碰撞的概率是百万分之6，概率说。.因为8就够了，至于为什么又转回6，因为如果hash碰撞次数在8附近徘徊，链表和红黑树的转换总会发生，为了防止这种情况发生。面试官：HashMap的内部节点是有序的吗？Angela：是无序的，根据hash值随机插入面试官：有没有有序的Map？Angela：LinkedHashMap和TreeMap面试官：请问LinkedHashMap是如何实现有序的？Angela：LinkedHashMap内部维护了一个单链表，有头节点和尾节点。同时LinkedHashMap的节点Entry不仅继承了HashMap的Node属性，还有before和after来标识前节点和后节点。可以实现按插入顺序或访问顺序排序。/***Thehead(eldest)ofthedoublylinkedlist.*/transientLinkedHashMap.Entryhead;/***Thetail(youngest)ofthedoublylinkedlist.*/transientLinkedHashMap.Entrytail;//链接新加入的p链表后端的节点privatevoidlinkNodeLast(LinkedHashMap.Entryp){LinkedHashMap.Entrylast=tail;tail=p;if(last==null)head=p;否则{p。before=last;last.after=p;}}//LinkedHashMap节点类staticclassEntryextendsHashMap.Node{Entrybefore,after;Entry(inthash,Kkey,Vvalue,Nodenext){super(hash,key,value,next);}}示例代码：publicstaticvoidmain(String[]args){Mapma??p=newLinkedHashMap();map.put("1","Angela");map.put("2","of");map.put("3","blog");for(Map.Entryitem:map.entrySet()){System.out.println(item.getKey()+":"+item.getValue());}}//控制台输出1:Angela2:of3:Bloginterviewer:Tellme关于TreeMap是如何实现排序的？Angela：TreeMap是基于Key的自然顺序或者Comprator的顺序行排序内部是通过红黑树实现的，所以要么key所属的类实现了Comparable接口，要么自定义一个实现了Comparator接口的比较器传递给TreeMap用户key进行比较。面试官：前面说了，CAS和synchronized的结合可以降低锁的粒度。能介绍一下CAS的实现和synchronized实现的原理吗？安吉拉：让我们约好下一期，好吗？面试官：嗯，回去等通知吧！
