栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LRU算法实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LRU算法实现

什么是LRU算法?

LRU是一种缓存淘汰算法,比方说手机只能开三个应用,你开第四个应用的时候,最先打开的那个就会被关闭,而中途你用过哪个应用,哪个就会被提到最前面,剩下的顺序不变。

那么你要接受一个capacity参数作为缓存的最大容量,然后实现两个API,一个是put(key,val),另外一个是get(key),举个具体例子看看LRU如何工作:

//缓存容量为2
LRUCache cache = new LRUCache(2);
//cache就像一个队列
//最近使用的放在队头,久未使用的放在队尾

cache.put(1,1);

cache.put(2,2);
//cache = [(2,2),(1,1)];

cache.get(1);
//cache = [(1,1),(2,2)];

cache.put(3,3);
//cache = [(3,3),(1,1)];

cache.get(2);   //返回-1,未找到

cache.put(1,4);
//cache = [(1,4).(3,3)];

既然要用到键值对,那么肯定有map结构,而又需要方便地删除队尾元素,访问哪个元素以后还要放在队头,那么使用双向链表比较合适,这个数据结构长这样:

首先是双链表的节点类:

class Node {
    public int key,val;
    public Node next,prev;
    public Node(int k, int v){
        this.key = k;
        this.val = v;
    }
}

然后依靠此节点类构建一个双链表,实现几个需要的API:

class DoubleList{
    //链表头部添加节点
    public void addFirst(Node x);
    
    //删除链表中的x节点
    public void remove(Node x);
    
    //删除链表中的最后一个节点,并返回
    public Node removeLast();
    
    //返回链表长度
    public int size();
}

这里也可以解释为什么要用双向链表,因为我们有删除操作,删除一个节点不光要得到该节点本身的指针,也需要操作其前驱节点的指针。

先把逻辑理清楚:

HashMap map;

DoubleList cache;

int get(int key){
    if(key不存在){
        return -1;
    }
    else{
        将数据(key,val)移到开头;
        return val; 
    }
}

void put(int key,int val){
    Node x = new Node(key,val);
    if(key已经存在){
        把旧数据删除;
        将新数据x插入到开头
    }
    else{
        if(cache已满){
            删除最后一个节点腾位置
            删除map中映射到该数据的键
        }
        将新节点x插入到开头
        map中新建key对新节点x的映射
    }
}

实际代码实现:

class LRUCache {
    private HashMap map;
    
    private DoubleList cache;
    
    private int capacity;
    
    public LRUCache(int cap){
        this.capacity = cap;
        map  = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        int val = map.get(key).val;
        //利用put方法把数据提前
        put(key,val);
        return val;
    }
    
    public void put(int key,int val){
        //先把新节点x做出来
        Node x = new Node(key,val);
        if(map.containsKey(key)){
            cache.remove(map.get(key));
            cache.addFirst(x);
        }
        else{
            if(cache.size == capacity){
                Node last = cache.removeLast();
                //这里要把map中的键也删除
                map.remove(last.key);
            }
            cache.addFirst(x);
            //这里要在map中添加索引
            map.put(key,x);
        }
    }
}

到这里,你已经掌握了LRU算法的思想和实现了,就是在处理链表节点的同时不要忘了更新哈希表中对节点的映射


再补上一个完全实现代码:

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private Map map;

    
    private class ListNode {

        private Integer key;
        private Integer value;
        
        private ListNode pre;
        
        private ListNode next;

        public ListNode() {
        }

        public ListNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;

    
    private ListNode dummyHead;
    
    private ListNode dummyTail;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        dummyHead = new ListNode(-1, -1);
        dummyTail = new ListNode(-1, -1);
        // 初始化链表为 head <-> tail

        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
    }

    
    public int get(int key) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            int val = node.value;

            // 把当前 node 移动到双向链表的头部
            moveNode2Head(key);
            return val;
        } else {
            return -1;
        }
    }

    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 1、更新 value
            map.get(key).value = value;
            // 2、把当前 node 移动到双向链表的头部
            moveNode2Head(key);
            return;
        }

        // 放元素的操作是一样的

        if (map.size() == capacity) {
            // 如果满了
            ListNode oldTail = removeTail();

            // 设计 key 就是为了在这里删除
            map.remove(oldTail.key);
        }

        // 然后添加元素
        ListNode newNode = new ListNode(key, value);
        map.put(key, newNode);
        addNode2Head(newNode);
    }

    // 为了突出主干逻辑,下面是 3 个公用的方法

    
    private ListNode removeTail() {
        ListNode oldTail = dummyTail.pre;
        ListNode newTail = oldTail.pre;

        // 两侧结点建立连接
        newTail.next = dummyTail;
        dummyTail.pre = newTail;

        // 释放引用
        oldTail.pre = null;
        oldTail.next = null;

        return oldTail;
    }

    
    private void moveNode2Head(int key) {
        // 1、先把 node 拿出来
        ListNode node = map.get(key);

        // 2、原来 node 的前驱和后继接上
        node.pre.next = node.next;
        node.next.pre = node.pre;

        // 3、再把 node 放在末尾
        addNode2Head(node);
    }

    
    private void addNode2Head(ListNode newNode) {
        // 1、当前头结点
        ListNode oldHead = dummyHead.next;

        // 2、末尾结点的后继指向新结点
        oldHead.pre = newNode;

        // 3、设置新结点的前驱和后继
        newNode.pre = dummyHead;
        newNode.next = oldHead;

        // 4、更改虚拟头结点的后继结点
        dummyHead.next = newNode;
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978146.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号