HashMap源码分析
HashMap是Java中常用的key-value集合实现类，实现了Map接口。
数据结构
核心:
- 整体是一个数组；
- 数组每个位置是一个链表(或红黑树)；
- 链表每个节点中的Value即我们存储的Object；
JDK 1.7
数据结构
- 数组+链表
核心属性
核心方法
put方法
核心扩容机制
JDK 1.8
数据结构
- 数组+链表+红黑树
核心属性
核心方法
put方法
核心扩容
JDK1.7和JDK1.8的区别
-
最重要的一点是底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构;
-
jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容;
-
插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插；
-
jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀；
-
扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序，因此1.8避免了并发死循环的问题；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前；
-
jdk1.8是扩容时通过hash&cap= 0和 hash&cap = 1将链表分散，无需改变hash值，扩容到新表只有两个位置，一组(loHead->loTail)是原索引位置，另一组是原索引+旧数组长度的新索引位置(hiHead->hiTail)，而1.7是通过更新hashSeed来修改hash值每个元素重新计算索引达到分散的目的；
-
扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。
ConcurrHashMap
JDK 1.7
数据结构
ConcurrentHashMap在初始化时会要求初始化concurrencyLevel作为segment数组长度，即并发度，代表最多有多少个线程可以同时操作ConcurrentHashMap,默认是16，每个segment片段里面含有键值对HashEntry数组，是真正存放键值对的地方。这就是ConcurrentHashMap的数据结构。
核心属性
//默认的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认的并发度，也就是默认的Segment数组长度
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//最大容量，ConcurrentMap最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//每个segment中table数组的长度,必须是2^n,最小为2
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
//允许最大segment数量,用于限定concurrencyLevel的边界,必须是2^n
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
//非锁定情况下调用size和contains方法的重试次数,避免由于table连续被修改导致无限重试
static final int RETRIES_BEFORE_LOCK = 2;
//计算segment位置的掩码值
final int segmentMask;
//用于计算算segment位置时,hash参与运算的位数
final int segmentShift;
//segmentMask 和 segmentShift作用主要是根据key的hash值做计算定位在哪个Segment片段。
//Segment数组
final Segment<K,V>[] segments;
Segment介绍
【分段锁】继承于重入锁ReentrantLock，要想访问Segment片段，线程必须获得同步锁
static final class Segment<K,V> extends ReentrantLock implements Serializable {
//尝试获取锁的最多尝试次数，即自旋次数
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
//HashEntry数组，也就是键值对数组，volatile修饰，线程可见性
transient volatile HashEntry<K, V>[] table;
//元素的个数
transient int count;
//segment中发生改变元素的操作的次数，如put/remove
transient int modCount;
//当table大小超过阈值时,对table进行扩容,值为capacity *loadFactor
transient int threshold;
//加载因子
final float loadFactor;
Segment(float lf, int threshold, HashEntry<K, V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
}
核心方法
put方法
- 计算 key 的 hash 值
- 根据 hash 值找到 Segment 数组中的位置 j
- 插入新值到 槽 s 中
Segment初始化的时候只初始化了0位置上的数据，其余Segment用到了再进行初始化，通过延时加载的策略，而延迟加载调用的就是ensureSegment方法
private Segment<K,V> ensureSegment(int k) {
//获取当前的segments数组
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
//按照segment[0]的HashEntry数组长度和加载因子初始化Segment[k]
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// 使用当前 segment[0] 处的数组长度和负载因子来初始化 segment[k]，这就是之前要初始化 segment[0] 的原因。
// 为什么要用 " 当前 "，因为 segment[0] 可能早就扩容过了。
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
//再次检查一遍该槽是否被其他线程初始化。
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
//unsafe保障内存可见性
// 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))//cas操作，原子性
break;
}
}
}
return seg;
}
get方法
get方法是不加锁的，Entry以volatile修饰，读取的都是最新变量。
size方法
扩容核心
private void rehash(HashEntry<K,V> node) {
// 记录老的table数组
HashEntry<K,V>[] oldTable = table;
// 记录老的容量
int oldCapacity = oldTable.length;
// 获取新数组的容量，之前的两倍
int newCapacity = oldCapacity << 1;
// 计算新的阀值
threshold = (int)(newCapacity * loadFactor);
// 创建新容量的HashEntry数组
HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
// 用来计算下标
int sizeMask = newCapacity - 1;
// 遍历老的table进行元素转移
for (int i = 0; i < oldCapacity ; i++) {
// 获取每个数组中的链表元素
HashEntry<K,V> e = oldTable[i];
// 为空就没啥东西转移的了
if (e != null) {
// 获取头节点的下一个节点
HashEntry<K,V> next = e.next;
// 计算下标
int idx = e.hash & sizeMask;
// 如果next == null，则表示链表元素只有一个
if (next == null)
// 直接把当前元素转移到新数组上面即可
newTable[idx] = e;
else {
// 如果不止一个就需要进行转移了
// 先把头节点赋值给lastRun，以及新数组中的下标
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
// 遍历每一个元素，找下标相同的元素，以最后一组为准
for (HashEntry<K,V> last = next; last != null; last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// 先把找到相同下标的元素转移过去
newTable[lastIdx] = lastRun;
// 再把lastRun之前的元素，分别放入新的元素
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
// 头插法
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 扩容完成还需要将新的元素添加到链表当中
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
// 把当前segment的table 更新成扩容后的元素
table = newTable;
}
扩容原理与HashMap 1.8 一样，只能有两个位置（原索引位置或原索引位置+旧数组长度），不同之处在于使用lastRun结点优化的好处，避免数据迁移时，lastRun结点及后边结点不必重新new出HashEntry对象到新数组，直接将lastRun结点引用传过去即可，如果lastRun结点是最后一个结点，那么此次优化就是多余的，但是极少是这种情况。
JDK 1.8
在JDK1.7版本上，ConcurrentHashMap还是通过分段锁来实现的，Segment的数量制约着并发量。在JDK1.8中，已经摒弃了这种结构设计，而是直接采用Node数组+链表+红黑树的结构来实现，同时并发控制使用Synchronized和CAS来操作。
核心属性
// node数组最大容量：2^30=1073741824
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认初始值，必须是2的幕数
private static final int DEFAULT_CAPACITY = 16;
//数组可能最大值，需要与toArray（）相关方法关联
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//并发级别，遗留下来的，为兼容以前的版本
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 负载因子
private static final float LOAD_FACTOR = 0.75f;
// 链表转红黑树阀值,> 8 链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//树转链表阀值，小于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
// 2^15-1，help resize的最大线程数
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 32-16=16，sizeCtl中记录size大小的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// forwarding nodes的hash值
static final int MOVED = -1;
// 树根节点的hash值
static final int TREEBIN = -2;
// ReservationNode的hash值
static final int RESERVED = -3;
// 可用处理器数量
static final int NCPU = Runtime.getRuntime().availableProcessors();
//存放node的数组
transient volatile Node<K,V>[] table;
/*控制标识符，用来控制table的初始化和扩容的操作，不同的值有不同的含义
*当为负数时：-1代表正在初始化，-N代表有N-1个线程正在 进行扩容
*当为0时：代表当时的table还没有被初始化
*当为正数时：表示初始化或者下一次进行扩容的大小
*/
private transient volatile int sizeCtl;
数据结构
- 数组+链表+红黑树
核心方法
put方法
1.如果没有初始化就先调用initTable（）来初始化
2.若没有hash冲突就直接CAS插入
3.若正在扩容则先进行扩容
4.若存在hash冲突，则通过加锁来保证线程安全：链表就直接遍历到尾端插入：红黑树就旋转插入
5.如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
6.如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容
简单来讲，整个put主流程，解决了3个问题：初始化——>扩容——>数据迁移。
核心扩容
根据cpu核心数将数组划分不同的隔离的扩容区间，线程CAS争抢不同区间，加锁锁住头结点，与ConcurrentHashMap 1.7扩容机制(lastRun)一样，扩容成功后标记结点为forwarding结点，hash值为-1，代表此位置已经扩容完成。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// stride 在单核下直接等于 n，多核模式下为 (n>>>3)/NCPU，最小值是 16，小于16就强制16
// stride 可以理解为”步长“，有 n 个位置是需要进行迁移的，
// 将这 n 个任务分为多个任务包，每个任务包有 stride 个任务
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果 nextTab 为 null，先进行一次初始化
// 前面我们说了，外围会保证第一个发起迁移的线程调用此方法时，参数 nextTab 为 null
// 之后参与迁移的线程调用此方法时，nextTab 不会为 null
if (nextTab == null) {
try {
// 容量翻倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
// nextTable 是 ConcurrentHashMap 中的属性
nextTable = nextTab;
// transferIndex 也是 ConcurrentHashMap 的属性，用于控制迁移的位置
transferIndex = n;
}
int nextn = nextTab.length;
// ForwardingNode 翻译过来就是正在被迁移的 Node
// 这个构造方法会生成一个Node，key、value 和 next 都为 null，关键是 hash 为 MOVED
// 后面我们会看到，原数组中位置 i 处的节点完成迁移工作后，就会将位置 i 处设置为这个 ForwardingNode，用来告诉其他线程该位置已经处理过了，所以它其实相当于是一个标志。（fwd的hash值为-1，fwd.nextTable=nextTab）
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// advance =true指的是做完了一个位置的迁移工作，可以准备做下一个位置的了
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
/*
* 下面这个 for 循环，最难理解的在前面，而要看懂它们，应该先看懂后面的，然后再倒回来看
*
*/
// i 是位置索引，bound 是边界，注意是从后往前
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// advance 为 true 表示可以进行下一个位置的迁移了
// 控制 --i ,遍历原hash表中的节点。简单理解：i 指向了 transferIndex，bound 指向了 transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
// 将 transferIndex 值赋给 nextIndex，这里 transferIndex 一旦小于等于 0，说明原数组的所有位置都有相应的线程去处理了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//用CAS计算得到的transferIndex
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
// 看括号中的代码，nextBound 是这次迁移任务的边界，注意，是从后往前
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// 所有的迁移操作已经完成
nextTable = null;
// 将新的 nextTab 赋值给 table 属性，完成迁移
table = nextTab;
// 重新计算 sizeCtl：n 是原数组长度，所以 sizeCtl 得出的值将是新数组长度的 0.75 倍
sizeCtl = (n << 1) - (n >>> 1);
return;//跳出死循环
}
// 之前我们说过，sizeCtl 在迁移前会设置为 (rs << RESIZE_STAMP_SHIFT) + 2
// 然后，每有一个线程参与迁移就会将 sizeCtl 加 1，
// 这里使用 CAS 操作对 sizeCtl 进行减 1，代表做完了属于自己的任务，新加入一个线程参与到扩容操作
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 任务结束，方法退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 到这里，说明 (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT，
// 也就是说，所有的迁移任务都做完了，也就会进入到上面的 if(finishing){} 分支了
finishing = advance = true;
i = n; // recheck before commit
}
}
// f.hash == -1 表示遍历到了ForwardingNode节点，意味着该节点已经处理过了。这里是控制并发扩容的核心
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 该位置处是一个 ForwardingNode，代表该位置已经迁移过了
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 对数组该位置处的结点加锁，开始处理数组该位置处的迁移工作
synchronized (f) {
//节点复制工作
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// 表示是链表节点
if (fh >= 0) {
// 构造两个链表 一个是原链表 另一个是原链表的反序排列
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 在nextTable i 位置处插上链表
setTabAt(nextTab, i, ln);
// 在nextTable i + n 位置处插上链表
setTabAt(nextTab, i + n, hn);
// 在table i 位置处插上ForwardingNode 表示该节点已经处理过了，其他线程一旦看到该位置的 hash 值为 MOVED，就不会进行迁移了
setTabAt(tab, i, fwd);
// advance 设置为 true，代表该位置已经迁移完毕，可以执行--i动作，遍历节点
advance = true;
}
else if (f instanceof TreeBin) {
// 红黑树的迁移
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果一分为二后，节点数<=6，那么将红黑树转换回链表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
// 将 ln 放置在新数组的位置 i
setTabAt(nextTab, i, ln);
// 将 hn 放置在新数组的位置 i+n
setTabAt(nextTab, i + n, hn);
// 将原数组该位置处设置为 fwd，代表该位置已经处理完毕，
// 其他线程一旦看到该位置的 hash 值为 MOVED，就不会进行迁移了
setTabAt(tab, i, fwd);
// advance 设置为 true，代表该位置已经迁移完毕
advance = true;
}
}
}
}
}
}
这里对并发操作的机制做一个解释，原数组长度为n，意味着就有n个迁移任务。最简单的就是让每一个线程每次负责一个小任务。做完一个任务在检测是否有其他没做完的任务，然后就可以帮助迁移了。Doug Lea 使用了一个 stride，简单理解就是步长，每个线程每次负责迁移其中的一部分，比方说每次迁移 16 个小任务。所以，我们就需要一个全局的调度者来安排哪个线程执行哪几个任务，这个就是属性 transferIndex 的作用。
第一个发起数据迁移的线程会将 transferIndex 指向原数组最后的位置，然后从后往前的 stride 个任务属于第一个线程，然后将 transferIndex 指向新的位置，再往前的 stride 个任务属于第二个线程，依此类推。当然，这里说的第二个线程不是真的一定指代了第二个线程，也可以是同一个线程。其实就是将一个大的迁移任务分为了一个个任务包。
说到底，transfer 这个方法并没有实现所有的迁移任务，每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作，其他的需要由外围来控制。
get方法
get操作从来都是最简单的，简单概括一下：
1.计算hash值，定位到该table索引位置，如果是首节点符合就返回
2.根据 hash 值找到数组对应位置: (n – 1) & h
3.根据该位置处结点性质进行相应查找 ：如果该位置为 null，那么直接返回 null 就可以了；如果该位置处的节点刚好就是我们需要的，返回该节点的值即可；如果该位置节点的 hash 值小于 0，说明正在扩容，或者是红黑树，后面我们再介绍 find 方法；如果以上 3 条都不满足，那就是链表，进行遍历比对即可；
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 判断头结点是否就是我们需要的节点
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果头结点的 hash 小于 0，说明 正在扩容，或者该位置是红黑树
else if (eh < 0)
// 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
return (p = e.find(h, key)) != null ? p.val : null;
// 遍历链表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
size方法有个分布式累加器的概念，累加每个counter数组中的和即为size。
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a; //变化的数量
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
欢迎关注我的微信公众号，学习更多干货！
