本文共 4164 字，大约阅读时间需要 13 分钟。

作者：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
   
     head;/** * The tail (youngest) of the doubly linked list. */transient LinkedHashMap.Entry
    
      tail;
    
   

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

/** * HashMap.Node subclass for normal LinkedHashMap entries. */static class Entry
   
     extends HashMap.Node
    
      {  Entry
     
       before, after;  Entry(int hash, K key, V value, Node
      
        next) {    super(hash, key, value, next);  }}
      
     
    
   

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

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

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

afterNodeAccess(e) 和 afterNodeInsertion(evict);

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,         boolean evict) {  Node
   
    [] tab; Node
    
      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
     
       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
      
       )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 eldestvoid afterNodeInsertion(boolean evict) {  LinkedHashMap.Entry
   
     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
   
     newNode(int hash, K key, V value, Node
    
      e) {  LinkedHashMap.Entry
     
       p =    new LinkedHashMap.Entry
      
       (hash, key, value, e);  linkNodeLast(p);  return p;}private void linkNodeLast(LinkedHashMap.Entry
       
         p) {  LinkedHashMap.Entry
        
          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
   
     e) {  LinkedHashMap.Entry
    
      last;  //需要改变顺序 并且 当前节点不是最后一个  if (accessOrder && (last = tail) != e) {    // b 当前节点之前的节点    // a 当前节点之后的节点    LinkedHashMap.Entry
     
       p =      (LinkedHashMap.Entry
      
       )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.

2.

3.

4.

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

转载地址：http://oycsf.baihongyu.com/