下面代码分析时基于 jdk1.8 的
HashMap 是什么？
说先我们看一下HashMap的基本用法：
<code>Map<string> map = new HashMap<>();
\t\tmap.put("hello", "world");
\t\tSystem.out.println(map);/<string>/<code>
我们从put操作开始分析。源码如下：
点进入 putVal 方法：
如果你直接看上面的代码，可能会懵掉。
下面我们可以换一个思路来思考作者是怎么实现HashMap的？？
HashMap是干什么的？
我们从上面用法上可以看出，HashMap 是用来存储 key -value数据的。
HashMap 是用什么数据结构来存储的？
我们可以回忆一下 ArrayList 和 LinkedList 的数据结构。
我们从ArrayList 的add 方法看起：
从上面可以看出 ArrayList 使用的是 数组实现。
下面看下 LinkedList add 方法：
Node 节点定义如下：
LinkedList 节点定义
所以 LinkedList 使用的是双向链表。
HashMap 数据结构 = 数组 + 单向链表，如下图
HashMap 的数据结构
我们通过看源码来验证上面数据结构：
内部类 Node定义
上图的是HashMap中的Node 节点定义，是一个单向链表。
上图定义Node数组 来放Node节点。
HashMap其他定义
1.Node 数组的定义长度为
默认Node数组大小
默认为16.
2.负载 因子 DEFAULT_LOAD_FACTOR 什么意思呢？
负载因子
默认负载因子为0.75 ，当存储的元素越来越多，Node数组存储的空间越来越少，该怎么办呢？
只有扩容，那么该怎么扩容？什么时候扩容呢？
我们知道HashMap默认大小为16，负载因子为0.75
则当容量 > 12时，进行扩容。
3.当链表的长度大于一定长度怎么办？
当链表的长度很长时，会有什么缺点呢？
如果查询到的节点是最后一个节点时，则需要遍历此节点上的所有链表中的元素。所以比较耗时。
JDK8 中，当链表长度大于一定长度时，就会转成 红黑树。
当 单向链表的长度 > 8 时，就会转成 红黑树
- 当向Map中put一个元素时，如何知道放在数据中的哪个位置呢？
从上面的数据结构可以看出，先把元素存储在数组中，如果有重叠，则放在链表中。
当put一个key，首先通过获取 key.hashCode把key生成一个hashCode,然后再经过一些列算法生成0-15之间的数值(因为Map的默认值为16）。
那么怎样设计一个算法，把key计算成一个0-15 之间的数据呢?
1.先通过Object的hashCode方法，获取key的hashCode值
2.然后控制这个值在0-15 之间，可以对16进行取模
put源码分析
首先我们看下put方法的流程：
流程如下：
1、计算key的hash值
调用Object的hashCode，得到hashCode值，然后 第16位 和 高16位 做异或，得到最终hash值。
2、得到Node节点在数组中的位置
计算逻辑为 (n-1) & hash
为什么是 n - 1 呢？默认值为16, 15 的二进制为 01111
比如 上面得到的hash值为 ：
00000000011111000001110110101
& 01111
--------------------------------------------------------------
0101
如果为n - 1 ,则 hash值的倒数第5位无论为1或者0，和 15的与后，最终的值都在0-15之间。
上面代码逻辑如下：
1、第一个if: 如果table还没有初始化，则先进行初始化。
2、第二个if : 如果根据key的hash值，获取到在数组中的位置，如果为 null,则直接new 一个Node节点，直接放进去。
下面看else代码：
1、第一个if : 如果原来的位置有节点，且key相同，则直接覆盖原值即可。
2、else if : 判断节点是否为 红黑树，如果是，则调用红黑树添加逻辑。
3、else: 则为链表，调用链表的处理逻辑
(1) 如果 (e = p.next) == null ，则 直接创建Node节点，如果大于红黑树阀值，则转红黑树，然后插入。
(2) if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break;
如果插入的key 已经存在，则直接跳出，执行下面逻辑。
执行上面的前提是在Map存在此key，则直接替换旧值即可。
最后再次要判断是否需要扩容？？
resize 方法
上面的最初oldCap中为16，(newCap = oldCap << 1 ） 则扩容为当前容量的2倍。
比如：当前oldCap = 16, 16的二进制为 1000，左移一位为：10000，= 32
容量变的同时，threshold 也要变，32 * 0.75 = 24；
下面的操作就是对节点进行重新分配：
有以下几种情况：
1、有节点，但是下面为空
2、有节点，下面不为空，但是为红黑树
3、有节点，下面不为空，但是为链表
e.hash & oldCap 是什么意思呢？
e.hash & oldCap 的结果只有两个值，要么为0，要么为1。
rehash的时候，是根据 e.hash & oldCap 是否为0，来拆分low 和 high 两个链表的。
然后newTab[j] = low,newTab[j+oldCap]= high;
所以resize 后的位置，要么在newTab[i],要么在newTab[i + oldTab]
閱讀更多 碼農的一天 的文章
