Java集合之LinkedHashMap

深碍√TFBOYSˉ_ 2021-08-14 02:59 363阅读 0赞

### LinkedHashMap ###

*  1. 简介
 *  2. 继承关系
 *  3. 存储结构
 *  4. 深入源码
 *   *  4.1 属性
     *  4.2 内部类
     *  4.3 构造方法
     *  4.4 添加及删除元素
     *   *  4.4.1 afterNodeInsertion
         *  4.4.2 afterNodeRemoval
         *  4.4.3 afterNodeAccess
         *   *  示例一
             *  示例二
     *  4.5 获取元素
     *   *  4.5.1 get(Object key)
     *  4.6 LRU 实现

# 1. 简介 #

LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，所以可以用来实现LRU缓存策略。

# 2. 继承关系 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]  
      通过继承关系，我们可以看到继承了 `HashMap`，所以其拥有 `HashMap`的所有特性，并且额外增加了按顺序访问的特性。

# 3. 存储结构 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]  
      添加删除元素的时候需要同时维护在`HashMap`中的存储，也要维护在`LinkedList`中的存储，所以性能上来说会比`HashMap`稍慢。

# 4. 深入源码 #

## 4.1 属性 ##

/** * 指向双向链表的头节点指针 */
        transient LinkedHashMap.Entry<K,V> head;
    
        /** * 指向双向链表的尾节点指针 */
        transient LinkedHashMap.Entry<K,V> tail;
    
        /** * true：双向链表按访问顺序排序 * false：双向链表按插入顺序访问 */
        final boolean accessOrder;

（1）**head**

双向链表的头节点，旧数据存在头节点。

（2）**tail**

双向链表的尾节点，新数据存在尾节点。

（3）**accessOrder**

是否需要按访问顺序排序，如果为`false`则按插入顺序存储元素，如果是`true`则按访问顺序存储元素。

## 4.2 内部类 ##

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);
            }
        }
    
    	static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) { 
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
       }

可以看到 `LinkedHashMap` 不仅仅采用了 数组 + 链表 + 红黑树的结构，节点和节点之间还通过两个指针链接成了双向链表。

## 4.3 构造方法 ##

// 构造一个空的按插入顺序排序的 LinkedHashMap 实例，其默认初始容量（16）和负载因子（0.75）。
        public LinkedHashMap() { 
            super();
            accessOrder = false;
        }
    
    	// 构造一个空的按插入顺序排序的 LinkedHashMap 实例，初始容量为 initialCapacity 的二次幂取整的值 和负载因子（0.75）。
        public LinkedHashMap(int initialCapacity) { 
            super(initialCapacity);
            accessOrder = false;
        }
    
    	// 指定 initialCapacity 和 加载因子
        public LinkedHashMap(int initialCapacity, float loadFactor) { 
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
    
        public LinkedHashMap(Map<? extends K, ? extends V> m) { 
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }
        
    	// 该构造方法accessOrder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现LRU缓存策略的关键。
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) { 
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

前四个构造方法`accessOrder`都等于`false`，说明双向链表是按插入顺序存储元素。

最后一个构造方法`accessOrder`从构造方法参数传入，如果传入`true`，则就实现了按访问顺序存储元素，这也是实现`LRU`缓存策略的关键。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]

## 4.4 添加及删除元素 ##

通过观察`LinkedHashMap`，可以看到其并没有`put`和 `remove`方法，说明其调用的是父类 `HashMap`的方法，那么其是怎么实现按插入顺序或访问顺序访问的特性的呢？

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
           // 代码省略
               
            afterNodeAccess(e);
       		// 代码省略
            afterNodeInsertion(evict);
            return null;
        }

final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) { 
            // 代码省略
            afterNodeRemoval(node);
            return null;
        }

// 该方法位于 LinkedHashMap 中
        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;
        }

我们直到在 `afterNodeInsertion`、`afterNodeAccess`、`afterNodeRemoval` 这三个方法中为空实现，而 `LinkedHashMap`中却实现了该方法，所以这便是`LinkedHashMap` 特性的决定方法。

### 4.4.1 afterNodeInsertion ###

该方法在节点被插入之后调用该方法

void afterNodeInsertion(boolean evict) {  // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
            // 如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把双向链表的头节点移除
            if (evict && (first = head) != null && removeEldestEntry(first)) { 
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
        }

（1）如果`evict`为`true`，且头节点不为空，且确定移除最老的元素，那么就调用`HashMap.removeNode()`把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；

（2）`HashMap.removeNode()`从`HashMap`中把这个节点移除之后，会调用`afterNodeRemoval()`方法；

（3）`afterNodeRemoval()`方法在`LinkedHashMap`中也有实现，用来在移除元素后修改双向链表，见下文；

（4）默认`removeEldestEntry()`方法返回`false`，也就是不删除元素。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
            return false;
        }
    
    	// 这里调用的是 HashMap 中的方法删除，已在 HashMap 中分析过
        final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) { 
            Node<K,V>[] tab; Node<K,V> p; int n, index;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) { 
                Node<K,V> node = null, e; K k; V v;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
                else if ((e = p.next) != null) { 
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else { 
                        do { 
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) { 
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) { 
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        tab[index] = node.next;
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    // 调用删除节点后的方法
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

### 4.4.2 afterNodeRemoval ###

该方法在节点被删除之后调用该方法。

// e 为被删除的节点
    	// 实现便是在双向链表中删除一个节点的实现
        void afterNodeRemoval(Node<K,V> e) {  // unlink
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)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;
        }

经典的把节点从双向链表中删除的方法。

### 4.4.3 afterNodeAccess ###

该方法在节点被访问之后调用该方法。

在节点访问之后被调用，主要在`put()`已经存在的元素或`get()`时被调用，如果`accessOrder`为`true`，调用这个方法把访问到的节点移动到双向链表的末尾。

void afterNodeAccess(Node<K,V> e) {  // move node to last
            LinkedHashMap.Entry<K,V> last;
            // 如果accessOrder为true，并且访问的节点不是尾节点
            if (accessOrder && (last = tail) != e) { 
                LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                 // 把p节点从双向链表中移除 
                p.after = null;
                if (b == null)
                    head = a;
                else
                    b.after = a;
                if (a != null)
                    a.before = b;
                else
                    last = b;
                // 把p节点放到双向链表的末尾 
                if (last == null)
                    head = p;
                else { 
                    p.before = last;
                    last.after = p;
                }
                tail = p;
                ++modCount;
            }
        }

（1）如果accessOrder为true，并且访问的节点不是尾节点；

（2）从双向链表中移除访问的节点；

（3）把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）

#### 示例一 ####

public class Test { 
    
        public static void main(String[] args) { 
            LinkedHashMap linkedHashMap = new LinkedHashMap(16,0.75f,true);
            linkedHashMap.put("1","1");
            linkedHashMap.put("2","2");
            linkedHashMap.put("3","3");
    
            Set set = linkedHashMap.entrySet();
            System.out.println(set);
    
            linkedHashMap.get("1");
            set = linkedHashMap.entrySet();
            System.out.println(set);
    
            linkedHashMap.get("2");
            set = linkedHashMap.entrySet();
            System.out.println(set);
        }
    
    }

我们在构造方法中指定的是true，那么便说明我们采用的是按照访问顺序来访问对链表进行访问。

输出如下：  
![在这里插入图片描述][2019120715294124.png]  
      可以明显看到，我们访问的元素被添加到了双向链表的末尾。

#### 示例二 ####

public class Test { 
    
        public static void main(String[] args) { 
            LinkedHashMap linkedHashMap = new LinkedHashMap(16,0.75f,false);
            linkedHashMap.put("1","1");
            linkedHashMap.put("2","2");
            linkedHashMap.put("3","3");
    
            Set set = linkedHashMap.entrySet();
            System.out.println(set);
    
            linkedHashMap.get("1");
            set = linkedHashMap.entrySet();
            System.out.println(set);
    
            linkedHashMap.get("2");
            set = linkedHashMap.entrySet();
            System.out.println(set);
        }
    
    }

如果我们按照访问插入顺序来访问链表还是上面的输出吗？

输出如下：  
![在这里插入图片描述][20191207153319905.png]  
      可以明显看到输出两者不同，符合我们对该方法的分析。

## 4.5 获取元素 ##

### 4.5.1 get(Object key) ###

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;
        }
    
        final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { 
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) { 
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do { 
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

如果查找到了元素，且`accessOrder`为`true`，则调用`afterNodeAccess()`方法把访问的节点移到双向链表的末尾。

（1）`LinkedHashMap`继承自`HashMap`，具有`HashMap`的所有特性；

（2）`LinkedHashMap`内部维护了一个双向链表存储所有的元素；

（3）如果`accessOrder`为`false`，则可以按插入元素的顺序遍历元素；

（4）如果accessOrder为true，则可以按访问元素的顺序遍历元素；

（5）`LinkedHashMap`的实现非常精妙，很多方法都是在`HashMap`中留的钩子（`Hook`），直接实现这些`Hook`就可以实现对应的功能了，并不需要再重写`put()`等方法；

（6）默认的`LinkedHashMap`并不会移除旧元素，如果需要移除旧元素，则需要重写`removeEldestEntry()`方法设定移除策略；

（7）`LinkedHashMap`可以用来实现`LRU`缓存淘汰策略；

## 4.6 LRU 实现 ##

`LRU`（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

所以我们可以这样做，刚被访问过的元素将其放到链表尾（链表头），刚被添加的元素也被放入到链表尾（链表头），而当缓存大小满了之后，则删除链表头（链表尾）的元素，这样便实现了LRU。

在`LinkedHashMap`中，如果我们访问了一个元素，则一定会调用`afterNodeAccess`方法，而该方法将链表中的节点放入到了链表尾，而在添加元素时，同样调用了该方法，所以我们只需要在缓存满时删除表头的元素即可。回到删除元素的方法`afterNodeInsertion`，在该方法中调用了`removeEldestEntry`方法，默认返回`false`，所以我们只要重写该方法即可。在缓存满时删除表头节点。

/** * @author wangzhao * @date 2019/12/7 16:26 */
    public class LRUCache extends LinkedHashMap { 
    
        // 缓存的最大容量
        private  int capacity;
    
        public LRUCache(int capacity){ 
            // 注意，这里一定要将 accessOrder 指定为 true，只有其为true，afterNodeAccess 方法才能生效
            super(capacity,0.75f,true);
            this.capacity = capacity;
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) { 
            return size() > this.capacity;
        }
    
        public static void main(String[] args) { 
            LRUCache lru = new LRUCache(3);
            lru.put("1","1");
            lru.put("2","2");
            lru.put("3","3");
    
            System.out.println(lru.entrySet());
            // 输出： [1=1, 2=2, 3=3]
            
            lru.get("1");
            System.out.println(lru.entrySet());
            // 输出： [2=2, 3=3, 1=1]
    
            lru.get("2");
            System.out.println(lru.entrySet());
    		// 输出： [3=3, 1=1, 2=2]
    
            lru.get("3");
            System.out.println(lru.entrySet());
    		// 输出： [1=1, 2=2, 3=3]
    
            lru.put("4","4");
            System.out.println(lru.entrySet());
            // 输出：[2=2, 3=3, 4=4]
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210813/3c5da493545244a98d74e5a448671a3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]: /images/20210813/cd58ad66e04f4b36aa22d78271e6a947.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]: /images/20210813/41a93d10a0c04e4b9e410f907c31c1bc.png
[2019120715294124.png]: /images/20210813/6fb7a545c5a240ddb89dc67986b02e55.png
[20191207153319905.png]: /images/20210813/91dc24da1aca4816854a7435e382109e.png