基于LinkedHashMap实现LRU缓存_开发_开发者

开发者 https://www.devze.com 2023-05-06 10:27 出处：网络作者： JAVA旭阳

目录概述分析LRU缓存实现总结概述 LinkedHashMap是Java集合中一个常用的容器，它继承了HashMap, 是一个有序的Hash表。那么该如何基于LinkedHashMap实现一个LRU缓存呢？这也是面试经常被问到的题目，主要是考察你对Ja

概述

LinkedHashMap是Java集合中一个常用的容器，它继承了HashMap, 是一个有序的Hash表。那么该如何基于LinkedHashMap实现一个LRU缓存呢？这也是面试经常被问到的题目，主要是考察你对Java集合容器的了解程度以及LinkedHashMap的实现原理。

分析

什么是LRU?

LRU（Least Recently Used）指的是最近最少使用，是一种缓存淘汰算法，淘汰掉那个最少使用的的数据。

LinkedHashMap是有序的，它默认通过双向链表维护元素的插入顺序，同时，通过构造函数设置AccessOrder属性为true的情况，维护元素的访问顺序，这里的访问包括插入、修改、查询等元素，每次操作都会记录顺序，所以LRU缓存其实是包括访问的，所以我们需要通过构造函数设置LinkedHashMap设置accessOrder为true。
已经解决了顺javascript序的问题，也就是最近访问的会在双向链表的尾部，最老的数据会在头部。那么如何删除头部的元素呢？其实LinkedHashMap也提供了一个回调函数removeEldestEntry，它也会在添加元素的时候调用，默认返回false，我们可以通过重写这个方法的逻辑，如果LinkedHashMap大于缓存指定数量，就进行淘汰。

基于LinkedHashMap实现LRU缓存

LRU缓存实现

场景：我们需要设计一个缓存最多只能存储10个元素，当元素个数超过10的时候，删除（淘汰）那些最近最少使用的数据，仅保存热点数据。

public class LRUCache<K, V> extends LinkeandroiddHashMap<K, V> {

    /**
     * 缓存允许的最大容量
     */
    private final int maxSize;

    public LRUCache(int initialCapacity, int maxSize) {
        // accessOrder必须为true
        super(initialCapacity, 0.75f, true);
        this.maxSize = maxSize;
    }

    // 重写
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当键值对个数超过最大容量时，返回true，触发删除操作
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(5, 5);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        cache.put("4", "4");
        // 做一次查询
        cache.get("1");
        cache.put("5", "5");
        cache.pujavascriptt("6"开发者_Go学习, "6");
        cache.put("7", "7");编程
        System.out.println(snUFncache);
    }

}

运行结果：