大家好 今天我想分析下1.8 源码 LinkedHashmap希望能对大家帮助
我的公众号
微信公众号
首先看下 LinkedHashMap 的继承 结构
graph TB
Map -->LinkedHashMap
HashMap ==> LinkedHashMap
mark
（虚线接口 实线 继承）
LinkedHashMap 是 继承了HashMap 实现了 Map 接口
LinkedHashMap 的 特性就是 顺序的放 顺序的取出来
看下效果--
public static void main(String[] args) {
Map map = new LinkedHashMap();
map.put("1","gxgeek");
map.put("2","cancer");
map.put("3","reverse");
map.put("4","hash");
map.put("5","demo");
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry entry = (Map.Entry) iterator.next();
System.out.println(entry);
}
}
out：
1=gxgeek
2=cancer
3=reverse
4=hash
5=demo
既然继承了HashMap 应该有HashMap的 特性
先看下 构造方法吧
public LinkedHashMap() {
super();
accessOrder = false;
}
这里调用父类 构造 （HashMap） 应该是初始化了 （桶） 了
然后 accessOrder = false 是什么意思呢？
翻译注释
accessOrder false： 基于插入顺序 true： 基于访问顺序
final boolean accessOrder;
可以看到 默认构造都是按照false，但是什么是反问顺序呢
查看构造有一个可以自己甚至 成 ture 的方法
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
private static void haveArgsConstructor() {
Map map = new LinkedHashMap(16,0.75f,true);
map.put("1","gxgeek");
map.put("2","cancer");
map.put("3","reverse");
map.put("4","hash");
map.put("5","demo");
//分别访问了 1 2
map.get("1");
map.get("2");
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry entry = (Map.Entry) iterator.next();
System.out.println(entry);
}
}
out：
3=reverse
4=hash
5=demo
1=gxgeek
2=cancer
可以看到访问过的被放到最后了 （这里涉及了LRU算法了）
这边 首先看下 LinkedHashMap的 entry吧
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
这边继承了 HashMap 的 的节点 在其基础上扩展了一下。改成了一个双向链表。
类变量
// 头节点
transient LinkedHashMap.Entry<K,V> head;
// 尾节点
transient LinkedHashMap.Entry<K,V> tail;
接着我们 继续看下 put 方法 到底干了什么
因为是 继承父类 没有重写 但是在hashmap put 有几个方法 被重写了
- 首先被重写的 是newNode（） 创建table 表 node 节点方法
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);
linkNodeLast (p);
return p;
}
//这段代码很简单了 先放进来的代码 放在尾节点 然后 分别改下 链表
before after
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
这三个代码是 hashmap 专门给linkedhashmap 预留的
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
的最后 放了个钩子 回调用的 afterNodeInsertion 调用函数 看下 after insert 干了什么
这个方法 默认 传过来的是 false
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//removeEldestEntry(first) 默认返回false
//如果有需要，我们可以选择重写removeEldestEntry方法，来定义老节点first在put新数据时的删除机制。 实现LRU 机制
// 下面方法的意思是删除 头结点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
LinkedHashMap 没有 重写 remove 但是 重写了afterNodeRemoval（） 这个回调函数
看下具体做了什么
mark
mark
afterNodeRemoval 在removenode 最后执行看下干了什么
mark
嗯 也很好理解 吧这个节点的 前后置空 这个 节点的 前后相互连接
LinkedHashMap 还重写了 get 和 getOrDefault
mark
可以看出 无非 就是
mark
多了 accessOrder 参数 这个参数前面构造函数 有提到
看下 afterNodeAccess 到底回调了什么
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//将这个元放置在最后一个位置
p.after = null;
将 原位置 的 after 位置 向前一位
if (b == null)
head = a;
else
b.after = a;
// 下面这段代码意思就是 把 当前位置放置到最后一位
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
// //尾节点的引用赋值成p
tail = p;
++modCount;//增加修改次数
}
}
mark
由于 双向链表的原因 只需要for一遍 时间复杂度最大为O（N） 比HashMap 双重for循环 时间复杂度低
最后迭代 遍历
mark
mark
mark
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
//初始化时，next 为 LinkedHashMap内部维护的双向链表的表头
next = head;
expectedModCount = modCount;
//当前节点为null
current = null;
}
public final boolean hasNext() {
//就是判断next是否为null，默认next是head 表头
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//更新当前节点为e
current = e;
//更新下一个节点是e的后置节点
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
//调用HashMap removeNode
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount; //重新赋值 expectedModCount
}
}
这个方法就是 迭代器 循环 从表头 开始循环输出
再怎么删改查都会更新 整个链表
总结
-
基本过了一遍 LinkedHashMap 因为继承了 HashMap 的原因 所以 该类 有两套 数据结构 -
一个是hashmap的 数组+ 链表 + 红黑树
,一个是 他增加的两个属性 before after 的双向链表结构 -
改变了迭代顺序 顺序循环输出
-
增加了accessOrder accessOrder = true 情况下 可以看到 最新访问的被放置在了最后， 不过会修改 修改次数（modCount）这个属性 在迭代器 里可以看到 如果 modCount != expectedModCount 就会报错 ，这是由于LinkedHashmap 本省是线程不安全，如果我们一般遍历 一遍在这个模式下 get 数据就会报错 这是一 隐含点
-
值得注意的是 重写containsValue（V v） 方法 优化时间复杂度到 O（N）
-
应用场景： 由于 accessOrder 的存在 我们可以实现 LRU 算法 比如 验证码校验 访问过放到最后 然后 继承 LinkedHashMap 重写最大 重新设计桶位 （比如只有1000+的桶位置） 一个简单的内存缓存就实现了 不用去继承redis 初级快速 实验 不过这边 推荐 第三方 guava cache 强大 实现了LRU 算法
网友评论