java集合之LinkedHashMap解析-白红宇

java集合之LinkedHashMap解析

阅读量：4256 次

发布时间：2019-05-26

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

LinkedHashMap 继承自HashMap，主要结构还是HashMap，添加了双向链表来保证插入顺序或者访问顺序。

著名的LRUCache就是借助了LinkedHashMap的保持访问顺序的特性实现的。

//LinkedHashMap中保存的节点，比hashMap中的Node添加了before，after，node中还有next，    //添加的两个节点的指针，组成了双向链表    static class LinkedHashMapEntry
   
     extends HashMap.Node
    
      {        LinkedHashMapEntry
     
       before, after;        LinkedHashMapEntry(int hash, K key, V value, Node
      
        next) {            super(hash, key, value, next);        }    }   //双向链表的头和尾    /**     * The head (eldest) of the doubly linked list.     */    transient LinkedHashMapEntry
       
         head;    /**     * The tail (youngest) of the doubly linked list.     */    transient LinkedHashMapEntry
        
          tail; //true时双向链表访问顺序，false时插入顺序 /** * The iteration ordering method for this linked hash map: 
         true * for access-order, 
         false for insertion-order. * * @serial */ final boolean accessOrder;

newNode函数时hashMap中的函数，LinkedHashMap重写了这个函数。

//生成一个新节点，然后连接到末尾 Node
   
     newNode(int hash, K key, V value, Node
    
      e) {        LinkedHashMapEntry
     
       p =            new LinkedHashMapEntry
      
       (hash, key, value, e);        linkNodeLast(p);        return p;    }连接到双向链表尾 private void linkNodeLast(LinkedHashMapEntry
       
         p) {        LinkedHashMapEntry
        
          last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }//treeNode，类似newNode TreeNode
         
           newTreeNode(int hash, K key, V value, Node
          
            next) { TreeNode
           
             p = new TreeNode
            
             (hash, key, value, next); linkNodeLast(p); return p; }

这样就实现了每次插入新节点，放到双向链表尾部。

为了实现linkedHashMap的访问顺序排序，HashMap中预留了三个重要函数，在很多地方被调用但是都没有实现：

// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node
   
     p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node
    
      p) { }

LinkedHashMap中实现了这三个函数：

//操作过数组和链表上的元素之后，修改双向链表，删除节点 void afterNodeRemoval(Node
   
     e) { // unlink        LinkedHashMapEntry
    
      p =            (LinkedHashMapEntry
     
      )e, b = p.before, a = p.after;        p.before = p.after = null;        if (b == null)            head = a;        else            b.after = a;        if (a == null)            tail = b;        else            a.before = b;    }// 插入新的节点，调用过afterNodeAccess之后最终会查找双向链表删除相同的key的节点    void afterNodeInsertion(boolean evict) { // possibly remove eldest        LinkedHashMapEntry
      
        first;        if (evict && (first = head) != null && removeEldestEntry(first)) {            K key = first.key;            removeNode(hash(key), key, null, false, true);        }    }//accessOrder== true ，访问的不是最后一个节点，保证最后一个节点时最近使用的    void afterNodeAccess(Node
       
         e) {        LinkedHashMapEntry
        
          last; if (accessOrder && (last = tail) != e) { LinkedHashMapEntry
         
           p = (LinkedHashMapEntry
          
           )e, b = p.before, a = p.after; p.after = null; 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; } }