在上篇文章中解答了初步认识了 HashMap 的扩容，初始化以及容量的实现，今天接着上篇文章来讲，解决一下第二个问题。Q2. 底层的存储数据结构？
老规矩，在开始之前还是先把常用的几个属性掏出来
/** * 树化的阈值 */ static final int TREEIFY_THRESHOLD = 8; /** * 反树化的阈值 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 最小树节点容量 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * 节点数组 */ transient Node<K,V>[] table;还有一部分属性在上一篇文章中已经讲过了，这里不再描述了。本篇文章的重点是描述 HashMap 的存储结构，其他没有介绍的属性暂时不用关心。
上篇文章说道：HashMap 是在 putVal 这个方法里面进行初始化的，这个方法里面的 resize 方法既担任了初始化的工作同时也担任了扩容的工作。
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; //这里的长度就是 32 if ((p = tab[i = (n - 1) & hash]) == null) // （32 - 1）和 key 的 hash 值做 & 运算，检测当前索引位置是否存在值 tab[i] = newNode(hash, key, value, null); //不存在就把该 Node 节点放在数组的最后位置。 else { //该位置已经有值了 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断该位置旧 Node key 的 hash 值是否与传进来的相等，并且（key == key，或者 key.equals(key)） else if (p instanceof TreeNode) //不相等就判断对象的实例是否是 TreeNode 类型 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //如果是 TreeNode 类型，说明已经树化，调用 TreeNode 的 putTreeVal 将节点插入到树中 else {//该位置有值，并且 hash 不一致，则产生和 hash 冲突，下面的循环开始解决 hash 冲突 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); //树化 break; } //链表的下一个节点不为空，那么计算判断链表的 next 节点的 hash 和传进来的 key 的 hash 是否相等，k 是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; //如果都不满足，直接存放即可 } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }根据上面的代码进行分析，基本可以确定 HashMap 是由数组 + 链表（树）组成的。首先 tab数组作为主体部分，tab 数组里面的每一个值都挂了一个 Node 节点的单链表。（Node 节点中都存有下一个节点的引用）
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; //下一个节点的引用 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }当我们想往 Map 容器中 put 一个值时，会先调用 hash(key) 这个方法，计算出 key 的 hash 值，然后将计算完毕的 hash 以及 key，value 传给 putVal 方法。
调用 putVal 方法之后，会先去判断该值是否在 tab 表中存在。判断方式如下:
if((p = tab[i = (n - 1) & hash]) == null){ tab[i] = newNode(hash, key, value, null); }a. 如果 (p = tab[i = (n - 1) & hash]) == null 满足条件 说明该位置没有数据，此时将 Node 节点放在 tab[i] 的位置，并且将该节点的下一个节点置为 null，也就是说没有 hash 冲突的 Node 节点只是一个单节点的链表。
看看 hash 方法是如何计算的，源码如下:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }这里有个点需要注意，HashMap 是允许空 key 的，如果 put 进来的 key 为 null 的话，就将 0 作为 key 为 null 的 hash 值。如果不为空的话就计算 key 的 hash 值为 h，与 h >>> 16 做位运算。
b. 如果 (p = tab[i = (n - 1) & hash]) == null 不满足条件 说明该位置已经数据了，这里就出现了 hash 冲突。既然出现了冲突，就需要去解决冲突。接着 putVal 的源码往下看。
既然这个位置已经有值了，那么就需要判断当前位置的 Node 节点和要存储的 Node 节点是否相同。 判断依据
存储的 Node 节点的 hash 值和 当前位置的 hash 是否想等存储的 Node 节点的 key 和当前位置的 key 相等（==）。或者、要存储的节点的 key 不能为空且存储的 key 和源节点的 key 要相同（equal） 如果上面两个条件都满足，那么将执行 e = p（原值返回）如果当前位置的 Node 节点和要存储的 Node 节点不相同，那么就要判断当前节点的位置是否是 TreeNode 类型，如果是 TreeNode 类型，就调用 TreeNode 类型来 put TreeVal 存值。（树化存储，后面讲）
如果当前位置的 Node 节点和要存储的 Node 节点不相同，且当前节点不是 TreeNode 类型，那么就要遍历当前节点的链表。直到将这个链表的节点遍历完为止。(也就是将值插入到链表的最后位置，尾插法)
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); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 让指针位置后移 }这里一直找当前节点的下一个； 如果下一个为空，那么就将要存储的节点插入到当前节点所处在的链表中。 如果当前节点的链表下一个不为空，那么还是执行与上面同样的比较。
这个过程可以使用流程图来描述一下，更加形象。 根据上面的流程图，我们大概知道了，HashMap 的存储结构应该是这个样子（在未树化之前）
上面我们说到了树化，也就是如果 Node 是 TreeNode 的实例时，会调用 TreeNode 这个对象的 putTreeVal 方法。 同时在遍历 Node 链表时，也会判断当前这个节点的长度到达树化的阈值时，会调用 treeifyBin 这个方法将链表树化。 存值的过程我们先不管，先看看 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) //当数组的长度为空或者数组的长度 < 64 的时候，会调用 resize 方法进行扩容 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); } }通过 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 和前面我们分析代码来看树化需要两个条件
数组中元素下面的链表节点数必须要 >= 8 才能树化数组的长度需要大于 64，如果你的长度小于 64，hashMap 会优先选择先扩容。 只有满足了上述的两个要求，tab 数组才会树化。为什么当数组容量 >= 64 时才树化？因为当 table 数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。
关于树化的过程我看的还不是很明白，这里先留个坑吧。等我看明白树化的过程了再补上这个坑。
虽然树化的过程没有梳理出来，但是对于第二个问题我们确是可以回答了。 jdk1.8 的存储结果是使用 数组 + 链表 + 红黑树来进行存储的。当数组中元素下面的链表节点数大于 8 时，并且数组的长度大于等于 64，如果数组的长度小于 64，hashMap 会优先选择先扩容。
