HashMap作为Java中的重要的数据结构，不仅在平常工作中被大量使用，并且在面试中也是处于必问的重要角色，今天带大家从源码角度再次重新认识一下我们常用的HashMap。
在从JDK7转化为JDK8时，HashMap的实现也发生了很大的改变，先来看一下它们的区别：
JDK7 中使用数组+链表，JDk8 中使用数组+链表+红黑树实现
新节点在插入到链表时插入的顺序不同（JDK7插入在头节点，JDK8插入在尾节点）
HASH算法有所简化
扩容机制有优化
首先看存储结构，如果大家对红黑树比较陌生，可以先自行查看完全平衡二叉树（AVL）和红黑树的相关知识，篇幅有限不再赘述。这里只列出红黑树的一些性能特点：
调整规则没有完全平衡二叉树严格
插入效率比链表低，但查询效率比链表高
红黑树查询效率介于链表和完全平衡二叉树之间，折中
JDK7
在HashMap中，我们最常用的操作大概就是put与get了，但是你真的了解他们的实现原理吗？看看put操作的核心代码：
inthash=hash(key);inti=indexFor(hash,table.length);table[i]=newNode;
大体来说，包含三个操作：
1、计算传入key的hash值
2、通过indexFor方法计算下标值
3、将newNode加入链表，放进对应的数组下标中
注意，第三部我们直接将newNode赋值给table[i]，也就是说把节点插入在了头结点上，而将原先的链表直接连在我们新插入的节点后面。
顺带一提，HashMap中支持key为null，数组第0个位置存放key=null的元素，只能有一个key=null的元素，第0个位置不存在数组。
而get操作就比较简单了，先找到数组的下标，再比较key是否和给定的key相同，不同则顺着链表找下一个，直到找到或为空。具体通过getEntry()方法，遍历比较hash值是否相等，比较key是否相等。
//key不为null,获取valuefinalEntry<K,V>getEntry(Objectkey){if(size==0){//判断链表中是否有值//链表中没值,也就是没有valuereturnnull;}//链表中有值,获取key的hash值inthash=(key==null)?0:hash(key);//在“该hash值对应的链表”上查找“键值等于key”的元素for(Entry<K,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){Objectk;//判断key是否相同if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;//key相等,返回相应的value}returnnull;//链表中没有相应的key}既然被称为HashMap，那么计算hash值肯定是必要的一环，先看看JDK7中HashMap的hash方法：
finalinthash(Objectk){inth=hashSeed;if(0!=h&&kinstanceofString){returnsun.misc.Hashing.stringHash32((String)k);}h^=k.hashCode();h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}在这当中，暂且不看hash种子，我们可以看到计算中存在大量的右移操作，那么为什么要进行右移呢，这是考虑到了碰撞性问题。之前提到使用indexFor来计算数组下标：
staticintindexFor(inth,intlength){returnh&(length-1);}这里提一点，HashMap的长度一定是一个二的次方数，这点是在它的初始化和扩容中被限定的。这里在计算下表时，一个二的次方数减去1，能够保证它的二进制数的后几位数字全部是1，便于计算下标。
举个例子，HashMap长度为16，这样计算出的hash值与0000 1111做与运算，只需要取后四位，就实现了数组下标的计算。而与操作的计算速度比取余操作是要快上一些的。
回到上面，继续讲为什么要进行大量的右移操作，还是以长度为16来看，如果几个key计算出的hash值为：
101001100010011000000110
我们发现，只要后四位一样，hash值都一样，碰撞性很高，所以这时要引入右移操作，让高位也能参与到与运算。让链表分散，减少链表长度。
JDK8
jdk8中引入了红黑树，但并不是说链表并不存在，查阅源码，我们可以发现两个非常关键的值：
staticfinalintTREEIFT_THRESHOLD=8;staticfinalintUNTREEIFT_THRESHOLD=6;
当链表的元素超过8时，会自动转成红黑树；当红黑树的节点数小于6时，变回链表。
看看put操作：
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node<K,V>[]tab;Node<K,V>p;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{Node<K,V>e;Kk;//key相等情况，e在最后处理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){//binCount是遍历链表过程中计数//遍历链表，循环到尾结点，把新元素加在尾部，breakif((e=p.next)==null){p.next=newNode(hash,key,value,null);//判断是否大于变成树的阈值-1,7会变成8，变成红黑树if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}//找到相等元素也breakif(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}//重复keyif(e!=null){//existingmappingforkeyVoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;//扩容if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}看完这段代码，我们就明白了为什么jdk8中使用的是尾插法。因为在判断是使用链表或红黑树的过程中，要判断是否超过8个元素，至少需要遍历一遍，所以使用尾插法，新元素可以直接插入在尾结点。
get方法大体思路不变，计算下标，然后遍历，只不过是比jdk7中多加上一个判断是试用链表存储还是红黑树存储的步骤。
而jdk8也精简了它的hash算法：
staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}只右移16位，精简了hash算法，配合红黑树提高查询效率。
最后看一下两者的扩容操作，扩容是对数组进行扩容，而不是链表或红黑树。我们在初始化时数组的默认长度是16，前面提到当存储的元素很多时会发生hash碰撞。我们扩容的目的是将长链表的长度减短，提高查询效率。
由于扩容的源码比较长，就不贴在这里，只列出核心思想。
jdk7中：
只有当数量大于阈值，且当前插入位置不为空时才会进行扩容，并且容量为原先2倍。
在将老的table转移到新的table时，需要重新计算数组的下标。
扩容后，重新计算下标。以从16位扩容到32位为例：
h101001103100011111结果00000110（与之前相同）
h101101103100011111结果00010110（与之前不同，相当于比之前加了16）
扩容后，数组下标可能改变，也可能不变。这时要看扩容的那一位的哈希值是1还是0，如果是1则不同，0则相同。但是在这个过程中，有可能造成死锁问题。
jdk8中：
JDK8扩容中，为了避免之前提到的死锁问题，改进了扩容方法。通过判断这1位是0还是1，是0则不变。如果是1 ，加上原先数组大小。
//key不为null,获取valuefinalEntry<K,V>getEntry(Objectkey){if(size==0){//判断链表中是否有值//链表中没值,也就是没有valuereturnnull;}//链表中有值,获取key的hash值inthash=(key==null)?0:hash(key);//在“该hash值对应的链表”上查找“键值等于key”的元素for(Entry<K,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){Objectk;//判断key是否相同if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;//key相等,返回相应的value}returnnull;//链表中没有相应的key}0总结：
扩容这一操作非常耗时，默认达到75%按照2倍进行扩容，这个75%也就是factor扩容因子。
JDK7中扩容是在节点还没有加到HashMap前发生的；JDK8中扩容是在节点加到HashMap后发生的。
JDK7扩容是一个一个元素计算然后转移，JDK8是先遍历，判断哪些是放到新数组的低位，哪些是高位，然后将low的元素和high的元素分别组合起来，一次性转移到新的数组中。
最后
如果觉得对您有所帮助，小伙伴们可以点赞、转发一下，非常感谢
公众号
码农参上，加个好友，做个点赞之交啊