缓存LRU算法(哈希链表)

缓存LRU

LRU算法实际上是设计一个数据结构：首先要接收一个capacity参数缓存最大容量，然后实现两个API，一个put(key,val) ，一个是get(key)方法获取key对应的val，若key不存在则返回-1

get和put必须是O(1)

1.LRUCache类（哈希链表）

代码语言：javascript复制

public class LRUCache{
    
    private HashMap<Integer,Node> map;
    
    private DoubleList cache;
    
    //capacity
    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);
        }
    }
}

2.Node类

代码语言：javascript复制

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

3.DoubleList类

代码语言：javascript复制

class DoubleList{
    
    public void addFirst(Node x);
    
    public void remove(Node x);
    
    public Node removeLast();
}

腾讯云开发者社区

0 人点赞