LinkedHashMap底层实现+LRU缓存实现

一、介绍

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

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

二、函数介绍

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 相关知识】，并且【短时间在面试方面有跨越式提升】

面试路上，你不孤单！