LinkedHashMap原理解析
LinkedHashMap
LinkedHashMap
LinkedHashMap
是Java集合框架中的一种实现,它是 HashMap
的子类,并使用双向链表来维护元素的插入顺序或访问顺序。与 HashMap
不同,LinkedHashMap
中元素的顺序是可以预测的。因此,LinkedHashMap
非常适合需要按照顺序遍历元素的场景。
作用
LinkedHashMap
的主要作用是维护元素的顺序,这使得它非常适合于需要按照顺序遍历元素的场景。例如,缓存实现或记录某些操作的日志。LinkedHashMap
还能支持按照访问顺序来维护元素顺序,这意味着可以根据元素的访问顺序进行遍历。
优势
相比于 HashMap
,LinkedHashMap
的优势在于它可以维护元素的插入顺序或访问顺序。这使得 LinkedHashMap
非常适合需要按照顺序遍历元素的场景。虽然与 HashMap
相比,在插入和删除操作上 LinkedHashMap
稍慢,但遍历操作更快。
思考点:
-
LinkedHashMap
在HashMap
的基础上做了什么改动,是怎么样实现双向链表的?想了解
LinkedHashMap
的调整, 首先我们需要记住LinkedHashMap
中的两个变量head
(头节点)和tail
(尾节点)。双向链表的实现: 在
LinkedHashMap
中对HashMap.Node
节点进行了扩展, 补充了before(前), **after(后)**节点信息, 然后在创建新Note节点时, 进行了双向链表的(**before、after)**的绑定// 对HashMap.Node节点进行扩展, 补充了双向链表 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); } } Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e); // 设置双向链表节点 linkNodeLast(p); return p; } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<>(hash, key, value, next); // 设置双向链表节点 linkNodeLast(p); return p; } // 设置节点双向链表 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { // 缓存尾节点tail LinkedHashMap.Entry<K,V> last = tail; // 重新定义尾节点 tail = p; if (last == null) // 如果之前不存在尾节点时, 则当前是第一次插入, 不进行处理 head = p; else { // 把插入节点的前一个节点设置为尾节点last p.before = last; // 尾节点的后一个节点设置为插入节点p last.after = p; } }
对
HashMap
的扩展: 在HashMap
中提供了如下方法// 在对设置节点value后的扩展 void afterNodeAccess(Node<K,V> p) { } // 节点添加完成后的扩展 void afterNodeInsertion(boolean evict) { } // 删除节点后的扩展 void afterNodeRemoval(Node<K,V> p) { }
而
LinkedHashMap
对上述三个方法进行了调整afterNodeAccess
设置值后, 在按照访问顺序排序
时, 会把操作节点移动到链表最后一位afterNodeInsertion
插入新节点后执行一些操作, 主要目的是实现基于访问顺序的缓存策略afterNodeRemoval
删除节点后的操作, 重新删除节点的前后节点关系
-
LinkedHashMap
和HashMap
相比为什么说遍历操作更快。在为什么快之前需要先大概了解
HashMap
的遍历方式。已经知道HashMap
是通过 数组+链表(黑红树)实现的, 那么HashMap
在遍历的时候, 其实是先遍历遍历数组获取到hash桶, 然后在遍历hash桶获取到真实的节点数据。而对于
LinkedHashMap
来说, 因为已经实现了双向链表, 所以不需要想HashMap
中一样关心那么多, 只需要通过内部定义的变量head
(头节点)直接对链表进行遍历就好。所以才会说
LinkedHashMap
在遍历上比HashMap
快。
使用案例
在 LinkedHashMap
中, 模式是按照插入顺序排序, 但是如果将 accessOrder
设置为 true
,那么 LinkedHashMap
将会按照访问/操作顺序来调整元素的顺序,即最近访问/操作的元素将被放在最后。
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16 , 0.75f, Boolean.TRUE);
linkedHashMap.put("1", "1");
linkedHashMap.put("2", "2");
linkedHashMap.get("2");
System.out.println(linkedHashMap); // {"2"="2","1"="1"} 发送改变
实现原理, 通过对 HashMap.afterNodeAccess
进行扩展, 当插入时, 对链表进行重新排序, 把访问/操作的节点设置到尾节点
// e为操作节点
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
// p -> 操作节点
LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e,
// b -> 操作节点前节点
b = p.before,
// a -> 操作节点后节点
a = p.after;
// 设置操作节点到尾节点, 然后重新绑定操作节点的前后节点关系
p.after = null;
// 如果前节点不存在, 标识操作节点为头节点, 把a设置为头节点信息
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;
}
// 操作节点设置为尾节点
tail = p;
++modCount;
}
}
转载自:https://juejin.cn/post/7270140695476699191