乐趣区

关于java:LRU算法原理及其实现

jiezi

LRU 是什么

古代计算机，内存仍是相当低廉的，那么如果利用好、治理好无限的内存，来为用户提供更好的性能，是一个有意义的议题。

LRU(Least Recently Used) 即最近起码应用，属于典型的内存淘汰机制。

艰深的说，LRU 算法认为，最近被频繁拜访的数据会具备更高的留存，淘汰那些不常被拜访的数据。

LRU 算法实现思路

依据 LRU 算法的理念，咱们须要：
一个参数 cap 来作为最大容量
一种数据结构来存储数据，并且须要 1. 轻易地更新最新的拜访的数据。2. 轻易地找出最近起码被应用的数据，当达到 cap 时，清理掉。
在这里，咱们用到的数据结构是：hashmap+ 双向链表。
1. 利用 hashmap 的 get、put 办法 O(1)的工夫复杂度，疾速取、存数据。
2. 利用 doublelinkedlist 的特色（能够拜访到某个节点之前和之后的节点），实现 O(1)的新增和删除数据。

如下图所示：

当 key2 再次被应用时，它所对应的 node3 被更新到链表头部。

假如 cap=3，当 key4 创立、被拜访后，处于链表尾部的 node2 将被淘汰，key1 将被分明。

LRU 的简略实现

节点 node, 寄存 key、val 值、前节点、后节点

class Node{
    public int key;
    public int val;
    public Node next;
    public Node previous;

    public Node() {}

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

双向链表，属性有 size、头节点、尾节点。
提供 api：

  • addFirst(): 头插法入链表
  • remove(): 删除最初一个节点
  • remove(Node node): 删除特定节点
  • size()：获取链表长度
class DoubleList{
    private int size;
    private Node head;
    private Node tail;

    public DoubleList() {this.head = new Node();
        this.tail = new Node();
        size = 0;
        head.next = tail;
        tail.previous = head;
    }

    public void addFirst(Node node){
        Node temp = head.next;
        head.next = node;
        node.previous = head;
        node.next = temp;
        temp.previous = node;
        size++;
    }

    public void remove(Node node){if(null==node|| node.previous==null|| node.next==null){return;}

        node.previous.next = node.next;
        node.next.previous = node.previous;
        node.next=null;
        node.previous=null;
        size--;
    }

    public void remove(){if(size<=0) return;
        Node temp = tail.previous;
        temp.previous.next = temp.next;
        tail.previous = temp.previous;
        temp.next = null;
        temp.previous=null;
        size--;
    }

    public int size(){return size;}
}

LRU 算法实现类
API

  • get(int key): 为 null 返回 -1

  • put(int key, int value)

    • 若 map 中有，删除原节点，减少新节点
    • 若 map 中没有，map 和链表中新增新数据。
public class LRUCache {

    Map<Integer,Node> map;
    DoubleList cache;
    int cap;


    public LRUCache(int cap) {map = new HashMap<>();
        cache = new DoubleList();
        this.cap = cap;
    }

    public int get(int key){Node node = map.get(key);
        return  node==null? -1:node.val;

    }

    public void put(int key, int val){Node node = new Node(key,val);
        if(map.get(key)!=null){cache.remove(map.get(key));
            cache.addFirst(node);
            map.put(key,node);
            return;
        }

        map.put(key,node);
        cache.addFirst(node);
        if(cache.size()>cap){cache.remove();
        }

    }

    public static void main(String[] args) {
        //test, cap = 3
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        //<1,1> 来到链表头部
        lruCache.put(1,1);
        //<4,4> 来到链表头部，<2,2> 被淘汰。lruCache.put(4,4);
    }

}

LRU 利用场景

  • 底层的内存治理，页面置换算法
  • 个别的缓存服务，memcache\redis 之类
  • 局部业务场景

参考
LRU 策略详解和实现
LRU 原理以及利用场景

退出移动版