LinkedHashMap原理(浅谈)

谁借莪１个温暖的怀抱￠ 2023-03-13 09:16 7阅读 0赞

### 文章目录 ###

*  一. 回顾
 *  二. LinkedHashMap
 *   *  2.1 成员变量
     *  2.2 构造方法
     *  2.3 静态内部类
     *  2.4 linkNodeLast()方法
     *  2.5 访问顺序
     *  2.6 LinkedHashMap是如何实现LRU算法？

# 一. 回顾 #

前面深入了解了[HashMap实现原理][HashMap]以及[HashMap常见问题][HashMap 1]，今天简略了解LinkedHashMap原理。

**此笔记仅供自己学习完后复习回顾参考，还有很多待提高的地方，如有错误请指正**

# 二. LinkedHashMap #

打开IDEA，按两下shift搜索LinkedHashMap，打开源码，可以看到如下：

* @since   1.4
     */
    public class LinkedHashMap<K,V>
        extends HashMap<K,V>
        implements Map<K,V>
    {

**解释：** @since1.4代表LinkedHashMap在jdk1.4才开始有。LinkedHashMap继承了HashMap，实现了Map接口。由此可以看出LinkedHashMap是一个HashMap，推理出其在HashMap的基础上增加了某些东西。

## 2.1 成员变量 ##

**head、tail：** 从中文意思可看出这是节点的头尾指针，也就是在HashMap的基础上加了头尾指针。 指针的类型是`LinkedHashMap.Entry<K,V>`，它是LinkedHashMap的静态内部类，后面再详述。

/** * 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;

--------------------

**accessOrder：** 从中文意思可看出这是访问顺序。这也是在HashMap的基础上加的东西。注释中作出了解释，这是给LinkedHashMap作迭代用的。当值为`true`的时候，该变量代表访问顺序（后面再用例子详述什么是访问顺序）；当值为`false`的时候，该变量代表插入顺序。(即存键值对进去是什么顺序，迭代打印出来的就是什么顺序)。

/** * 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;

--------------------

## 2.2 构造方法 ##

因为LinkedHashMap继承了HashMap，所以两者底层架构并没有很大的差异(同样都是数组+链表+红黑树)。

**两者的差别就在：LinkedHashMap的数据节点多了2个指针：`头指针head`和`尾指针tail`**

它有5个构造方法，比HashMap多了1个，其他的四个构造方法和HashMap的都差不多。如下：  
![在这里插入图片描述][20200512212028289.png]

--------------------

**LinkedHashMap()：** 无参构造，调用父类HashMap的无参构造(初始容量为16，负载因子为0.75)，并且设置`accessOrder=false;`(即使用插入顺序)

/** * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance * with the default initial capacity (16) and load factor (0.75). */
        public LinkedHashMap() { 
            super();
            accessOrder = false;
        }

--------------------

**LinkedHashMap(int initialCapacity)：** 调用父类HashMap(initialCapacity)，指定初始容量，并且设置`accessOrder=false;`(即使用插入顺序)

/** * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance * with the specified initial capacity and a default load factor (0.75). * * @param initialCapacity the initial capacity * @throws IllegalArgumentException if the initial capacity is negative */
        public LinkedHashMap(int initialCapacity) { 
            super(initialCapacity);
            accessOrder = false;
        }

--------------------

**LinkedHashMap(int initialCapacity, float loadFactor)：** 调用父类HashMap(initialCapacity, loadFactor)，指定初始容量和负载因子，并且设置`accessOrder=false;`(即使用插入顺序)

/** * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance * with the specified initial capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
        public LinkedHashMap(int initialCapacity, float loadFactor) { 
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }

--------------------

**LinkedHashMap(Map<? extends K, ? extends V> m)：** 调用父类HashMap的空参构造，并且设置`accessOrder=false;`(即使用插入顺序)，调用putMapEntries()方法将map集合转为LinkedHashMap集合。容量由入参map集合决定

/** * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with * the same mappings as the specified map. The <tt>LinkedHashMap</tt> * instance is created with a default load factor (0.75) and an initial * capacity sufficient to hold the mappings in the specified map. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */
        public LinkedHashMap(Map<? extends K, ? extends V> m) { 
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }

--------------------

**LinkedHashMap(int initialCapacity,  
float loadFactor,  
boolean accessOrder)：** 调用父类HashMap的`(initialCapacity, loadFactor)`，并且设置指定的`accessOrder`(即使用指定的顺序)。此三个入参的构造方法在HashMap并没有

/** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) { 
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

--------------------

## 2.3 静态内部类 ##

这是增加了head、tail两个指针的类型，继承了HashMap.Node<K,V>，也就是说拥有HashMap.Node<K,V>的特性。构造方法调用了HashMap.Node<K,V>的`Node(int hash, K key, V value, Node<K,V> next)`

/** * 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);
            }
        }

## 2.4 linkNodeLast()方法 ##

在链表末尾添加节点，如下：

// link at the end of list
        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;
            }
        }

**可以看出LinkedHashMap加了head、tail的指针，作用和C语言的链表差不多。**

## 2.5 访问顺序 ##

上面介绍成员变量`accessOrder`的时候，涉及到`访问顺序`这个词。

--------------------

**在解释这个知识点之前，先回顾一下`LRU知识点`**

**LRU：Least Recently Used，中文是`最近最少使用`。是一种常用的`页面置换算法`。在内存不命中的条件下，内存缺页需要将页面置换。详情如下：**  
![在这里插入图片描述][20200512215014592.png]

--------------------

下面用一个测试实例来解释说明。  
下面的测试目的是证明：

1.  HashMap插入的顺序与取出的顺序是不一样的，即HashMap是无序的
2.  LinkedHashMap插入的顺序与取出的顺序是一样的，即LinkedHashMap是有序的

@Test
        public void test1(){ 
            Map<String, String> linkMap = new LinkedHashMap<String, String>();
            Map<String, String> hashMap = new HashMap<String, String>();
    
            linkMap.put("2", "2");
            linkMap.put("1", "1");
            linkMap.put("3", "3");
    
            hashMap.put("2", "2");
            hashMap.put("1", "1");
            hashMap.put("3", "3");
    
            Set<Map.Entry<String, String>> linkEntries = linkMap.entrySet();
            Set<Map.Entry<String, String>> hashEntries = hashMap.entrySet();
    
            System.out.print("LinkedHashMap:");
            for (Map.Entry<String, String> entry : linkEntries) { 
                System.out.print(" " + entry + " ");
            }
    
            System.out.println();
    
            System.out.print("HashMap:");
            for (Map.Entry<String, String> entry : hashEntries) { 
                System.out.print(" " + entry + " ");
            }
        }

测试结果：  
![在这里插入图片描述][20200512221024325.png]

--------------------

下面测试开启`accessOrder`访问顺序（即`accessOrder=true`)。如下：

@Test
        public void test2() { 
            //使用三个入参的构造器来设置accessOrder=true
            Map<String, String> linkMap =
                    new LinkedHashMap<String, String>(16, 0.75f, true);
    
            linkMap.put("2", "2");
            linkMap.put("1", "1");
            linkMap.put("3", "3");
    
            Set<Map.Entry<String, String>> linkEntries = linkMap.entrySet();//获取键值对集合
    
            System.out.print("访问前的LinkedHashMap:");
            for (Map.Entry<String, String> entry : linkEntries) { 
                System.out.print(" " + entry + " ");
            }
            System.out.println();
    
            //访问linkMap
            linkMap.get("2");
            System.out.print("访问2后的LinkedHashMap:");
            for (Map.Entry<String, String> entry : linkEntries) { 
                System.out.print(" " + entry + " ");
            }
            System.out.println();
            
            //访问linkMap
            linkMap.get("1");
            System.out.print("访问1后的LinkedHashMap:");
            for (Map.Entry<String, String> entry : linkEntries) { 
                System.out.print(" " + entry + " ");
            }
    
    
        }

测试结果：  
![在这里插入图片描述][20200513091223107.png]  
可以看到被访问后的元素，被置顶了。也就是说，LinedHashMap访问某元素，某元素将被置顶。这样的功能应用在`LRU`缓存方面。 经常访问的元素就可以很快速地找到了，而不被经常访问的元素可以沉到底甚至可以被覆盖，LinkedHahsMap这样的功能使得它在缓存技术方面发扬光大。

**总结:从上面的访问顺序，也可以总结出，遍历LinkedHashMap是按照从链表开始扫描，扫到尾部的。get元素后，元素被放到链表的尾部，所以每次get后再遍历LinkedHashMap，get的元素都会出现在末尾。**

## 2.6 LinkedHashMap是如何实现LRU算法？ ##

Mybatis中的Lrucache底层是用LinkedHashMap。我们从源码分析LinkedHashMap怎么可以实现LRU。

因为涉及的是访问顺序，而它又是因get()方法引起的，所以首先从get()方法看起，如下：

public V get(Object key) { 
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }

发现与`afterNodeAccess(e)`有关，点进去看看，如下：

void afterNodeAccess(Node<K,V> e) {  // move node to last
            LinkedHashMap.Entry<K,V> last;
            if (accessOrder && (last = tail) != e) { 
                LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)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;
            }
        }

看到方法开头就已经有一行注释了`// move node to last`，意思就是将元素移到链表尾部。

**总结：当访问某元素，如果设置了访问顺序`accessOrder=true`，则该元素被移到链表尾部。**

**按照这个思路，如果满足当前长度大于某值就移除链头的元素，这样就实现了LRU缓存。**

由此可推理当我们put元素进去，LinkedHashMap会判断元素是否已经达到了LRU设定的缓存大小，如果达到就会实行LRU。将很久不被使用的元素移除。因此我们查看LinkedHashMap的`put()`方法，发现没有这个方法。那说明LinkedHashMap的put方法调用的是父类HashMap的`put()`方法。打开HashMap找到`put()`方法，发现有一个`afterNodeInsertion()`，如下：  
![在这里插入图片描述][20200513111704347.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][2020051311185718.png]  
上图中此`afterNodeInsertion()`方法并没有在HashMap中实现而是在LinkedHashMap实现。

打开LinkedHashMap查看`afterNodeInsertion()`方法，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2_size_16_color_FFFFFF_t_70 1]  
点进去看`removeEldestEntry(first)`该方法默认是返回false(即默认不实现缓存功能)。如下：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
            return false;
        }

**总结：综上所述只要我们重写这个方法在某条件下返回true就可以实现LRU缓存。**

**测试例子：用LinkedHashMap实现LRU缓存**

@Test
        public void test3() { 
            Map<String, String> map =
                    new LinkedHashMap<String, String>(5, 0.75f, true) { 
                        @Override
                        protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { 
                            //当前长度>=5，再插入就移除。即达到阈值时就实现LRU
                            return this.size()>=5;
                        }
                    };
    
            map.put("2", "2");
            map.put("1", "1");
            map.put("3", "3");
            map.put("9", "9");
    
            Set<Map.Entry<String, String>> linkEntries = map.entrySet();//获取键值对集合
    
            //访问linkMap
            map.get("2");
            System.out.print("访问2后的LinkedHashMap:");
            for (Map.Entry<String, String> entry : linkEntries) { 
                System.out.print(" " + entry + " ");
            }
            System.out.println();
    
            map.put("5", "5");
    
            System.out.print("存入5后的LinkedHashMap:");
            for (Map.Entry<String, String> entry : linkEntries) { 
                System.out.print(" " + entry + " ");
            }
            System.out.println();
        }

测试结果：  
![在这里插入图片描述][20200513112709229.png]

[HashMap]: https://blog.csdn.net/qq_40634846/article/details/105988947
[HashMap 1]: https://blog.csdn.net/qq_40634846/article/details/106017742
[20200512212028289.png]: /images/20230312/d7965fcaf3a54033936aa1a46d965ca5.png
[20200512215014592.png]: /images/20230312/4530193733ce4882ac3b11c06eb20acd.png
[20200512221024325.png]: /images/20230312/af49f5ee6f2e404cb7df6b79a0fc1313.png
[20200513091223107.png]: /images/20230312/40dee863e3fb4b30ae75e0622227b0db.png
[20200513111704347.png]: https://img-blog.csdnimg.cn/20200513111704347.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200513111802798.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2,size_16,color_FFFFFF,t_70
[2020051311185718.png]: https://img-blog.csdnimg.cn/2020051311185718.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200513112100964.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2,size_16,color_FFFFFF,t_70
[20200513112709229.png]: https://img-blog.csdnimg.cn/20200513112709229.png