JDK8对HashMap的底层代码有进行优化，在原来的数组+链表的组合结构上，添加了红黑树的支持，提升了HashMap对数据操作的性能。就想看看其内部的大致实现，当然对网上很多关于hashmap的技术分享也进行参考和学习，还是挺有收获的，在此将自己对HashMap的理解做个笔记，仅供参考。。。
HashMap
由于JDK8中对HashMap进行了优化，主要就是在原来数组+链表的结构组合上，加上了树这种数据结构，具体就是在hashmpa的数据添加中，当链到达一定数量后，就会对链进行树形转化,转化成红黑树。
HashMap核心属性说明
一个类的属性，通常就是对象数据保存的容器，对象操作方法与这些属性密切相关，先大致弄清楚这些属性的含义，对方法的源代码理解会有帮助。
- HashMap存储键值对的容器
通过HashMap的源代码和我们对它的组成结构数组+链表+树可以知道，必然有一个数组，数组中存放的是链表节点，还可能会有树节点的结构表示:
//存放元数据的容器，数组
transient Node<K,V>[] table;
数组表示存放相同结构元素的容器，从上可知，存放的数据类型是Node,结合HashMap组合结构和源代码可知，这是表示链表节点的结构:
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;
}
....//省略
}
从结构可以看出，链上节点中包含4个属性：HashMap存储的key值、value值、key值生成的hash值、还有指向下一个节点的next对象。每个字段都有本身存在的意义和作用，其中：
-
key/value分别就是在使用hashmap存入的键值对数据。 -
next对象则是单向链表组成的基本元素，表示当前节点连接的下一个节点。 -
hash字段的值，是根据hash(key)方法生成的整数，表示当前节点的哈希标记，用于定位保存key为键的对象所存放的数组位置和在调用get方法根据键key快捷查找节点。
并且，可以知道，创建一个链表节点需要的几个参数：节点的键值对和该节点哈希值、指向的下一个节点对象。
在JDK8,HashMap中还存在树形结构,当单链表过长(多少才叫长？)的时候，转换成树结构：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
....//
}
因为HashMap使用的是红黑树，该红黑树会在后续介绍，先要知道树通常最简单的二叉树，包含三个节点：父节点、左子树节点、右子树节点。红黑树在基本的树结构上，加了表示节点红黑颜色的boolean字段read。
- 存储数据默认初始化大小和最大容量
既然知道了HashMap是由三大数据结构，那么针对数组是否有最大值、最小值的限定？真的单条链表是否对节点有长度限定？真的红黑树结构上的节点是否也有最大值、最小值限定？
针对数组长度最大值最小值限定,可以看到默认数组长度是16，最大值是2的32次方。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
- 与HashMap数据容器扩容相关属性
HashMap重新扩容也是很重要的一步，那什么时候数组需要扩容，依据的条件什么？扩容规则是什么？扩容对之前旧位置上的节点会有影响么？
transient int size;
int threshold;
final float loadFactor;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
这里有个负载因子字段，用于与当前数组容器大小相乘得到阀值=数组长度x负载因子。边界值就是这个阀值，当当前数组容器中保存的节点数量大于该阀值就会进行扩容。
也就是代码中size * loadFactor与threshold比较大小。默认负载因子是0.75。也就是默认当数组保存节点数量大于16 * 0.75=12的时候，数组容器就要进行扩容。扩容规则就是：容器长度扩充一倍。
- 数据容器链表转换成树相关属性
针对单向链表和树互相转换边界,即为限定，当由于hash值散列不均，造成单条链表过长达到多长的时候，需要转换成红黑树。
当单条链表长度超过8个节点的时候，就转换成红黑树结构，当红黑树节点小于6个节点的时候，就要转成链表。
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
还有个参数，表示满足进行树形转换时，当前数组容量大小需要大于64才能进行，不然，需要通过resize方法扩容，并对之前数组上所有节点进行重新位置排列。
HashMap大致结构组成：
HashMap常用方法详解
容器的常规操作也就是增删改查了。
-
新增键值对:
主要流程就是：
- 根据对键值进行hash计算得到存放数组位置下标。
- 判断指定下标位置数组内容是否为空，为空创建节点并存放在当前位置。成功添加返回
- 若是指定下标位置存在节点，则继续判断节点是
链表还是树结构 - 若是树节点，则走添加树节点方法
putTreeVal - 若是链表，则遍历链表，在链尾增加节点，并判断节点数，是否需要
树形转换。 - 若是添加的节点值已经存在，则替换成新节点值，返回旧节点值。
- 若是在添加后有删除数组头节点需求，则可以重写protected方法
afterNodeInsertion。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//针对键值进行hash算法处理，得到代表该节点哈希属性的哈希值
//该哈希值在定位和比较查询过程中均有重要作用
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1. 若是容器未进行初始化，则进行初始化，初始大小为16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2. 若是指定位置数组内未存放数据，则保存改数据到此处
//定位位置是通过tab[i = (n - 1) & hash]来的
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//3. 容器已经初始化并且数组位置已经存有数据
Node<K,V> e; K k;
//3.1 若是添加节点数据和tab[(n - 1) & hash]出相等，则替换成新值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//3.2 若是所在链上已经是红黑树结构，则调用树添加节点规则
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//3.3 添加节点在链表上，则遍历查看是否匹配，未匹配则添加节点
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;
}
}
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;
}
关于hash计算方法图解，如下图：参考自美团点评技术团队-Java 8系列之重新认识HashMap
在链表节点的添加过程中，若是达到满足转成红黑树的条件(
数组容量大于64并且链表节点树大于8)，则需要调用方法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 {
// e代表的是哈希表中指定桶位置里链表节点，即为遍历的第一个节点
// 要进行树形化，先要创建树节点，内容与传入的e节点值一样
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);//该方法内会将上面维护的双向链表节点转换成真正树形结构
}
}
// For treeifyBin 新建树节点，由于链表节点和树节点属性值差不多，直接使用
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
关于上述红黑树节点的添加，详情可以参考:HashMap 在 JDK 1.8 中新增的操作： 红黑树中添加元素 putTreeVal
添加元素流程图，如下图：参考美团点评技术团队-Java 8系列之重新认识HashMap
-
根据键值查找节点:
因为添加节点会初见三种情况：直接保存在桶位置、保存在链表链尾、保存在树中。所以查询时候也会根据判断，在三种结构上进行遍历查找。
如何判定是同一个节点？要根据节点的哈希值属性+key值即可快速匹配。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//根据计算键值的哈希值来查找
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//首先查找桶位置上的头节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//若是桶位置头节点不匹配，则遍历桶上的结构
//若是树形结构，则按照树的遍历规则查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//若是链表结构，则是更为简单的遍历查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
比较复杂的就是在红黑树上的节点查找，也就是上面方法getTreeNode。
可以大致看看源代码，也就是从根节点在红黑树上根据哈希值和值对象来查找：
因为红黑树是一种弱平衡的有序二叉树，有序有序说明要根据节点的关键字进行排序，关键字就是每个节点中存储的hash值，直接根据查找对象的hash值来快速进行类似递归式的二分查找来匹配元素：
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//根据节点的哈希值判断是查找左子树还是右子树
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
-
扩容操作:
在JDK8针对HashMap的扩容还是有点意思的。什么时候进行扩容？扩容规则？扩容影响?
扩容方法就是resize，也就是对数组进行加长。通常都是加长一倍，在容器初始化和容器内节点量大于阀值的时候就会扩容。扩容后，会对旧容器的所有节点进行重置，按照一定规则判断节点是保留还是移动存放。扩容基于写时复制思想，会新建一个容量的新数组，在把旧数组节点遍历处理到新数组上。
在扩容后，旧节点位置有两种可能：判断规则是(e.hash & oldCap) == 0
a. 保持位置不变的移动到新容器中
b. 移动到新数组位置[原数组下标+原数组容量]位置。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//扩容一倍(无符号左移1位，即x2)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//阀值也要跟着改变
newThr = oldThr << 1; // double threshold
}
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 { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//对链表上节点遍历处理
next = e.next;
//若是链表节点的hash值与旧容器大小相与为0，则位置保持不变的存放在新数组位置，反之存放在新数组下标[原数组下标+原数组容量]位置上
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);
// 原索引放到新的bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到新的bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
关于原节点位置索引变化规则，可以参考下面两张图(图片来自：美团点评技术团队):
其中，图(a)表示扩容前key1和key2两种key确定索引位置的事例;
图(b)表示扩容后key1和key2两者key确定索引实例，其中hash1是key1的hashcode高16位与底16位的异或运算结果:
在扩容重新计算hash之后，因为n变成2倍，那么
n-1的mask范围在高位多1位(红色)，因此新的节点位置索引就是[原索引位置+原容量大小],这也就解释得通，为什么在判断节点是否需要变换位置的时候是通过n & hash是否等于0来决定了。(也就是仅仅判断图b上key2对应第五位上是否是1)关于上述红黑树节点的拆分，详情可以参考:HashMap 在 JDK 1.8 中新增的操作： 树形结构修剪 split
主要的新增、删除、修改操作大致流程：
- 确定起始头节点也就是桶位置的节点
- 桶位置节点不为null并且新处理的节点与头节点匹配、之间简单操作
- 新处理节点与桶节点不匹配，遍历树TreeNode或者链表Node进行处理。
- 处理完成修改容量、修改次数、重新调整结构。
红黑树
- 什么是红黑树？
红黑树本质上是一种自平衡二叉查找树，但是它在二叉查找树基础上额外添加了颜色标记(红与黑)，同时制定一些符合红黑树的规则，这些规则保证了红黑树的弱平衡：在插入、删除、查找的最坏时间复杂度都是O(logn)。
从定义大概可以知道几点：
为什么说是自平衡?如何实现自平衡?
平衡是相对排序作为前提的，即红黑树也是有序二叉查找树，二叉说明红黑树树结构至多只有2个子树(左子树和右子树)。弱平衡是相比AVL而言的，自平衡意味着：当添加和删除节点不满足红黑树要求的时候，会通过左旋和右旋来操作节点使得树还是红黑树。-
红黑树有什么性质和要求？
1. 每个节点都是有色的，要么红色要么黑色。 2. 根节点永远是黑色的。 3. 所有的叶节点都是黑色的。(注意在不同场景下，对叶子节点定义的不同) 4. 每个红色节点的两个子节点一定都是黑色的。 5. 从任一节点到其子树中每个节点的路径都包含相同数量的黑色节点。 红黑树生成的目地是？解决什么问题？
那么为什么要定义红黑树，因为该算法在最坏情况下的运行时间也是非常良好的，并且在实践中是高效的：可以在O(logN)时间复杂度内做查找，插入和删除。(其中N为树中节点数目),就是提高有序二叉树的查找、删除、添加效率。
为什么HashMap要使用红黑树?
因为传统HashMap底层是使用数组+链表方式存储数据，并且是使用链接法来解决hash冲突的，会导致出现一种最坏情况:
当哈希表由于多次碰撞，导致单个桶上的链表个数无限增长，那么对该map的查找的时间复杂度就是O(n)了,为了尽可能的提高查找效率，新引入了红黑树结构来提升性能，因为该算法的查找的最坏时间复杂度是O(logn)，显然的O(logn) < O(n)，带来的代价就是：
需要维护链表和红黑树的转换，和本身红黑树在新增、删除节点时候带来的结构调整左旋和右旋等开销。-
红黑树有那些常规操作，在HashMap源代码中是如何体现的?
针对红黑树在HashMap底层结构如何关联的，在上述代码已经表述清楚。这里，主要看看红黑树自平衡的左旋和右旋节点操作实现:HashMap中针对指定节点左旋和右旋操作源代码如下：(最好方式结合图看源代码)
针对节点X:
红黑树左旋右旋.png
a. 左旋
针对节点X的左旋，按照代码步骤在图中做出标注:先不考虑节点颜色，关注点在于节点的调整，且没有将图细化出节点的双向关系，仅仅是单向。
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//入参p相当于上图的节点X,对X进行左旋
//r相当于上图节点Y
if (p != null && (r = p.right) != null) {
//第一步X1：若是Y左子树不为空,获取Y的左子树节点B，赋值给X的右子树
if ((rl = p.right = r.left) != null)
rl.parent = p; //设置Y左子树B的父节点是X
//第二步X2: 将X的父节点ROOT赋值给Y的父节点
if ((pp = r.parent = p.parent) == null)
//若是X没有父节点，设置Y成父节点，并设置其颜色黑色(树根一定是黑色)
(root = r).red = false;
else if (pp.left == p) //若是X是父节点ROOT的左子树
pp.left = r; //那么把父节点ROOT的左子树设置成Y
else
pp.right = r; //那么把父节点ROOT的右子树子树设置成Y
r.left = p; //第三步X3: 将X赋值给Y的左子树
p.parent = r; //设置X的父节点是Y
}
return root;
}
b. 右旋
针对节点Y的右旋，按照代码步骤在图中做出标注:先不考虑节点颜色，关注点在于节点的调整，没有提现出父节点指向的链。
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//P节点相当于上图的节点Y，针对Y进行右旋
//如果节点Y不为空，左子树不为空,l相当于节点X
if (p != null && (l = p.left) != null) {
//Y1: 将节点X的右子树赋值给Y的左子树
if ((lr = p.left = l.right) != null)
lr.parent = p; //节点X的右子树的父节点为节点Y
//Y2: 将节点Y的父节点赋值给节点X
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;//若是Y无父节点，设置父节点为X颜色黑色
else if (pp.right == p)//Y节点为ROOT的右子树
pp.right = l;//赋值节点X为ROOT右子树
else
pp.left = l;//赋值节点X为ROOT左子树
l.right = p; //Y3: 设置节点X的右子树为节点Y
p.parent = l;//节点Y的父节点设置为X
}
return root;
}
关于红黑树的节点操作，在TreeMap中更能提现出来，包括红黑树的左右旋转，为了满足红黑树条件而及进行的重新着色再次不做详解，改天心血来潮再做研究。
更多详细说明，可以参考:重温数据结构：深入理解红黑树
并发
为什么说hashmap是线程不安全的?
由HashMap的源代码中可以看到，内部并未涉及到并发相关的关键字synchronized,volatile,原子性类，并且自己编写多线程对同一个map对象实例进行操作旧可以看到结果。如何保证Map的线程安全有那些实现?有什么区别?
可以通过Collections.synchronizedMap方法来保证一个map的线程安全性。该方法内部是创建一个SynchronizedMap类,通过synchronized机制在每个方法内通过一个公共对象进行加锁，会造成map对象级别的阻塞。
ConcurrentHashMap底层还是基于HashMap的，锁机制也是synchronized来实现，只是颗粒级别不同，ConcurrentHashMap是分段锁，针对每个桶进行加锁，当多个线程可以同时访问操作同一个map上的不同桶节点。实现读操作的完全并行，写操作一定程度上的并行(不同的线程写入不同的桶数据)。并且，与SynchronizedMap不同，针对多线程一个读，一个写同一个map对象时候，ConcurrentHashMap不会抛出java.util.ConcurrentModificationException异常。
常见问题（参考网络）
- HashMap原理，内部数据结构？
底层使用哈希表(数组+链表),当链表过长的时候，会转换成红黑树实现O(logn)时间复杂度查找。
2.讲一下HashMap中put方法过程?
a. 对key求hash值，然后再计算索引下标
b. 如果没有碰撞，直接放入桶中
c. 如果有碰撞，以链表方式连接到尾部
d. 如果链表长度超过阀值(TREEIFY_THRESHOLD=8 && capicity > 64),就把链表转成红黑树
e. 如果节点已经存在就替换原值
f. 如果桶满了(capicityx负载因子)，就需要resize扩容
HashMap中hash函数是如何实现的？还有那些hash实现方式?
a. 将key的hashcode值高16位与hashcode值低16位进行异或操作
b. 通过(n-1) & hash 得到桶索引值HashMap怎样解决冲突，讲一下扩容过程，加入一个值在原数组中，现在移动到新数组，位置是如何改变的？
a. 将新节点加到链表尾部
b. 容量扩充为原来的2倍，然后对每个节点重新重新计算哈希值。
c. 原节点保持原索引位置不变或者移动到新数组索引[原索引+原容量]位置处。抛开HashMap，hash冲突有那些解决办法？
a. 开放定址法:放弃冲突位置，寻找新位置插入，所有元素都存放在hash表中。也就是说，散列表中的每一个位置要么有元素，要么没元素。参考:散列表之开放定址法
b. 链地址法(链接法): 当通过哈希函数处理发现元素都映射到同一个位置，则可以将新节点链接到之前存在节点后，形成链表，就是链接法。参考：散列表之链接法针对hashmap中某个Entry链太长，查找的时间复杂度可能达到O(n)，如何优化？
将链表转换成红黑树，JDK8中已经实现。
参考：
