HashMap是最常用的数据类型之一，也是面试必问的问题之一，尤其是它的底层实现原理。它既是一道常见的面试题，也是理解HashMap的基石，重要性不言而喻。HashMap的底层实现JDK1.7和JDK1.8中HashMap的底层实现是不同的。在JDK1.7中，HashMap是使用数组+链表实现的，而在JDK1.8中是使用数组+链表或者红黑树实现的。HashMap在JDK1.7中的实现如下图所示：HashMap在JDK1.8中的实现如下图所示：我们这篇文章重点学习JDK1.8主流版本中的HashMap。HashMap中的每个元素称为一个哈希桶（bucket），哈希桶包含4个内容：hashvaluekeyvaluenext（下一个节点）HashMap插入过程HashMap元素的新实现源码如下（源码如下）两者都是基于JDK1.8的主流版本：publicVput(Kkey,Vvalue){//对key进行HashreturnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;//如果哈希表为空，则建表if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;//根据key的哈希值iif((p=tab[i=(n-1)&hash])==null)//如果table[i]等于null，插入tab[i]=newNode(hash,key,value,null);else{Nodee;kk;//如果key已经存在，直接覆盖valueif(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;//如果key不存在，判断是否是红黑树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;}//key已经存在直接覆盖valueif(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();afterNodeInsertion(evict);returnnull;}以上源码都添加了相应的代码注释，简单来说就是的元素添加HashMap的过程是，先对key值进行hash得到hash值，根据hash值得到元素位置，判断元素位置是否为空，如果为空则直接插入，如果不为空，判断是否是红黑树，如果是红黑树则直接插入，否则判断链表是否大于8，数组长度是否大于64，如果这两个条件都满足遇到了，把链表转成红黑tree，然后插入元素，如果这两个条件有一个不满足，则遍历插入链表，其执行过程如下图所示：为什么要将链表转为红黑树？JDK1.8引入了一种新的数据结构红黑树来实现HashMap，主要是出于性能的考虑，因为链表超过一定长度后，查询效率会很低，它的时间复杂度为O(n)，而时间红黑树的复杂度是O(logn)，所以引入红黑树可以加快HashMap在数据量大的情况下的查询效率。哈希算法实现HashMap的哈希算法实现源码如下：staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}其中，key.hashCode()是Java自带的hashCode()方法，返回一个int类型的hash值，然后将hashCode右移16位，正好是32bit的一半，异或与自身（同0，相差1），主要是将hash值的高低位混合，增加低位的随机性，从而实现HashMap的hash算法。总结HashMap在JDK1.7中是使用数组+链表实现的，而在JDK1.8中是使用数组+链表或者红黑树实现的。JDK1.8之所以引入红黑树，主要是出于性能方面的考虑。HashMap在插入的时候会判断当前链表的长度是否大于8和数组的长度是否大于64，如果满足这两个条件，则将链表转为红黑树然后再插入，否则会通过链表插入。参考文档：https://tech.meituan.com/2016/06/24/java-hashmap.html本文转载自微信公众号《Java面试真题解析》，可通过以下二维码关注。转载本文请联系Java面试真题解析公众号。
