使用LinkedHashMap实现LRU算法

谁践踏了优雅 2022-10-25 14:01 336阅读 0赞

LRU算法，最近最少使用原则，如果要实现该算法，可以借助LinkedHashMap数据结构，LinkedHashMap继承HashMap，底层使用哈希表和双向链表来保存所有元素，使用LinkedHashMap可以确保元素按照顺序进行存储。

默认情况下，LinkedHashMap是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据。

下面就基于这两种存储方式，简单展示一下如何实现LRU算法：

一、基于按添加顺序存储的方式实现LRU：

  1. public class LRUTest
  2. {
  3.     int capacity;
  4.     LinkedHashMap<Integer, Integer> cache;
  6.     LRUTest(int capacity)
  7.     {
  8.         cache = new LinkedHashMap<>();
  9.         this.capacity = capacity;
  10.     }
  12.     //访问元素
  13.     public int get(int key)
  14.     {
  15.         if(!cache.containsKey(key))
  16.         {
  17.             return -1;
  18.         }
  20.         //存在，先从链表头部删除删除，在插入到链表尾部
  21.         int val = cache.get(key);
  22.         cache.remove(key);
  23.         cache.put(key, val);
  25.         return val;
  26.     }
  28.     //添加元素
  29.     public void put(int key, int val)
  30.     {
  31.         if(cache.containsKey(key))
  32.         {
  33.             cache.remove(key);
  34.         }
  36.         //如果链表已经满了，则删除头部节点
  37.         if(cache.size() == capacity)
  38.         {
  39.             Set<Integer> keySet = cache.keySet();
  40.             Iterator<Integer> iterator = keySet.iterator();
  41.             cache.remove(iterator.next());
  42.         }
  44.         cache.put(key, val);
  45.     }
  46. }

二、基于按访问顺序存储的方式实现LRU：

该方式的核心就是继承LinkedHashMap，并设置LinkedHashMap的accessOrder参数为true，然后重写LinkedHashMap的removeEldestEntry()方法。

  1. public class LRUTest extends LinkedHashMap<String, String>
  2. {
  3.     private int capacity;
  5.     /**
  6.      * 当LinkedHashMap的accessOrder参数为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
  7.      */
  8.     public LRUTest(int capacity) {
  9.         super(16, 0.75f, true);
  10.         this.capacity = capacity;
  11.     }
  13.     /**
  14.      * LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
  15.      */
  16.     @Override
  17.     protected boolean removeEldestEntry(Map.Entry<String, String> eldest)
  18.     {
  19.         return size() > capacity;
  20.     }
  21. }

测试方法：

  1. public static void main(String[] args)
  2.     {
  3.         Map<String, String> linkedHashMap = new LRUTest(6);
  5.         linkedHashMap.put("1", "1");
  6.         linkedHashMap.put("2", "2");
  7.         linkedHashMap.put("3", "3");
  8.         linkedHashMap.put("4", "4");
  9.         linkedHashMap.put("5", "5");
  10.         linkedHashMap.put("6", "6");
  11.         linkedHashMap.put("7", "7");
  12.         linkedHashMap.put("8", "8");
  13.         linkedHashMap.put("9", "9");
  15.         System.out.println("size="+linkedHashMap.size());
  16.         System.out.println(linkedHashMap.get("8"));
  18.         linkedHashMap.forEach((k,v) ->{
  19.             System.out.print(k + ":"+ v +"  ");
  20.         });
  22.         System.out.println();
  23.         System.out.println("size="+linkedHashMap.size());
  24.     }

输出结果：

  1. size=6
  2. 8
  3. 4:4  5:5  6:6  7:7  9:9  8:8  
  4. size=6

发表评论

表情：
评论列表 （有 0 条评论，336人围观）

还没有评论，来说两句吧...

相关阅读