LeetCode解题之十八:LRU

本文阅读 2 分钟
首页 代码,Java 正文

题目

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

分析

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是有用的,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。Redis中的内存淘汰算法有应用。因此通过构建缓存列表来实现使用数据的前移。

解题

class LRUCache { 
 
    private HashMap<Integer, Node> map;
    
    private DoubleList cache;
   
    private int cap;
    
    public LRUCache(int capacity) { 
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) { 
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
     
        put(key, val);
        return val;
    }
    
    public void put(int key, int val) { 
       
        Node x = new Node(key, val);
        
        if (map.containsKey(key)) { 
           
            cache.remove(map.get(key));
            cache.addFirst(x);
         
            map.put(key, x);
        } else { 
            if (cap == cache.size()) { 
            
                Node last = cache.removeLast();
                map.remove(last.key);
            }
         
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://blog.csdn.net/Diamond_Tao/article/details/117886239
-- 展开阅读全文 --
大白话讲解JDK源码系列:从头到尾再讲一遍ThreadLocal
« 上一篇 01-30
KillDefender 的 Beacon 对象文件 PoC 实现
下一篇 » 02-09

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复