Java基础之LinkedHashMap源码解析-白红宇

Java集合源码解析系列

LinkedHashMap

public class LinkedHashMap
    
         extends HashMap
     
          implements Map
      
       {    /**     * HashMap.Node的子类     * 增加了前后节点的引用，因此不再是单链表而是双向链表     */    static class Entry
       
         extends HashMap.Node
        
          {        Entry
         
           before, after; Entry(int hash, K key, V value, Node
          
            next) { super(hash, key, value, next); } } /** * 双向链表的头节点和尾节点 * */ transient LinkedHashMap.Entry
           
             head; transient LinkedHashMap.Entry
            
              tail; /** * 排序规则的标志 * false表示按节点插入顺序排序 * true表示按节点访问顺序排序 * 默认是false */ final boolean accessOrder; /** *将节点插入链表尾部 */ private void linkNodeLast(LinkedHashMap.Entry
             
               p) { LinkedHashMap.Entry
              
                last = tail; tail = p; //如果是插入第一个节点，则头节点和尾节点都指向这个节点 if (last == null) head = p; //已经插入过节点了，就直接插入链表尾部 else { p.before = last; last.after = p; } } /** *将dst节点替换src节点 */ private void transferLinks(LinkedHashMap.Entry
               
                 src, LinkedHashMap.Entry
                
                  dst) { LinkedHashMap.Entry
                 
                   b = dst.before = src.before; LinkedHashMap.Entry
                  
                    a = dst.after = src.after; //src是第一个节点 if (b == null) head = dst; else b.after = dst; //src是最后一个节点 if (a == null) tail = dst; else a.before = dst; } /** *初始化LinkedHashMap，这里在调用HashMap的初始化方法之外，还需要将头节点和尾节点初始化 */ void reinitialize() { super.reinitialize(); head = tail = null; } /** * 这里覆写了HashMap的newNode方法 * 生成新的节点并插入到尾部 */ Node
                   
                     newNode(int hash, K key, V value, Node
                    
                      e) { LinkedHashMap.Entry
                     
                       p = new LinkedHashMap.Entry
                      
                       (hash, key, value, e); linkNodeLast(p); return p; } /** * 用next节点替换p节点 */ Node
                       
                         replacementNode(Node
                        
                          p, Node
                         
                           next) { LinkedHashMap.Entry
                          
                            q = (LinkedHashMap.Entry
                           
                            )p; LinkedHashMap.Entry
                            
                              t = new LinkedHashMap.Entry
                             
                              (q.hash, q.key, q.value, next); transferLinks(q, t); return t; } /** * 红黑树节点的相关方法 */ TreeNode
                              
                                newTreeNode(int hash, K key, V value, Node
                               
                                 next) { TreeNode
                                
                                  p = new TreeNode
                                 
                                  (hash, key, value, next); linkNodeLast(p); return p; } TreeNode
                                  
                                    replacementTreeNode(Node
                                   
                                     p, Node
                                    
                                      next) { LinkedHashMap.Entry
                                     
                                       q = (LinkedHashMap.Entry
                                      
                                       )p; TreeNode
                                       
                                         t = new TreeNode
                                        
                                         (q.hash, q.key, q.value, next); transferLinks(q, t); return t; } /** * 覆写HashMap中的afterNodeRemoval方法 * 将节点从链表中删除 */ void afterNodeRemoval(Node
                                         
                                           e) { LinkedHashMap.Entry
                                          
                                            p = (LinkedHashMap.Entry
                                           
                                            )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; } /** * 覆写HashMap中的afterNodeInsertion方法 * evict为true并且removeEldestEntry方法也为true的话就会删除近期最少使用的节点 * 所以这里可以看出LinkedHashMap能实现LRU算法 * 由HashMap的源码可知evict默认是true */ void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry
                                            
                                              first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; //满足条件则删除近期使用最少的节点 removeNode(hash(key), key, null, false, true); } } /** * 覆写HashMap中的afterNodeAccess方法，每当节点被访问时被调用 * 如果accessOrder为true，也就是LinkedHashMap的节点是按照访问顺序排序的，则需要将节点移到链表的末尾 * 这也是LinkedHashMap实现LRU算法的条件之一，即accessOrder要为true */ void afterNodeAccess(Node
                                             
                                               e) { // move node to last LinkedHashMap.Entry
                                              
                                                last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry
                                               
                                                 p = (LinkedHashMap.Entry
                                                
                                                 )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; } } /** * 可以看到默认accessOrder为false，也就是按节点插入顺序排序 */ public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } /** * 这个构造函数可以设置排序规则 * 所以如果要实现LRU算法，也就是要设置accessOrder为true，就要用这个构造函数 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } /** * 判断值是否存在，只需要循环双向链表 * 这里相比HashMap需要2层循环，提升了效率 */ public boolean containsValue(Object value) { for (LinkedHashMap.Entry
                                                 
                                                   e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; } /** * LinkedHashMap的get方法调用的是HashMap的getNode方法 * 注意这里会调用recordAccess方法 */ public V get(Object key) { Node
                                                  
                                                    e; //如果没找到返回null if ((e = getNode(hash(key), key)) == null) return null; //如果节点是按照访问顺序排序的，那就得去更新下顺序，把刚刚获取的节点放到链表末尾去 if (accessOrder) afterNodeAccess(e); return e.value; } /** * 跟上面的方法一样，只是如果对应的key的节点不存在，会返回一个默认的数据 */ public V getOrDefault(Object key, V defaultValue) { Node
                                                   
                                                     e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; } /** * 这个好理解，清空数据 */ public void clear() { super.clear(); head = tail = null; } /** * 这个方法用于控制是否要删除近期使用最少的节点 * 默认返回是false，所以如果要实现LRU算法，需要覆写该方法，比如节点满了返回true以便删掉使用较少的节点 */ protected boolean removeEldestEntry(Map.Entry
                                                    
                                                      eldest) { return false; } 
                                                      }

LinkedHashMap没有put方法，是怎么插入数据的呢

答案就在newNode方法

/** * 这里覆写了HashMap的newNode方法 * 生成新的节点并插入到尾部 */Node
    
      newNode(int hash, K key, V value, Node
     
       e) {    LinkedHashMap.Entry
      
        p =        new LinkedHashMap.Entry
       
        (hash, key, value, e);    linkNodeLast(p);    return p;}/** * 红黑树节点的相关方法 */TreeNode
        
          newTreeNode(int hash, K key, V value, Node
         
           next) { TreeNode
          
            p = new TreeNode
           
            (hash, key, value, next); linkNodeLast(p); return p;}

LinkedHashMap实际只是在HashMap的基础上加上了一个双向链表来保存节点插入的顺序，因此很多的逻辑都和HashMap是一样的。比如插入节点时，LinkedHashMap相比HashMap只需要在HashMap的基础上将节点插入双向链表，以及根据排序要求更新节点的顺序就行了

对于插入双向链表的功能，LinkedHashMap覆写了HashMap的newNode方法；而对于更新节点的顺序问题，LinkedHashMap覆写了afterNodeAccess方法和afterNodeInsertion方法

总结

LinkedHashMap继承自HashMap，是HashMap的子类，因此也不是线程安全的

LinkedHashMap底层存储结构与HashMap一样，不同的是LinkedHashMap增加了一个双向链表的头节点，插入的数据除了插入HashMap，还会插入链表中，因而可以保存插入节点的顺序

LinkedHashMap的节点在HashMap节点的基础上增加了前后节点的引用

LinkedHashMap可以插入null

LinkedHashMap相比HashMap在查找值和删除值时效率要高

LinkedHashMap还可以设置按插入顺序排序或是按访问顺序排序，默认是按插入顺序排序

LinkedHashMap没有put方法，而是覆写了afterNodeAccess方法和afterNodeInsertion方法。当插入的数据已经存在时，会调用afterNodeAccess方法看是否需要将数据插入到链表末尾；当插入的数据是新数据时，会通过afterNodeInsertion方法来根据设置删除近期使用最少的节点

LinkedHashMap可以用来实现LRU算法。首先需要用可以设置accessOrder的构造函数设置accessOrder为true，也就是按照节点访问顺序排序；然后removeEldestEntry方法设置当超过节点数时返回true，也就是删除近期最少使用的数据

以上是基于Java1.8并且只介绍了常用的一些方法的原理，详细的LinkedHashMap源码请查看：

欢迎关注我的微信公众号，和我一起学习一起成长！