LinkedHashMap底层实现+LRU缓存实现

秒速五厘米 2021-09-21 05:16 366阅读 0赞

### 一、介绍 ###

LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条**双向链表**，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。**除此之外，LinkedHashMap 对访问顺序也提供了相关支持**。在一些场景下，该特性很有用，比如**缓存**。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表或红黑树组成。LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

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

### 二、函数介绍 ###

1.LinkeHashMap在每次插入、删除后，都会调用一个函数来进行 双向链表的维护 ，准确的来说，是有三个函数来做这件事，这三个函数都统称为 回调函数 ，这三个函数分别是：

*  void afterNodeAccess(Node<K,V> p) \{ \}  
    其作用就是在访问元素之后，将该元素放到双向链表的尾巴处
 *  void afterNodeRemoval(Node<K,V> p) \{ \}  
    其作用就是在删除元素之后，将元素从双向链表中删除，
 *  void afterNodeInsertion(boolean evict) \{ \}  
    在插入新元素之后，需要回调函数判断是否需要移除一直不用的某些元素！

2.再介绍一下 LinkedHashMap 的构造函数！  
其主要是两个构造方法，一个是继承 HashMap ，**一个是可以选择 accessOrder 的值 (默认 false，代表按照插入顺序排序) 来确定是按插入顺序还是读取顺序排序**。

/** * //调用父类HashMap的构造方法。 * 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;
    }
    // 这里的 accessOrder 默认是为false，如果要按读取顺序排序需要将其设为 true
    // initialCapacity 代表 map 的 容量，loadFactor 代表加载因子 (默认即可)
    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { 
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

### 三、LRU缓存算法实现 ###

页置换算法，最近最少使用算法：当缓存达到容量的时候，总是置换出最近一段时间内最长时间未被使用的元素。

继承LinkedHashMap，并重写removeEldestEntry函数，即可很轻松的实现这个功能。

import java.util.LinkedHashMap;
    class LRUCache extends LinkedHashMap<Integer,Integer> { 
    
        private int limit;
    
        public LRUCache(int capacity) { 
            super(capacity,0.75f,true);
            limit = capacity;
        }
        
        public int get(int key) { 
        	// 这里选用getOrDefault函数而不选用get函数，是题目要求返回-1，而不是返回空
            return super.getOrDefault(key,-1);
        }
        
        public void put(int key, int value) { 
            super.put(key,value);
        }
    
        @Override
        public boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) { 
            return size() > limit;
        }
    }

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

**【Java 面试那点事】**

**这里致力于分享 Java 面试路上的各种知识，无论是技术还是经验，你需要的这里都有！**

**这里可以让你【快速了解 Java 相关知识】，并且【短时间在面试方面有跨越式提升】**

**面试路上，你不孤单！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/76c2f4ab69944d4ab4ad22409be7aada.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/d646afcf7b664c84b252bbfa00b58f29.png