LRU（Least recently used，最近最少使用）

佚名 6年前 (2019-05-09) 随笔 1740人围观抢沙发百度已收录

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。


/**
 * @Author: mly
 * @Date: Created in 2019/5/9
 * 如何来设计一款LRU算法呢？对于这种类似序列的结构我们一般可以选择链表或者是数组来构建。
 *
 * 差异对比：
 *
 * 数组 查询比较快，但是对于增删来说是一个不是一个好的选择
 * 链表 查询比较慢，但是对于增删来说十分方便O(1)时间复杂度内搞定
 * 有没有办法既能够让其搜索快，又能够快速进行增删操作。
 * 我们可以选择链表+hash表，hash表的搜索可以达到0(1)时间复杂度，这样就完美的解决我们搜索时间慢的问题了
 *
 * Hash表，在Java中HashMap是我们的不二选择
 * 链表，Node一个双向链表的实现，Node中存放的是数结构如下：
 */
public class Node<K,V> {
    private K key; private V value; private Node<K,V> prev; private Node<K,V> next; //通过HashMap中key存储Node的key,value存储Node,来建立Map对Node的映射关系 } /** * 构建双向链表节点ListNode，应包含key,value,prev,next这几个基本属性 * 对于Cache对象来说，我们需要规定缓存的容量，所以在初始化时，设置容量大小，然后实例化双向链表的head,tail，并让head.next->tail tail.prev->head，这样我们的双向链表构建完成 * 对于get操作,我们首先查阅hashmap，如果存在的话，直接将Node从当前位置移除，然后插入到链表的首部，在链表中实现删除直接让node的前驱节点指向后继节点，很方便.如果不存在，那么直接返回Null * 对于put操作，比较麻烦。 */

public class LRUCache<V> {
    /**
     * 容量
     */
    private int capacity = 1024; /** * Node记录表 */ private Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>(); /** * 双向链表头部 */ private ListNode<String, V> head; /** * 双向链表尾部 */ private ListNode<String, V> tail; public LRUCache(int capacity){ this(); this.capacity=capacity; } public LRUCache() { head = new ListNode<>(); tail = new ListNode<>(); head.next = tail; head.prev = head; tail.prev = head; tail.next = null; } public V get(String key) { ListNode<String, V> node = table.get(key); //如果Node不在表中,代表缓存中并没有 if (node == null) { return null; } //如果存在,则需要移动Node节点到表头  node.prev.next = node.next; node.next.prev = node.prev; //移动节点到表头 node.next = head.next; head.next.prev = node; node.prev = head; head.next = node; //存在缓存表  table.put(key, node); return node.value; } public void put(String key, V value) { ListNode<String, V> node = table.get(key); //如果Node不在表中，代表缓存中并没有 if (node == null) { if (table.size() == capacity) { //超过容量了 ,首先移除尾部的节点  table.remove(tail.prev.key); tail.prev = tail.next; tail.next = null; tail = tail.prev; } node = new ListNode<>(); node.key = key; node.value = value; table.put(key, node); } //如果存在，则需要移动Node节点到表头 node.next = head.next; head.next.prev = node; node.prev = head; head.next = node; } /** * 双向链表内部类 */ public static class ListNode<K, V> { private K key; private V value; ListNode<K, V> prev; ListNode<K, V> next; public ListNode(K key, V value) { this.key = key; this.value = value; } public ListNode() { } } @Override public String toString() { StringBuffer sb = new StringBuffer(); for (Map.Entry<String,ListNode<String,V>> map :table.entrySet()){ sb.append(map.getKey()+" "+map.getValue()); } return sb.toString(); } public static void main(String[] args) { LRUCache<ListNode> cache = new LRUCache<>(4); ListNode<String, Integer> node1 = new ListNode<>("key1", 1); ListNode<String, Integer> node2 = new ListNode<>("key2", 2); ListNode<String, Integer> node3 = new ListNode<>("key3", 3); ListNode<String, Integer> node4 = new ListNode<>("key4", 4); ListNode<String, Integer> node5 = new ListNode<>("key5", 5); cache.put("key1", node1); cache.put("key2", node2); cache.put("key3", node3); cache.put("key4", node4); cache.get("key2"); cache.put("key5", node5); cache.get("key2"); System.out.println(cache.toString()); }