数据结构

在HashMap的数据结构基础上，并通过双向链表维护顺序
image.png

  1. public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
  3.     // 继承HashMap，并维护自己独有的双向链表
  4.     transient LinkedHashMap.Entry<K, V> head;
  5.     transient LinkedHashMap.Entry<K, V> tail;
  6. }

put()

调用的是HashMap的put()方法，但会使用LinkedHashMap覆盖的newNode()

  1. Node<K, V> newNode(int var1, K var2, V var3, Node<K, V> var4) {
  2.     LinkedHashMap.Entry var5 = new LinkedHashMap.Entry(var1, var2, var3, var4);
  4.     // 将插入的节点放到链表尾部
  5.     this.linkNodeLast(var5);
  6.     return var5;
  7. }
  9. private void linkNodeLast(LinkedHashMap.Entry<K, V> var1) {
  10.     LinkedHashMap.Entry var2 = this.tail;
  11.     this.tail = var1;
  12.     if (var2 == null) {
  13.         this.head = var1;
  14.     } else {
  15.         var1.before = var2;
  16.         var2.after = var1;
  17.     }
  19. }

get()

JDK1.8的LRU最近访问放在链表尾部

  1. public V get(Object var1) {
  2.     Node var2;
  4.     // 这里的getNode是HashMap get()的核心逻辑
  5.     if ((var2 = this.getNode(hash(var1), var1)) == null) {
  6.         return null;
  7.     } else {
  8.         // 添加了维护链表顺序的LRU逻辑
  9.         if (this.accessOrder) {
  10.             this.afterNodeAccess(var2);
  11.         }
  13.         return var2.value;
  14.     }
  15. }
  18. void afterNodeAccess(Node<K, V> var1) {
  19.     LinkedHashMap.Entry var2;
  20.     if (this.accessOrder && (var2 = this.tail) != var1) {
  21.         LinkedHashMap.Entry var3 = (LinkedHashMap.Entry)var1;
  22.         LinkedHashMap.Entry var4 = var3.before;
  23.         LinkedHashMap.Entry var5 = var3.after;
  24.         var3.after = null;
  26.         // 前置节点为Null，则原节点为head节点
  27.         // 处理前后节点关系
  28.         if (var4 == null) {
  29.             this.head = var5;
  30.         } else {
  31.             var4.after = var5;
  32.         }
  34.         // 后置节点为null，则原节点为tail节点
  35.         // 处理前后节点关系
  36.         if (var5 != null) {
  37.             var5.before = var4;
  38.         } else {
  39.             var2 = var4;
  40.         }
  42.         // 链表原来是否没元素
  43.         if (var2 == null) {
  44.             this.head = var3;
  45.         } else {
  46.             // 不是则将原节点放到链表尾部
  47.             var3.before = var2;
  48.             var2.after = var3;
  49.         }
  51.         this.tail = var3;
  52.         ++this.modCount;
  53.     }
  55. }