LinkedHashMap 源码分析，底层竟这么简单！

作者：Pz
cnblogs.com/panzi/p/10845079.html

LinkedHashMap?是一个键有序的?HashMap，可以将?LinkedHashMap?理解为?LinkList?+?HashMap。

所以研究?LinkedHashMap?之前要先看?HashMap?代码，这里不再赘述。

其实?LinkedHashMap?无非就是通过链表结构将存储在?HashMap?中的数据通过?beofre,after连接起来。

作为一个链表结构?head,tail?必不可少

/**
?* The head (eldest) of the doubly linked list.
?*/
transient?LinkedHashMap.Entry<K,V>?head;

/**
?* The tail (youngest) of the doubly linked list.
?*/
transient?LinkedHashMap.Entry<K,V>?tail;

还要有一个存储 前节点和后节点的数据结构

/**
?* HashMap.Node subclass for normal LinkedHashMap entries.
?*/
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);
??}
}

最后，为了支持节点根据访问频率更新节点顺序，增加了?accessOrder?变量

/**
?* The iteration ordering method?for?this linked?hash?map: <tt>true</tt>
?*?for?access-order, <tt>false</tt>?for?insertion-order.
?*
?* @serial
?*/
final boolean accessOrder;

LinkedHashMap中的?put?方法没有重写，其实就是?HashMap?中的?put?方法。不过它给子类留了可供重写的方法。

afterNodeAccess(e) 和 afterNodeInsertion(evict);

final V?putVal(int?hash, K key, V?value, boolean onlyIfAbsent,
?????????boolean evict)?{
??Node<K,V>[] tab; Node<K,V> p;?int?n, i;
??if?((tab = table) ==?null?|| (n = tab.length) ==?0)
????n = (tab = resize()).length;
??if?((p = tab[i = (n -?1) & hash]) ==?null)
????tab[i] = newNode(hash, key,?value,?null);
??else?{
????Node<K,V> e; K k;
????if?(p.hash == hash &&
??????((k = p.key) == key || (key !=?null?&& key.equals(k))))
??????e = p;
????else?if?(p instanceof TreeNode)
??????e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key,?value);
????else?{
??????for?(int?binCount =?0; ; ++binCount) {
????????if?((e = p.next) ==?null) {
??????????p.next = newNode(hash, key,?value,?null);
??????????if?(binCount >= TREEIFY_THRESHOLD -?1)?// -1 for 1st
????????????treeifyBin(tab, hash);
??????????break;
????????}
????????if?(e.hash == hash &&
??????????((k = e.key) == key || (key !=?null?&& key.equals(k))))
??????????break;
????????p = e;
??????}
????}
????if?(e !=?null) {?// existing mapping for key
??????V oldValue = e.value;
??????if?(!onlyIfAbsent || oldValue ==?null)
????????e.value?=?value;
??????//
??????afterNodeAccess(e);
??????return?oldValue;
????}
??}
??++modCount;
??if?(++size > threshold)
????resize();
??//
??afterNodeInsertion(evict);
??return?null;
}

afterNodeInsertion?当有新节点插入时，是否删除第一个节点，removeEldestEntry在此类中返回了 false，所以，不会删除任何一个节点。

// possibly remove eldest
void?afterNodeInsertion(boolean?evict)?{
??LinkedHashMap.Entry<K,V> first;

??if?(evict && (first = head) !=?null?&& removeEldestEntry(first)) {
????K key = first.key;
????removeNode(hash(key), key,?null,?false,?true);
??}
}

另外，LinkedHashMap?重写了?newNode方法。以将新节点插入到链表最后一个节点上

tab[i] = newNode(hash, key,?value,?null);

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;
}
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;
??}
}

afterNodeAccess 当节点更新时，或者调用 get，getOrDefault 方法时，会根据 accessOrder 为true或者false执行该方法。

---

void afterNodeAccess(Node<K,V> e) {
??LinkedHashMap.Entry<K,V> last;
??//需要改变顺序 并且 当前节点不是最后一个
??if?(accessOrder && (last = tail) != e) {
????// b 当前节点之前的节点
????// a 当前节点之后的节点
????LinkedHashMap.Entry<K,V> p =
??????(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
????//需要将p节点置为最后一个节点，所以置 p节点的 after 为 null
????p.after =?null;

????B->P->A ===> B->P->E
????//如果没有前一个节点，所以 后一个节点置为 头节点
????if?(b ==?null)
??????head = a;
????else
??????//否则 将 b.after 置为 a
??????b.after = a;

????// B->P->A ===> B->A
????if?(a !=?null)
??????a.before = b;
????else
??????// B->P->NULL ===> B->A
??????last = b;
????//如果 last 为 null，将 p 置为头结点
????if?(last ==?null)
??????head = p;
????else?{
??????//B -> P -> NULL
??????p.before = last;
??????last.after = p;
????}
????//最后将tail置为 p 节点
????tail = p;
????++modCount;
??}
}

简单看了一下代码结构，虽然细节很多都没看，但是大体上的实现就是多了一层封装，通过链表结构实现顺序存储并且还能达到 O(1)的插入和删除，查找操作。

推荐去我的博客阅读更多：

1.Java JVM、集合、多线程、新特性系列教程

2.Spring MVC、Spring Boot、Spring Cloud 系列教程

3.Maven、Git、Eclipse、Intellij IDEA 系列工具教程

4.Java、后端、架构、阿里巴巴等大厂最新面试题

觉得不错，别忘了点赞+转发哦！

原文链接:https://www.cnblogs.com/javastack/p/12844558.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有