过去，HashMap是Java面试的常客，无论是刚毕业还是工作多年的同学，在Java面试中都会经常被问到关于HashMap的问题，每次面试都会被问到平时不关心的问题。 因为HashMap对毕业生和老司机都很熟悉，你越是经常忽视就越熟悉。
抱着知是知、知是知的精神，我深入学习了JDK 1.8版的HashMap源代码。 众所周知，在JDK 1.8中实现HashMap有一些改进，特别是在数据存储结构中引入了红黑树，查询更快。 本文也会分析相应的内容，期待大家的成果。
一. HashMap基础
1.1散列映射定义
不用说，先从HashMap的基础开始吧。 让我们先来看看HashMap的定义：
在公共类映射、V extends AbstractMapK、V implements MapK、v、Cloneable和Serializable1中，HashMap继承了AbstractMap
1.2散列映射属性
接下来，在源代码中查看HashMap的重要常量属性。
我需要在这里知道运算符的意思。 表示换档操作。 相对于二进制数左移一位，表示乘以2。 其中14表示00001中的1向左移动了4位，达到了10000。 换算成十进制数时，2^4=16，即HashMap的默认容量就是16。Java中还有其他位操作符计算速度快，可以在日常工作中使用以提高系统性能。
此处需要加载因子(load_factor )，加载因子默认为0.75，http://www.Sina.com /
二.初始化
一般来说，我们初始化的时候这样写：
MapK，V map=new HashMapK，v (；
在这个过程中发生了什么？ 看看源代码吧。
如果我们跟踪调试程序，就会发现这里的initialCapacity是31，而不是我们想象的16。 而且，经过几次变化后，initialCapacity最终变成了11。 为什么会这样呢？ 老实说，我也不知道。 希望大神能帮助我们解答。
我们继续。 初始化时，首先判断初始容量是否小于0，如果小于0，则抛出异常。 接着，判断初始容量是否大于最大容量2^31，如果大于，则将初始容量设定为最大初始容量。 接下来，判断加载因子： 0以下时，或者不是数字时，抛出异常。 这些验证完成后，将HashMap加载系数和扩展阈值设置为。 这里需要注意。 阈值=容量*加载因子。 我们的阈值是怎么来的？ 让我们看看一种叫做tableSizeFor ()的方法。
可以看到英语评论。 returnsapoweroftwosizeforthegiventargetcapacity.(返回与目标容量对应的2的幂。 )请想象一下，如果将初始值设置为非2的幂(例如19 )，则最终通过这种方法获得的数组大小将是多少。 算一下吧。
由于cap最大为2^31，可以看出该方法的最终目的是返回大于cap的最小2的幂。
三. put () )
然后，我们开始分析HashMap中最重要的方法之一：put ()。
首先，让我们看看hash(key )。 接下来，让我们看看putVal ) )方法。 这两种方法是精髓。
3.1散列(密钥)。
首先上传源代码：
key=null时也有混列值，可以看出是0。 因此，与http://www.Sina.com/HashTable源代码相比，可以看到hashtable的key直接执行hashCode，如果key为null，则抛出异常
也可以首先计算key的hashCode ()为h，然后将h与无条件右移16位的二进制进行异或) ^ )，从而获得最终的hash值。 此散列值是数组中的键值对的位置。
备注：异或的操作如下。 返回0^0=0、1^1=0、0^1=1、1^0=1(如果相同则返回0，如果不同则返回1 )。
我们现在没有深入追求为什么这样设计。 如果知道这样设计的目的是为了使散列值的分布更均匀就可以了。
3.2 putVal (方
法3.2.1 源码
我们直接看源码。
我们慢慢来分析。首先看入参：
hash：表示key的hash值
key：待存储的key值
value：待存储的value值，从这个方法可以知道，HashMap底层存储的是key-value的键值对，不只是存储了value
onlyIfAbsent：这个参数表示，是否需要替换相同的value值，如果为true，表示不替换已经存在的value
evict：如果为false，表示数组是新增模式
我们看到put时所传入的参数put(hash(key), key, value, false, true)，可以得到相应的含义。
3.2.2 HashMap的数据结构
在继续下一步分析之前，我们首先需要看一下HashMap底层的数据结构。
我们可以看到，HashMap底层是数组加单向链表或红黑树实现的(这是JDK 1.8里面的内容，之前的版本纯粹是数组加单向链表实现)。
下面我们看一下HashMap的一些重要的内部类。首先最重要的就是Node类，即HashMap内部定义的单向链表
我们重点看一下数据结构，Node中存储了key的hash值，键值对，同时还有下一个链表元素。我们重点关注一些equals这个方法，这个方法在什么时候会用到呢？当我们算出的key的hash值相同时，put方法并不会报错，而是继续向这个hash值的链表中添加元素。我们会调用equals方法来比对key和value是否相同，如果equals方法返回false，会继续向链表的尾部添加一个键值对。
当然，在JDK 1.8中引入了红黑树的概念，内部定义为TreeNode，对红黑树感兴趣的同学可以看看相关的文档，引入红黑树是为了提升查询的效率。
3.2.3 继续分析putVal()方法
首先判断当前HashMap的数组是否为空，如果为空，则调用resize()方法，对HashMap进行扩容，这次扩容的结果就是HashMap的初始化一个长度为16的数组。获取到数组的长度n。代码如下：
接着，根据长度-1和hash值进行按位与运算，算出hash值对应于数组中的位置，从tab中将这个位置上面的内容取出，判断为null时，在这个位置新增一个Node。代码如下：
如果同样的位置取到了数据，也就是这个hash值对应数组的位置上面已经有了键值对存在，这时候我们就需要做一些动作了。首先，我们判断这个Node，也就是p的hash值是否与传入的hash相等，然后接着判断key是否相等(这里判断key是否相等，用了一个或运算)。如果判断通过，表示要传入的key-val键值对就是tab[i]位置上面的键值对，直接替换即可，不用管后面是链表还是红黑树。代码如下：
如果tab[i]的key不是我们传入的key，下面我们首先要判断p这个Node是不是红黑树，如果是红黑树，直接向红黑树新增一个数据。向红黑树新增数据的代码我们后续再解析，目前先不进行分析。代码如下：
下面，当p是单向链表时，我们遍历链表进行插入等操作。找到链表的尾部，将节点新增到尾部。如果链表的长度大于等于红黑树化的阈值-1，就将桶(也就是链表)转成红黑树存储数据。如果在链表中还存在相同的key，直接替换旧的value即可。
最后，还有一个操作，大家千万不要忽略，也就是判断当前的键值对数量是否即将超过阈值，如果即将超过，需要进行resize()操作。
下一篇文章我们将着重分析resize()和get()的源码。
==========================================================================================
本文继续分析HashMap的源码。本文的重点是resize()方法和HashMap中其他的一些方法，希望各位提出宝贵的意见。
话不多说，咱们上源码。
上面一段代码的内容比较好理解，都已经根据注释就能看懂，主要的内容在下半部分：扩容后和扩容前，数据存放位置的变化。我们可以理解一下。
经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。