目录
前言
1、初始化
1.1、初始化
1.2、插入第一条数据
2、数组 + 链表
2.1、插入数据：没有hash冲突
2.2、插入数据：Key不同，但产生hash冲突
2.3、插入数据：Key相同
3、数组 + 红黑树
3.1、链表如何转化为红黑树？
3.2、为什么要转化为红黑树？
4、数组resize
5、后记
前言
做过java开发的同学应该都知道HashMap是使用数组+链表的数据结构进行数据的存储，后来演变到jdk8之后，为了提高插入和查询效率，在插入的数据超过某个阈值之后，会将数组+链表的结构转化成数组+红黑树的数据结构，也即如下图：
最近闲来无事，准备将HashMap插入数据的过程，以及其数据结构的转化过程，再回顾一下，故写此篇文章，以是记录。
1、初始化
对于HashMap，在我们初始化以及插入第一条数据的时候，内部发生了什么事情呢？
1.1、初始化
当我们执行了如下一个初始化操作：
HashMap<String,String> map = new HashMap<String,String>();从源代码层面看，只是对内部一个叫做loadFactor的属性进行了初始化0.75，那么这个loadFactor参数是做什么用的呢？
我们前言中说过，HashMap是用的一个数组+链表的形式进行数据的存储，那么这个数组的长度是如何决定的呢？什么时候要对数组进行扩充，什么时候又要对数组进行缩减呢？那么这个判断依据就是根据loadFactor来决定的。具体来说就是：当插入数据的个数 / 数组的长度 >= loadFactor时，我们就要对数组的长度进行扩展啦。因为当插入的数据越来越大的时候，在数组长度不变的情况下，hash冲突会越来越严重，数组节点下的数据就会越来越多，进而导致查询效率越来越差。
另外需要说明的是：在扩展数组的时候，数组的长度都是2^n个，在初始化的时候，数组长度是2^4 = 16，每一次扩展，都增加一倍。
1.2、插入第一条数据
当我们执行如下操作，插入第一条数据的时候，hashmap的内部又发生什么事情了呢？
map.put("chenza","30")
第一步：先计算字符串"chenza"的hash值，作为判断插入数据哪个节点的依据。
第二步: 初始化数组表table，如上所述，第一次初始化的时候，数组表table的长度是2^4 = 16
第三步：用"chenza"的hash值 和 数组表table的长度(n - 1) 做"且"运算，判断当前数据应该插入到数组的哪个位置。(注：做且运算的原因保证插入的位置是[0,n-1]之间，不会数组越界)
第四步：size字段+1，并判断是否超阈值threshold，如果超过阈值threshold，则进行数组table的扩展，且以后每插入一条数据，都会进行阈值判断。(注：这里的threshold = 当前的数组table长度 * loadFactor，与上节描述一致)
代码执行逻辑如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true); //计算key的hash值
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //初始化数组table，长度16
if ((p = tab[i = (n - 1) & hash]) == null) //计算数据应该插入的位置
tab[i] = newNode(hash, key, value, null); //在数组第i个位置插入数据
else {
....... //暂时省略
}
++modCount;
if (++size > threshold) //size记录插入的数据的个数，并判断是否超阈值。
resize();
......至此，我们的初始化及第一条数据插入已经完成。从上所述，我们得知，我们一共做了三方面的工作：
(1)、初始化参数loadFactor
(2)、完成数组table的初始化，将其长度置为2^4 = 16
(3)、将数据插入到数组table对应的节点上。
到目前位置，我们的HashMap的结构如下：
2、数组 + 链表
现在，在我们的HashMap中，已经有了一条数据，那么我们接下来插入第二条、第三条...第n条数据，看看HashMap中到底经历了怎样的过程。
2.1、插入数据：没有hash冲突
何为hash冲突，在HashMap中所说的hash冲突，指的是：i = hash(key) & (n - 1)之后，数组table在i处已经有数据，代表两个不同的key需要放到数组的同一个节点下。
当没有hash冲突时，和插入第一条数据一样，直接将数据插入到数组对应的节点即可。
无hash冲突时的代码执行逻辑：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, 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); //无hash冲突，直接将数据插入到数组中
else {
......
}此时的数据结构如下：
2.2、插入数据：Key不同，但产生hash冲突
当Key不同，但是产生hash冲突的情况下，就会产生链表操作了。此时会顺着冲突处的数组节点的链表一个一个的去找，直到找到叶子节点位置，将新数据作为新的叶子节点挂在链表下面，如下图所示:
当然在寻找叶子节点的过程中，如果发现当前数组节点下的链表长度超过一定的阈值时，就会自动将链表转化为红黑树进行存储(转化为红黑树的操作，参见第三节数组+红黑树 )。HashMap默认的链表长度不能超TREEIFY_THRESHOLD = 8.代码逻辑如下：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //循环找到链表的最下端，将新的数据添加到链表的最下端
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //如果链表长度超过8，则将链表转化为红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}2.3、插入数据：Key相同
key相同，hash(Key)自然相同，自然也会有hash冲突。所以key相同是hash冲突的一种特殊情况。
第一种情况：新数据的key和数组table的节点key相同，则直接替换数组table节点的value值即可。
第一种情况：新数据的key和链表下某个节点的key相同，遍历链表，替换key相同处的value值即可。
代码执行逻辑：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 和数组table节点的值相同，直接替换value即可，value的替换见最下面的代码e.value = value
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //在这里进行了e的赋值，value的替换见最下面的代码e.value = value
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; // 循环遍历链表，寻找key值相同的链表节点，找到直接挑出循环。
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //替换key相同的value
afterNodeAccess(e);
return oldValue;
}3、数组 + 红黑树
至此，我们在每个数组节点下插入的数据都不超过8个，所以一直是链表的形式进行数据的存储。
在第二节中，我们也预埋了伏笔，当数组table某个节点下的链表超过8个以后，HashMap就会调用treeifyBin函数，将链表转化成红黑树的结构，本节，我们就来看看他是如何转化为红黑树的，以及为什么要转化为红黑树？
3.1、链表如何转化为红黑树？
链表转化为红黑树的过程，就写在treeifyBin函数中，我们先看一下这块儿代码，然后再逐个分析。
//链表转化为红黑树的过程代码
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}第一步：转化成红黑树的条件： n = (tab.length) < MIN_TREEIFY_CAPACITY(64)，也就是说当数组table的长度小于64时，不会使用红黑树，只会对数组table进行扩展，重新分配数据的存放位置。
第二步：当数组table长度大于64时，才开启转化红黑树的执行逻辑。代码中有一个while循环，注意这个while循环只是把链表节点Node转化为红黑树的节点TreeNode，这个循环中并不进行生成红黑树。这就引入一个问题，他是如何把Node转化为TreeNode的呢？其实从继承关系中可以看到TreeNode是继承自Node，TreeNode和Node的结构如下，从图上看，TreeNode比Node多了几个属性：parent,left,right,prev,red
第三步：当把所有的Node节点转化为TreeNode节点之后，继续调用hd.treeify(tab)，这个才是真正的把链表转化为红黑树。
3.2、为什么要转化为红黑树？
(1)、从链表和红黑树的结构就可以看到，红黑树的层级更低，在进行查询时，链表的查询时间复杂度是O(n)，红黑树的查询时间复杂度是O(log(n))，在数据量很大的情况下，显然红黑树的查询效率比链表要好的多。
(2)、我们知道，平衡二叉树的结构更加平衡，左右子树的高度差不会超过1，为什么不使用平衡二叉树呢? 原因是我们还要考虑插入数据的性能，平衡二叉树的结构的确更加均衡，但是为了维持这种均衡，在插入数据时，需要不断的进行平衡二叉树的旋转调整，插入效率相比红黑树来说，差的多。根据权威资料显示：插入操作是红黑树的优势之一，红黑树的插入操作可以在 O(log(n)) 的时间内完成，而平衡二叉树的插入操作在最坏情况下需要 O(n)的时间。
4、数组resize
最后，我想给大家重放一下数组resize的过程，为什么呢？在我们实际使用HashMap的过程中，如果数据量很大，免不了要进行数组的resize。resize不仅仅要对数组table进行扩展，还要对数组table节点上下挂的数据进行重新分配，所以是一个非常消耗性能的过程。
有同学可能要问了，为什么要对数组table节点上下挂的数据进行重新分配，让他们安静的待在原来的节点下不是挺好的吗？为什么要翻来覆去的去折腾？对于这样的同学，送给你三个字："要多想"
原因很简单，数组table进行了扩展，那么数组的长度n也发生了变化，我们判断数据放在数组哪个节点之下用的是 hash(key) & (n - 1)，现在数组table长度n变了，数据存放的位置自然也要发生变化，不然查询key时定位的数组节点位置不一样，无法从HashMap中查出key对应的数据。
另外在走读源码的过程中，发现一个很有意思的设计：那就是原来一个数组节点下的链表(红黑树)数据，在进行resize之后，数据会被重新分配到几个新的节点上呢？答案是两个。这个点在没看源代码之前是没有想到的，看了源代码之后，感觉这个点设计的太精妙了。原因是什么呢？待我慢慢道来。
我们知道，数组table的长度每次resize都是扩展一倍，且长度还都是2^n，也就是说数组table的长度只会是16,32,64,128,256...；而数据存放到数组哪个节点是有由hash(key) & (length - 1) 来决定的。在这两个条件下，就会发生上述一个节点数据分裂成两个节点数据的情况。我们以扩展前数组table长度是16和扩展后数组table长度是32为例，来说明具体原因。
hash(key) 是不会变的，变的只有length - 1；
当length = 16时，length - 1就是15，15的二进制是00001111，
当length = 32时，length - 1就是31，31的二进制是00011111，
看出来什么特殊之处了吗？对，就是31的二进制比15的二进制的上一位多了一个1，这就导致(hash(key) & 31) 和 (hash(key) & 15) ，要么相等(数据保留在数组原位置)，要么最高位多一个1(也就是数组位置+16)；
32扩展到64； 64扩展到128... 原理类似。
看到这里，真是不得不感叹二进制世界的奇妙和jdk编程人员对二进制的运用达到了炉火纯青的地步。
所以在扩展前后一个数组节点下的数据的分裂过程如下：
下面是代码层面链表一分二的过程(代码里有作者注释)：(另：红黑树的分裂过程类似，也是将一个红黑树分裂成两个红黑树，在这里就不赘述了，大家可以看((TreeNode<K,V>)e).split(this, newTab, j, oldCap)中的split函数，里面也是两个变量loHead 和 hiHead分别存放分裂后的两个红黑树)
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//扩展前的数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//扩展前的插入数据的阈值(数组长度 * 0.75)
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //如果数组长度已经大于1 << 32，不再进行扩展，直接返回。
threshold = Integer.MAX_VALUE;
return oldTab;
}
// newCap = oldCap << 1,左移一位，相当于扩展一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//插入数据的阈值也扩展一倍。
newThr = oldThr << 1;
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// -----上面的代码主要是对新数组的长度和数据个数的阈值进行重新计算
// -----下面的代码主要是对数据重新分配
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是红黑树，则进行红黑树的分裂
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {//如果是链表，则进行链表的分裂
/**
*由分析知，一个链表只可能分裂成两个链表。
*loHead：存放的是位置不动的数据
*hiHead：存放的是位置+16(以分析为例)的数据
*/
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
//j不动，loHead还存放在原来的数组位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//j + 16(以分析为例),hiHead存放在j + 16位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}5、后记
断断续续写了好久，一边走读源码，一边画图，一边写文章，终于把HashMap的内部结构分析完了。相对其他java数据结构来说，HashMap结构算是稍微比较复杂的，但是HashMap并不是多线程安全的，在多线程使用的情况下，要注意线程安全问题。
了解了HashMap之后，其实也就了解了HashSet，因为HashSet就是内部构建了一个HashMap对象，使用了HashMap的key不会重复的特性来进行数据的去重。
另外本篇文章旨在探究HashMap的结构，对其中的红黑树并没有过多着墨进行进一步深究，因为红黑树的生成条件、插入数据时节点的旋转、红黑节点的变化等等，还是比较复杂的，如果写在这篇文章中，有点鸠占鹊巢的意思。所以，红黑树的内容完全可以单独抽离一篇文章进行探究，就不在HashMap文章中进行赘述了，后面有时间，我会再学习一下红黑树，再来跟大家唠叨唠叨。
