LRU算法java数据结构实现

xiaoxiao2021-02-28  24

LRU:(least recently used) 最近最少使用算法。LRU算法的java中数据结构的实现是一个LRU算法在面试中经常被问到的问题,我们可以用LinkedList来表示最近和最少使用。将访问过的数据用LinkedList数据结构进行存储,如果查找最少使用,直接返回LinkedList的尾节点即可。如果添加一个最近访问的数据a,可以将a从链表中的位置删除,移到链表的头部。

但是链表中查询数据DATA的位置一般访问速度慢,所以需要借助其它数据结构来完成查找,我们知道HashMap是一个高效的查询数据结构。如果我们将该数据DATA作为键,DATA对应的节点作为值,存储在HashMap中,那么,我们可以得到查询复杂度为O(1)的操作。

JAVA中已经帮助我们实现了一个这样的数据结构,LinkedHashMap.LinkedHashMap存放的键值对和存放时的位置一致。不会变化,可以设置LinkedHashMap按照插入的顺序排序,也可以按照访问的顺序排序,最先访问的放置在最后面,最近访问的在最前面。

LinkedHashMap自身已经实现了顺序存储,默认情况下是按照元素的添加顺序存储,也可以启用按照访问顺序存储,即最近读取的数据放在最前面,最早读取的数据放在最后面,然后它还有一个判断是否删除最老数据的方法,默认是返回false,即不删除数据,我们使用LinkedHashMap实现LRU缓存的方法就是对LinkedHashMap实现简单的扩展,下面是简单实现。

import java.util.LinkedHashMap; import java.util.Map;   public LRUCache<K, V> extends LinkedHashMap<K, V> {    private int cacheSize;  //缓存值大小      public LRUCache( int cacheSize) {      super ( 16 , 0.75 , true );  //true设置按照访问顺序排序      this .cacheSize = cacheSize;    }      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {      return size() >= cacheSize;  //如果LinkedHashMap的大小超过缓存值,返回true删除最早的数据    } }

         

 
转载请注明原文地址: https://www.6miu.com/read-1650083.html

最新回复(0)