手写LRU缓存

#一人分享一道面试手撕题#比较经典的题目,如果之前没写过的可能需要想一番,首先实现缓存最先想到的就是hashmap,O1级别的查找速度很适合做缓存,然后就是要实现lru,参考redis的zset底层实现,zset也是使用了两个数据结构跳表+hashmap,使用跳表实现排序,我们这里也是使用双向链表实现lru功能,每次查询对应数据的时候就将数据移除重新加到头部,也就是更新使用频率,附上代码如下
比较经典的题目,如果之前没写过的可能需要想一番,首先实现缓存最先想到的就是hashmap,O1级别的查找速度很适合做缓存,然后就是要实现lru,参考redis的zset底层实现,zset也是使用了两个数据结构跳表+hashmap,使用跳表实现排序,我们这里也是使用双向链表实现lru功能,每次查询对应数据的时候就将数据移除重新加到头部,也就是更新使用频率
//通过自定义节点,hashmap,哨兵节点
//删除时通过pre和next指针快速删除节点
//添加时只操作头尾,通过哨兵节点快速添加节点
class LRUCache {
    private class Node{
        //保留key,不然在删除尾结点的时候不能返回key让map也删除
        //而map又不知道尾结点是哪个
        int key,value;
        Node pre,next;
        Node(int key,int value){
            this.key=key;
            this.value=value;
        }
        Node(int key,int value,Node pre,Node next){
            this.key=key;
            this.value=value;
            this.pre=pre;
            this.next=next;
        }
    }
    private int capacity;
    //通过哨兵节点可以快速找到头结点和尾节点
    private Node dummy;
    //通过hashmap快速找到节点,通过节点pre指针和next指针快速实现删除
    private Map<Integer,Node> map=new HashMap();

    public LRUCache(int capacity) {
        this.capacity=capacity;
        //不能dummy=new Node(-1,-1,dummy,dummy)
        //这样会导致dummy的pre和next为null
        dummy=new Node(-1,-1);
        dummy.pre=dummy;
        dummy.next=dummy;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        //如果存在,更新使用频率(加到头部)
        Node node=map.get(key);
        remove(node);
        addFirst(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node;
        if(!map.containsKey(key)){
            while(map.size()>=capacity){
                int removeKey=removeLast();
                map.remove(removeKey);
            }
            node=new Node(key,value);
            addFirst(node);
        }else{
            //否则更新数值重新加入
            node=map.get(key);
            node.value=value;
            remove(node);
            addFirst(node);
        }
        map.put(key,node);

    }
    public void remove(Node node){
        Node pre=node.pre;
        Node next=node.next;
        pre.next=next;
        next.pre=pre;
    }
    public int removeLast(){
        Node tail=dummy.pre;
        remove(tail);
        return tail.key;
    }
    public void addFirst(Node node){
        //通过哨兵结点快速找到头结点
        Node head=dummy.next;
        head.pre=node;
        node.next=head;
        dummy.next=node;
        node.pre=dummy;
    }
}

手写LRU缓存

全站热榜

创作者周榜