2.9k 次阅读
ConcurrentHashMap源码分析_JDK1.8版本
文章均为本人技术笔记，转载请注明出处[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/
JDK1.6版本
ConcurrentHashMap结构
在JDK1.6中，ConcurrentHashMap将数据分成一段一段存储，给每一段数据配一把锁，当一个线程获得锁互斥访问一个段数据时，其他段的数据也可被其他线程访问；每个Segment拥有一把可重入锁，因此ConcurrentHashMap的分段锁数目即为Segment数组长度。ConcurrentHashMap结构：每一个segment都是一个HashEntry&K,V&[] table， table中的每一个元素本质上都是一个HashEntry的单向队列（单向链表实现）。每一个segment都是一个HashEntry&K,V&[] table， table中的每一个元素本质上都是一个HashEntry的单向队列。
锁分离实现
当一个线程访问Node/键值对数据时，必须获得与它对应的segment锁，其他线程可以访问其他Segment中的数据（锁分离）；
ConcurrentHashMap声明
public class ConcurrentHashMap&K,V& extends AbstractMap&K,V& implements ConcurrentMap&K,V&, Serializable
无锁算法：CAS
乐观锁与悲观锁
悲观锁比如synchronized锁，为确保其他线程不会干扰当前线程工作，因此挂起其他需要锁的线程，等待持有锁的线程释放；
乐观锁总是假设没有冲突发生去做操作，如果检测到冲突就失败重试，知道成功为止；
CAS(Compare And Swap)：CAS算法包含三个参数CAS(V, E, N)，判断预期值E和内存旧值是否相同(Compare)，如果相等用新值N覆盖旧值V(Swap)，否则失败；当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，其他线程失败（失败线程不会被阻塞，而是被告知“失败”，可以继续尝试）；CAS在硬件层面可以被编译为机器指令执行，因此性能高于基于锁占有方式实现线程安全；
ConcurrentHashMap结构图示
与JDK1.6对比
JDK 1.8取消类segments字段，直接用table数组存储键值对，JDK1.6中每个bucket中键值对组织方式是单向链表，查找复杂度是O(n)，JDK1.8中当链表长度超过TREEIFY_THRESHOLD时，链表转换为红黑树，查询复杂度可以降低到O(log n)，改进性能；
JDK1.8中，一个线程每次对一个桶（链表 or 红黑树）进行加锁，其他线程仍然可以访问其他桶；
ConcurrentHashMap底层数据结构与HashMap相同，仍然采用table数组+链表+红黑树结构；一个线程进行put/remove操作时，对桶（链表 or 红黑树）加上synchronized独占锁；ConcurrentHashMap采用CAS算法保证线程安全；
ConcurrentHashMap基本数据结构
transient volatile Node&K,V&[] table：键值对桶数组
private transient volatile Node&K,V&[] nextTable： rehash扩容时用到的新键值对数组
private transient volatile long baseCount：&span id = "jump1"&&/span&记录当前键值对总数，通过CAS更新，对所有线程可见
private transient volatile int sizeCtl
sizeCtl表示键值对总数阈值，通过CAS更新, 对所有线程可见
当sizeCtl & 0时，表示多个线程在等待扩容；
当sizeCtl = 0时，默认值；
当sizeCtl & 0时，表示扩容的阈值；
private transient volatile int cellBusy：自旋锁；
private transient volatile CounterCell[] counterCells: counter cell表，长度总为2的幂次；
static class Segment&K,V&：在JDK1.8中，Segment类仅仅在序列化和反序列化时发挥作用；
private transient KeySetView&K,V& keySet
private transient ValuesView&K,V& values
private transient EntrySetView&K,V& entrySet
描述键值对：Node&K, V&
static class Node&K,V& implements Map.Entry&K,V& {
// 键值对的value和next均为volatile类型
volatile V
volatile Node&K,V&
ConcurrentHashMap重要方法分析
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor & 0.0f) || initialCapacity & 0 || concurrencyLevel &= 0)
throw new IllegalArgumentException();
if (initialCapacity & concurrencyLevel)
// Use at least as many bins
initialCapacity = concurrencyL
// as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size &= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl =
该构造器会根据输入的initialCapacity确定一个 &= initialCapacity的最小2的次幂；
concurrentLevel：在JDK1.8之前本质是ConcurrentHashMap分段锁总数，表示同时更新ConcurrentHashMap且不产生锁竞争的最大线程数；在JDK1.8中，仅在构造器中确保初始容量&=concurrentLevel，为兼容旧版本而保留；
添加/更新键值对：putVal
putVal方法分析
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 不断CAS探测，如果其他线程正在修改tab，CAS尝试失败，直到成功为止
for (Node&K,V&[] tab =;) {
Node&K,V& int n, i,
// 空表，对tab进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
* CAS探测空桶
* 计算key所在bucket表中数组索引: i = (n - 1) & hash)
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// CAS添加新键值对
if (casTabAt(tab, i, null,
new Node&K,V&(hash, key, value, null)))
// no lock when adding to empty bin
// 检测到tab[i]桶正在进行rehash,
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
V oldVal =
// 对桶的首元素上锁独占
synchronized (f) {
if (tabAt(tab, i) == f) {
// 桶中键值对组织形式是链表
if (fh &= 0) {
binCount = 1;
for (Node&K,V& e =; ++binCount) {
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.
// 查找到对应键值对，更新值
if (!onlyIfAbsent)
// 桶中没有对应键值对，插入到链表尾部
Node&K,V& pred =
if ((e = e.next) == null) {
pred.next = new Node&K,V&(hash, key,
value, null);
// 桶中键值对组织形式是红黑树
else if (f instanceof TreeBin) {
binCount = 2;
if ((p = ((TreeBin&K,V&)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.
if (!onlyIfAbsent)
// 检查桶中键值对总数
if (binCount != 0) {
if (binCount &= TREEIFY_THRESHOLD)
// 链表转换为红黑树
treeifyBin(tab, i);
if (oldVal != null)
return oldV
// 更新baseCount
addCount(1L, binCount);
synchronized (f) {}操作通过对桶的首元素 = 链表表头 Or 红黑树根节点加锁，从而实现对整个桶进行加锁，有锁分离思想的体现；
获取键值对：get
public V get(Object key) {
Node&K,V&[] Node&K,V& e, int n, K
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)))
else if (eh & 0)
return (p = e.find(h, key)) != null ? p.val :
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
get方法通过CAS保证键值对的原子性，当tab[i]被锁住，CAS失败并不断重试，保证get不会出错；
删除键值对：remove
当baseCount超过sizeCtl，将table中所有bin内的键值对拷贝到nextTable；待补充；
helpTransfer
table原子操作方法
获取tab[i]：tabAt
static final &K,V& Node&K,V& tabAt(Node&K,V&[] tab, int i) {
return (Node&K,V&)U.getObjectVolatile(tab, ((long)i && ASHIFT) + ABASE);
tabAt方法原子读取table[i]；调用Unsafe对象的getObjectVolatile方法获取tab[i]，由于对volatile写操作happen-before于volatile读操作，因此其他线程对table的修改均对get读取可见；((long)i && ASHIFT) + ABASE)计算i元素的地址
CAS算法更新键值对：casTabAt
static final &K,V& boolean casTabAt(Node&K,V&[] tab, int i,
Node&K,V& c, Node&K,V& v) {
return U.compareAndSwapObject(tab, ((long)i && ASHIFT) + ABASE, c, v);
casTabAt通过compareAndSwapObject方法比较tabp[i]和v是否相等，相等就用c更新tab[i];
更新键值对：setTabAt
static final &K,V& void setTabAt(Node&K,V&[] tab, int i, Node&K,V& v) {
U.putObjectVolatile(tab, ((long)i && ASHIFT) + ABASE, v);
仅在synchronized同步块中被调用，更新键值对；
CAS更新baseCount
addCountaddCount
private final void addCount(long x, int check) {
CounterCell[] long b,
// s = b + x，完成baseCount++操作；
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
boolean uncontended =
if (as == null || (m = as.length - 1) & 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 多线程CAS发生失败时执行
fullAddCount(x, uncontended);
if (check &= 1)
s = sumCount();
if (check &= 0) {
Node&K,V&[] tab, int n,
// 当更新后的键值对总数baseCount &= 阈值sizeCtl时，进行rehash
while (s &= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) & MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sc & 0 表示其他线程已经在rehash
if (sc & 0) {
if ((sc &&& RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex &= 0)
// 其他线程的rehash操作已经完成，当前线程可以进行rehash
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
// sc &= 0 表示只有当前线程在进行rehash操作，调用辅助扩容方法transfer
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs && RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
addCount负责对baseCount + 1操作，CounterCell是Striped64类型，否则应对高并发问题；
fullAddCount
[1] 《Java并发编程的艺术》[2]
0 收藏&&|&&4
分享到微博？
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
各位，为什么省去了重新计算hash值 的时间？？
jdk1.7 以及jdk1.8 对于每一个元素 都只会计算一次hash值， 计算得到hash之后就将这个hash值放置到entry中，以后都不会再次计算。比如说下面的Node
： 那么文章重为什么说省去了计算hash值呢？
问题2： jdk1.7 和jdk1.8 中扩容 不同点在于，前者使用是hash值与数组长度-1 这个掩码进行与运算，得到Entry元素的新下标位置，得到的结果直接就是下标位置 ；
jdk1.8中是使用hash值与 数组长度
进行与运算，得到的是0 或者非零。如果是0 表示新位置下标不变，如果不是0那么表示位置有变动。
从这个表面上看，jdk1.7经过位运算之后能够直接获取到新位置下标； 而1.8 需要位运算，特殊情况下还需要加法运算，性能不是略差吗？我理解不对？
为什么很多地方都说后者jdk1.8 resize 有优化很多？？
1.8中 使用红黑树相对于链表只是提高了查找性能吧，在扩容方面有什么优化处理？
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
问题1 ：文章应该说明的有问题。并没有“省去了计算hash值“，如问题2的描述：
JDK7使用是hash值与数组长度-1 这个掩码进行与运算，得到Entry元素的新下标位置，得到的结果直接就是下标位置 ；Jdk1.8中是使用hash值与 数组长度 进行与运算，得到的是0 或者非零。如果是0表示新位置下标不变，如果不是0那么表示位置有变动，如果有变动下标位置是原位置加上数组长度。
从寻找新的下标位置上看，并没有省掉计算时间，反而附加一个加法运算。
问题2:LZ理解的没有问题。JDK8中resize方法并没有比JDK7中性能更好。Entry的key最坏的情况下在Map中是一个链表，JDK8为优化这个问题在链表数目大于8的时候转化为红黑树，但是resize中，又必需拆解和重建红黑树。
和普通的Entry链表一样，顺序遍历(此时只用它的next指针)，使用上述判断方式，分离成需要变动和不需要变动的两个列表。
如果列表长度小于8，去掉树结构指针，维持成一个链表如果列表长度大于8，重新构造成一棵树。总的来看，JDK7的resize时间复杂度n，JDK8的复杂度为nlog(n)
同步到新浪微博
分享到微博？
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。为了账号安全，请及时绑定邮箱和手机
点击这里，将文章分享到自己的动态
LinkedHashMap 源码详细分析（JDK1.8）
LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。所以，要看懂 LinkedHashMap 的源码，需要先看懂 HashMap 的源码。关于 HashMap 的源码分析，本文并不打算展开讲了。大家可以参考我之前的一篇文章“”。在那篇文章中，我配了十多张图帮助大家学习 HashMap 源码。
本篇文章的结构与我之前两篇关于 Java 集合类（）的源码分析文章不同，本文将不再分析集合类的基本操作（查找、遍历、插入、删除），而是把重点放在双向链表的维护上。包括链表的建立过程，删除节点的过程，以及访问顺序维护的过程等。好了，接下里开始分析吧。
上一章说了 LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表或红黑树组成，结构示意图大致如下：
LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。其结构可能如下图：
上图中，淡蓝色的箭头表示前驱引用，红色箭头表示后继引用。每当有新键值对节点插入，新节点最终会接在 tail 引用指向的节点后面。而 tail 引用则会移动到新的节点上，这样一个双向链表就建立起来了。
上面的结构并不是很难理解，虽然引入了红黑树，导致结构看起来略为复杂了一些。但大家完全可以忽略红黑树，而只关注链表结构本身。好了，接下来进入细节分析吧。
3. 源码分析
3.1 Entry 的继承体系
在对核心内容展开分析之前，这里先插队分析一下键值对节点的继承体系。先来看看继承体系结构图：
上面的继承体系乍一看还是有点复杂的，同时也有点让人迷惑。HashMap 的内部类 TreeNode 不继承它的了一个内部类 Node，却继承自 Node 的子类 LinkedHashMap 内部类 Entry。这里这样做是有一定原因的，这里先不说。先来简单说明一下上面的继承体系。LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node，并新增了两个引用，分别是 before 和 after。这两个引用的用途不难理解，也就是用于维护双向链表。同时，TreeNode 继承 LinkedHashMap 的内部类 Entry 后，就具备了和其他 Entry 一起组成链表的能力。但是这里需要大家考虑一个问题。当我们使用 HashMap 时，TreeNode 并不需要具备组成链表能力。如果继承 LinkedHashMap 内部类 Entry ，TreeNode 就多了两个用不到的引用，这样做不是会浪费空间吗？简单说明一下这个问题（水平有限，不保证完全正确），这里这么做确实会浪费空间，但与 TreeNode 通过继承获取的组成链表的能力相比，这点浪费是值得的。在 HashMap 的设计思路注释中，有这样一段话：
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins.
usages with well-distributed user hashCodes, tree bins are
rarely used.
大致的意思是 TreeNode 对象的大小约是普通 Node 对象的2倍，我们仅在桶（bin）中包含足够多的节点时再使用。当桶中的节点数量变少时（取决于删除和扩容），TreeNode 会被转成 Node。当用户实现的 hashCode 方法具有良好分布性时，树类型的桶将会很少被使用。
通过上面的注释，我们可以了解到。一般情况下，只要 hashCode 的实现不糟糕，Node 组成的链表很少会被转成由 TreeNode 组成的红黑树。也就是说 TreeNode 使用的并不多，浪费那点空间是可接受的。假如 TreeNode 机制继承自 Node 类，那么它要想具备组成链表的能力，就需要 Node 去继承 LinkedHashMap 的内部类 Entry。这个时候就得不偿失了，浪费很多空间去获取不一定用得到的能力。
说到这里，大家应该能明白节点类型的继承体系了。这里单独拿出来说一下，为下面的分析做铺垫。叙述略为啰嗦，见谅。
3.1 链表的建立过程
链表的建立过程是在插入键值对节点时开始的，初始情况下，让 LinkedHashMap 的 head 和 tail 引用同时指向新节点，链表就算建立起来了。随后不断有新节点插入，通过将新节点接在 tail 引用指向节点的后面，即可实现链表的更新。
Map 类型的集合类是通过 put(K,V) 方法插入键值对，LinkedHashMap 本身并没有覆写父类的 put 方法，而是直接使用了父类的实现。但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么，LinkedHashMap 是怎样建立链表的呢？在展开说明之前，我们先看一下 LinkedHashMap 插入操作相关的代码：
// HashMap 中实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
// HashMap 中实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node&K,V&[] Node&K,V& int n,
if ((tab = table) == null || (n = tab.length) == 0) {...}
// 通过节点 hash 定位节点所在的桶位置，并检测桶中是否包含节点引用
if ((p = tab[i = (n - 1) & hash]) == null) {...}
Node&K,V& K
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
else if (p instanceof TreeNode) {...}
// 遍历链表，并统计链表长度
for (int binCount = 0; ; ++binCount) {
// 未在单链表中找到要插入的节点，将新节点接在单链表的后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount &= TREEIFY_THRESHOLD - 1) {...}
// 插入的节点已经存在于单链表中
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
if (e != null) { // existing mapping for key
V oldValue = e.
if (!onlyIfAbsent || oldValue == null) {...}
afterNodeAccess(e);
// 回调方法，后续说明
return oldV
if (++size & threshold) {...}
afterNodeInsertion(evict);
// 回调方法，后续说明
// HashMap 中实现
Node&K,V& newNode(int hash, K key, V value, Node&K,V& next) {
return new Node&&(hash, key, value, next);
// LinkedHashMap 中覆写
Node&K,V& newNode(int hash, K key, V value, Node&K,V& e) {
LinkedHashMap.Entry&K,V& p =
new LinkedHashMap.Entry&K,V&(hash, key, value, e);
// 将 Entry 接在双向链表的尾部
linkNodeLast(p);
// LinkedHashMap 中实现
private void linkNodeLast(LinkedHashMap.Entry&K,V& p) {
LinkedHashMap.Entry&K,V& last =
// last 为 null，表明链表还未建立
if (last == null)
// 将新节点 p 接在链表尾部
p.before =
last.after =
上面就是 LinkedHashMap 插入相关的源码，这里省略了部分非关键的代码。我根据上面的代码，可以知道 LinkedHashMap 插入操作的调用过程。如下：
我把 newNode 方法红色背景标注了出来，这一步比较关键。LinkedHashMap 覆写了该方法。在这个方法中，LinkedHashMap 创建了 Entry，并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部，实现了双向链表的建立。双向链表建立之后，我们就可以按照插入顺序去遍历 LinkedHashMap，大家可以自己写点测试代码验证一下插入顺序。
以上就是 LinkedHashMap 维护插入顺序的相关分析。本节的最后，再额外补充一些东西。大家如果仔细看上面的代码的话，会发现有两个以after开头方法，在上文中没有被提及。在 JDK 1.8 HashMap 的源码中，相关的方法有3个：
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node&K,V& p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node&K,V& p) { }
根据这三个方法的注释可以看出，这些方法的用途是在增删查等操作后，通过回调的方式，让 LinkedHashMap 有机会做一些后置操作。上述三个方法的具体实现在 LinkedHashMap 中，本节先不分析这些实现，相关分析会在后续章节中进行。
3.2 链表节点的删除过程
与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现。在删除节点时，父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表，这不是它的职责。那么删除及节点后，被删除的节点该如何从双链表中移除呢？当然，办法还算是有的。上一节最后提到 HashMap 中三个回调方法运行 LinkedHashMap 对一些操作做出响应。所以，在删除及节点后，回调方法 afterNodeRemoval 会被调用。LinkedHashMap 覆写该方法，并在该方法中完成了移除被删除节点的操作。相关源码如下：
// HashMap 中实现
public V remove(Object key) {
return (e = removeNode(hash(key), key, null, false, true)) == null ?
// HashMap 中实现
final Node&K,V& removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node&K,V&[] Node&K,V& int n,
if ((tab = table) != null && (n = tab.length) & 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node&K,V& node = null, K V
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
else if ((e = p.next) != null) {
if (p instanceof TreeNode) {...}
// 遍历单链表，寻找要删除的节点，并赋值给 node 变量
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
} while ((e = e.next) != null);
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) {...}
// 将要删除的节点从单链表中移除
else if (node == p)
tab[index] = node.
p.next = node.
afterNodeRemoval(node);
// 调用删除回调方法进行后续操作
// LinkedHashMap 中覆写
void afterNodeRemoval(Node&K,V& e) { // unlink
LinkedHashMap.Entry&K,V& p =
(LinkedHashMap.Entry&K,V&)e, b = p.before, a = p.
// 将 p 节点的前驱后后继引用置空
p.before = p.after =
// b 为 null，表明 p 是头节点
if (b == null)
// a 为 null，表明 p 是尾节点
if (a == null)
a.before =
删除的过程并不复杂，上面这么多代码其实就做了三件事：
根据 hash 定位到桶位置
遍历链表或调用红黑树相关的删除方法
从 LinkedHashMap 维护的双链表中移除要删除的节点
举个例子说明一下，假如我们要删除下图键值为 3 的节点。
根据 hash 定位到该节点属于3号桶，然后在对3号桶保存的单链表进行遍历。找到要删除的节点后，先从单链表中移除该节点。如下：
然后再双向链表中移除该节点：
删除及相关修复过程并不复杂，结合上面的图片，大家应该很容易就能理解，这里就不多说了。
3.3 访问顺序的维护过程
前面说了插入顺序的实现，本节来讲讲访问顺序。默认情况下，LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap，指定 accessOrder 参数为 true，即可让它按访问顺序维护链表。访问顺序的原理上并不复杂，当我们调用get/getOrDefault/replace等方法时，只需要将这些方法访问的节点移动到链表的尾部即可。相应的源码如下：
// LinkedHashMap 中覆写
public V get(Object key) {
if ((e = getNode(hash(key), key)) == null)
// 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问节点移动到链表最后
if (accessOrder)
afterNodeAccess(e);
// LinkedHashMap 中覆写
void afterNodeAccess(Node&K,V& e) { // move node to last
LinkedHashMap.Entry&K,V&
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry&K,V& p =
(LinkedHashMap.Entry&K,V&)e, b = p.before, a = p.
// 如果 b 为 null，表明 p 为头节点
if (b == null)
if (a != null)
a.before =
* 这里存疑，父条件分支已经确保节点 e 不会是尾节点，
* 那么 e.after 必然不会为 null，不知道 else 分支有什么作用
if (last == null)
// 将 p 接在链表的最后
p.before =
last.after =
上面就是访问顺序的实现代码，并不复杂。下面举例演示一下，帮助大家理解。假设我们访问下图键值为3的节点，访问前结构为：
访问后，键值为3的节点将会被移动到双向链表的最后位置，其前驱和后继也会跟着更新。访问后的结构如下：
3.4 基于 LinkedHashMap 实现缓存
前面介绍了 LinkedHashMap 是如何维护插入和访问顺序的，大家对 LinkedHashMap 的原理应该有了一定的认识。本节我们来写一些代码实践一下，这里通过继承 LinkedHashMap 实现了一个简单的 LRU 策略的缓存。在写代码之前，先介绍一下前置知识。
在3.1节分析链表建立过程时，我故意忽略了部分源码分析。本节就把忽略的部分补上，先看源码吧：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry&K,V&
// 根据条件判断是否移除最近最少被访问的节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.
removeNode(hash(key), key, null, false, true);
// 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
protected boolean removeEldestEntry(Map.Entry&K,V& eldest) {
上面的源码的核心逻辑在一般情况下都不会被执行，所以之前并没有进行分析。上面的代码做的事情比较简单，就是通过一些条件，判断是否移除最近最少被访问的节点。看到这里，大家应该知道上面两个方法的用途了。当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。本节所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时，传入最大节点数。当插入的节点数超过最大节点数时，移除最近最少被访问的节点。实现代码如下：
public class SimpleCache&K, V& extends LinkedHashMap&K, V& {
private static final int MAX_NODE_NUM = 100;
public SimpleCache() {
this(MAX_NODE_NUM);
public SimpleCache(int limit) {
super(limit, 0.75f, true);
this.limit =
public V save(K key, V val) {
return put(key, val);
public V getOne(K key) {
return get(key);
public boolean exists(K key) {
return containsKey(key);
* 判断节点数是否超限
* @param eldest
* @return 超限返回 true，否则返回 false
protected boolean removeEldestEntry(Map.Entry&K, V& eldest) {
return size() &
测试代码如下：
public class SimpleCacheTest {
public void test() throws Exception {
SimpleCache&Integer, Integer& cache = new SimpleCache&&(3);
for (int i = 0; i & 10; i++) {
cache.save(i, i * i);
System.out.println("插入10个键值对后，缓存内容：");
System.out.println(cache + "\n");
System.out.println("访问键值为7的节点后，缓存内容：");
cache.getOne(7);
System.out.println(cache + "\n");
System.out.println("插入键值为1的键值对后，缓存内容：");
cache.save(1, 1);
System.out.println(cache);
测试结果如下：
在测试代码中，设定缓存大小为3。在向缓存中插入10个键值对后，只有最后3个被保存下来了，其他的都被移除了。然后通过访问键值为7的节点，使得该节点被移到双向链表的最后位置。当我们再次插入一个键值对时，键值为7的节点就不会被移除。
本节作为对前面内的补充，简单介绍了 LinkedHashMap 在其他方面的应用。本节内容及相关代码并不难理解，这里就不在赘述了。
本文从 LinkedHashMap 维护双向链表的角度对 LinkedHashMap 的源码进行了分析，并在文章的结尾基于 LinkedHashMap 实现了一个简单的 Cache。在日常开发中，LinkedHashMap 的使用频率虽不及 HashMap，但它也个重要的实现。在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构，并实现了不同的功能。HashMap 底层基于拉链式的散列结构，并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构，HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上，通过维护一条双向链表，实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能。我在前面几篇文章中，对 HashMap 和 TreeMap 以及他们均使用到的红黑树进行了详细的分析，有兴趣的朋友可以去看看。
到此，本篇文章就写完了，感谢大家的阅读！
附录：映射类文章列表
本文在知识共享许可协议 4.0 下发布，转载请注明出处
作者：coolblog
本文同步发布在我的个人博客：
本作品采用进行许可。
本文原创发布于慕课网 ，转载请注明出处，谢谢合作
若觉得本文不错，就分享一下吧！
评论加载中...
相关文章推荐
正在加载中
JAVA开发工程师
作者相关文章