【Java】一文掌握HashMap
HashMap作为Java面试八股常客，你真的理解了吗？它说难也不难，说简单也不简单。往简单了说就是数组+链表+红黑树，ConcurrentHashMap最多加了一些同步操作；往难了说，为什么选用红黑树，散列算法的细节，扩容细节等。不用怕，今天这篇文章，就从源码入手，彻底搞清楚HashMap，顺带也一起聊聊ConcurrentHashMap！
一句话介绍HashMap：
HashMap采用数组+链表+红黑树（jdk8新增）结构，put元素时，会先计算put对象的hashCode，然后根据hashCode找到对应的数组下标（桶的位置），如果发生hash冲突，即对应桶里已经存在其他元素，则会按照链表形势插入其后，当hash冲突达到一定数量，那么HashMap会将链表转为红黑树以提高查询效率。
初始化
1. 容量
HashMap在初始化时，如果未指定容量，则默认初始容量是16，即使手动指定初始容量，HashMap也会把数值转换为2的幂次方
容量设为2的幂次方的原因为了提高扩容效率，因为HashMap容量扩容是翻倍，保证是2的幂次方则只需要左移一位即可（可参考resize方法中的扩容逻辑）
/**
* 结果为>=cap的最小2的自然数幂
*/
static final int tableSizeFor(int cap) {
//先移位再或运算，最终保证返回值是2的整数幂
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2. 负载因子
如果未指定负载因子，那么HashMap的默认负载因子是0.75，负载因子用于HashMap扩容，当前键值对个数 >= HashMap最大容量*装填因子时，HashMap会进行rehash操作
负载因子，可以理解为数组扩容的触发点，0.75是基于泊松概率学得出的最佳负载点
- 负载因子过高（如1）：数组空间利用率高，hash冲突的情况增加，红黑树出现的几率增高
- 负载因子过低（如0.5）：hash冲突减少，但数组利用率不高，大部分数组位置都是空的
数据结构
/**
* 默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认装填因子0.75，如果当前键值对个数 >= HashMap最大容量*装填因子，进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* JDK1.8 新加，Entry链表最大长度，当桶中节点数目大于该长度时，将链表转成红黑树存储；
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* JDK1.8 新加，当桶中节点数小于该长度，将红黑树转为链表存储；
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶可能被转化为树形结构的最小容量。当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突。
* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
数据结构：
Node节点
当桶为链表结构时，数据结构如下
/**
* JDK1.6用Entry描述键值对，JDK1.8中用Node代替Entry
*/
static class Node<K, V> implements Map.Entry<K, V> {
// hash存储key的hashCode
final int hash;
// final:一个键值对的key不可改变
final K key;
V value;
//指向下个节点的引用
Node<K, V> next;
// ...
}
TreeNode节点
当桶转换为红黑树时，数据结构如下：
/**
* JDK1.8新增，用来支持桶的红黑树结构实现
* 性质1. 节点是红色或黑色。
* 性质2. 根是黑色。
* 性质3. 所有叶子都是黑色（叶子是NIL节点）。
* 性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
* 性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
*/
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
TreeNode<K, V> parent; //节点的父亲
TreeNode<K, V> left; //节点的左孩子
TreeNode<K, V> right; //节点的右孩子
TreeNode<K, V> prev; //节点的前一个节点
boolean red; //true表示红节点，false表示黑节点
}
接口实现
putVal方法
- 如果哈希表为空，调用resize()创建一个哈希表。
- 如果指定参数hash在表中没有对应的桶，即为没有碰撞，直接将键值对插入到哈希表中即可。
- 如果有碰撞，遍历桶，找到key映射的节点
- 桶中的第一个节点就匹配了，将桶中的第一个节点记录起来。
- 如果桶中的第一个节点没有匹配，且桶中结构为红黑树，则调用红黑树对应的方法插入键值对。
- 如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于等于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。
treeifyBin方法首先判断桶数组长度，若小于MIN_TREEIFY_CAPACITY（64），则进行扩容，反之才是转换红黑树
- 如果找到了key映射的节点，且节点不为null
- 记录节点的vlaue。
- 如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换。
- 返回记录下来的节点的value。
- 如果没有找到key映射的节点（2、3步中讲了，这种情况会插入到hashMap中），插入节点后size会加1，这时要检查size是否大于临界值threshold，如果大于会使用resize方法进行扩容。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// ...
}
resize方法
如果table为null，则对table进行初始化
如果对table扩容，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
resize的步骤总结为:
- 计算扩容后的容量，临界值。
- 将hashMap的临界值修改为扩容后的临界值。
- 根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组。
- 将旧数组的元素复制到table中。
final Node<K, V>[] resize() {
// ...
}
removeNode方法
Map.remove和相关方法的实现需要的方法
removeNode方法的步骤总结为:
- 如果数组table为空或key映射到的桶为空，返回null。
- 如果key映射到的桶上第一个node的就是要删除的node，记录下来。
- 如果桶内不止一个node，且桶内的结构为红黑树，记录key映射到的node。
- 桶内的结构不为红黑树，那么桶内的结构就肯定为链表，遍历链表，找到key映射到的node，记录下来。
- 如果被记录下来的node不为null，删除node，size-1被删除。
- 返回被删除的node。
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// ...
}
getNode方法
根据key的哈希值和key获取对应的节点 getNode可分为以下几个步骤：
- 如果哈希表为空，或key对应的桶为空，返回null
- 如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点。
- 如果桶中的第一个节点没有匹配上，而且有后续节点
- 如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
- 如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配
- 找到节点返回null，否则返回null。
final Node<K, V> getNode(int hash, Object key) {
// ...
}
hash算法
HashMap中键值对的存储形式为链表节点，hashCode相同的节点（位于同一个桶）用链表组织
hash方法分为三步:
- 取key的hashCode
- key的hashCode高16位异或低16位
- 将第一步和第二步得到的结果进行取模运算。
static final int hash(Object key) {
int h;
//计算key的hashCode, h = Objects.hashCode(key)
//h >>> 16表示对h无符号右移16位，高位补0，然后h与h >>> 16按位异或
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap的hash方法调用Object的hashCode，Object的hashCode则是JVM根据对象所在的内存地址锁计算出来的hash码
数组下标计算：
tab[i = (n - 1) & hash]
(n - 1) & hash 本质上是hash % n，位运算更快
扩容时机
- 数据数量达到阈值（threshold），在插数据时，如putVal/computIfAbsent/compute/merge方法
- 链表元素超过8个而触发红黑树转换时，若数组长度不足64，则不会转换红黑树，而是对数组进行扩容，在treeifyBin方法
红黑树
1. 为什么选用红黑树
平衡二叉树，二叉树的左右子节点的数量相对平衡
AVL树：高度平衡二叉树，保证所有节点的左右子树的高度差不超过1。在插入和删除的过程中，只要不满足条件，则会通过左旋或者右旋子树来保证二叉树的平衡。它的平衡度高，调整频率高，适用于查询多，插入删除少的场景
红黑树：弱平衡二叉树，其他和AVL树大致相同，但它只保证根到叶子的最长路径不会超过最短路径的2倍。它的平衡度低，调整频率低，适用于插入删除多的场景
综上所述，HashMap采用红黑树作为数据结构存储
2. 变色规则
当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）：
（1）把父节点设为黑色
（2）把叔叔也设为黑色
（3）把祖父也就是父亲的父亲设为红色（爷爷）
（4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则
可归结为三步：
（1）把父节点一层的两个节点都变黑色
（2）把父节点的父节点，也就是整个子树的根节点变为红色
（3）把子树的根节点左旋转变化
如以下例子，在下面的红黑树中插入数字6，插入节点设为红色，找到它的父节点7，然后开始插入，插入之后，它的父层级的7和13都变成了黑色，而父层级的根节点12变成了红色
3. 旋转规则
左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。
（1）把父结点旋转
右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。
（1）把父节点变为黑色
（2）把祖父结点变为红色（爷爷）
（3）把祖父结点旋转（爷爷）
4. 红黑树的使用
- 在putVal方法中，若节点为红黑树，则调用TreeNode的putTreeVal方法
- 在removeNode方法中，若节点为红黑树，则调用TreeNode的removeTreeNode方法
- 在get方法中，若节点为红黑树，则调用TreeNode的find方法
- 其他结构如TreeMap、TreeSet，均采用红黑树实现
ConcurrentHashMap
既然说到了HashMap，那我们也就捎带聊聊ConcurrentHashMap。
HashMap线程不安全，要使用线程安全Map，要使用ConcurrentHashMap
当然了，你要用HashTable我也没意见，如果你能忍受它的任何操作都是synchronized的话。现在面试还问HashTable的，我是真的不能理解[狗头]
ConcurrentHashMap的存储结构和HashMap相同
DCL初始化数组
ConcurrentHashMap的数组是懒加载模式，即put时才会初始化，因此，数组是通过DCL（double check lock）的模式来保证线程安全的初始化数组
/**
* 存放node的数组,大小是2的幂次方
*/
transient volatile Node<K, V>[] table;
private final Node<K, V>[] initTable() {
Node<K, V>[] tab;
int sc;
// 判断数组是否初始化
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
// 有其他线程在初始化，这里让出CPU时间片等待
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// 成功将SIZECTL设置为-1
try {
// 再次判断数组是否初始化
if ((tab = table) == null || tab.length == 0) {
// 设置数组初始长度，默认16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
table = tab = nt;
// 设置下次扩容长度
sc = n - (n >>> 2);
// << 代表左移 >> 代表右移 <<< 代表无符号左移 >>> 代表无符号右移
// 向右移动两位
// 00000000 00000000 00000000 00010000 = 16
// 00000000 00000000 00000000 00000100 = 4
// 下次扩容长度 = 16-4 = 12
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
其中SIZECTL是ConcurrentHashMap的数组初始化和扩容的标识：
- SIZECTL==-1：当前数组正在初始化
- SIZECTL<-1：当前数组正在扩容
- SIZECTL==0：ConcurrentHashMap仅仅new出来
- SIZECTL>0：数组下次扩容的阈值或构造方法传入了初始化的容量
hash算法
ConcurrentHashMap和HashMap的hash算法略有不同，ConcurrentHashMap计算hash时计算了两次hash，让分布更均匀，以减少hash冲突
(h ^ (h >>> 16)) & HASH_BITS
第一步的位移和异或运算和HashMap一样，是为了尽可能的分布均匀，第二步的HASH_BITS为0x7fffffff，即Integer的最大值，做与运算的目的是为了让结果保证为正数
因为ConcurrentHashMap定义了三种负数的特殊hash值
static final int MOVED = -1; // 代表当前数据在迁移（扩容）
static final int TREEBIN = -2; // 代表当前数据所指向是红黑树节点
static final int RESERVED = -3; // 代表当前为知已经被占，但还未赋值
putVal方法
putVal方法可以分为以下几步：
- 检查key/value是否为空，如果为空，则抛异常，否则进行2
- 进入for死循环，进行3
- 检查table是否初始化了，如果没有，则调用initTable()进行初始化然后进行 2，否则进行4
- 根据key的hash值计算出其应该在table中储存的位置i，取出table[i]的节点用f表示。
根据f的不同有如下三种情况：
- 如果table[i]==null(即该位置的节点为空，没有发生碰撞)，则利用CAS操作直接存储在该位置，如果CAS操作成功则退出死循环。
- 如果table[i]!=null(即该位置已经有其它节点，发生碰撞)，碰撞处理也有两种情况
- 检查table[i]的节点的hash是否等于MOVED，如果等于，则检测到正在扩容，则帮助其扩容
- 说明table[i]的节点的hash值不等于MOVED，如果table[i]为链表节点，则将此节点插入链表中即可，如果table[i]为树节点，则将此节点插入树中即可。插入成功后，进行 5
- 如果table[i]的节点是链表节点，则检查table的第i个位置的链表是否需要转化为树，如果需要则调用treeifyBin函数进行转化
结论：
- ConcurrentHashMap要插入到数组时，基于CAS保证线程安全
- ConcurrentHashMap要挂链表或红黑树下时，基于synchronized保证线程安全，锁指定数组位置的node对象（桶锁）
putVal和remove方法的同步方式大致相同，get方法和hashMap的get方法也大致相同，就不再赘述了
size方法
ConcurrentHashMap基于分段计数实现，基于CounterCell的value的CAS来记录个数
private final void addCount(long x, int check) {
CounterCell[] as;
long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a;
long v;
int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {
Node<K, V>[] tab, nt;
int n, sc;
while (s >= (long) (sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
} else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
扩容时机
- 数据数量达到阈值（threshold），在插数据时，在addCount方法
- 链表元素超过8个而触发红黑树转换时，若数组长度不足64，则不会转换红黑树，而是对数组进行扩容，在treeifyBin方法中调用tryPresize进行扩容
- putAll时，传入Map的长度经过运算如果大于阈值，也会扩容，会先进行tryPresize
最终的扩容方法是transfer
private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
// ...
}
其他Map
掌握这俩重点，其他Map大同小异了，都是根据自身特性增加额外的逻辑
LinkedHashMap：继承HashMap，内部新增一个双向链表结构，并复写了newNode方法，在创建节点时，把节点加入自己的链表结构
TreeMap：继承AbstractMap，以红黑树的结构实现key的有序排列
题外话
最好的学习方法，是看源码，只有掌握了作者的思路，才能真正掌握它；另外，看优秀作者的代码，学习优秀的思路，也是提升自身coding素质的重要途径！