LRU的设计与实现(算法村第五关黄金挑战)

2024-01-08 16:48:16

146. LRU 缓存 - 力扣(LeetCode)

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

用一张图来理解整个流程

假设内存只能容纳3个页面,按照 7 0 1 2 0 3 0 4 的次序访问页面。假设内存按照栈的方式来描述访问时间:上面是最近访问的,下面是最远时间访问的,那LRU就是这样工作的:

在这里插入图片描述

HashMap + 双向链表

class LRUCache
{
    /**
     * 双向链表的结点
     */
    class Node
    {
        int key;    //结点的标识
        int value;  //结点的值
        Node pre;
        Node next;

        public Node(){}

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

    Node dummyHead; //虚拟头结点
    Node dummyTail; //虚拟尾结点
    /**
     * 用于定位结点的HashMap
     */
    HashMap<Integer, Node> hashMap = new HashMap<>();
    int capacity;   //容量大小
    int size; //当前缓存大小

    public LRUCache(int capacity)
    {
        this.capacity = capacity;
        this.size = 0;

        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
    }

    /**
     * 移除结点
     */
    public void remove(Node node)
    {
        //node前驱的后继改为node的后继
        node.pre.next = node.next;
        //node后继的前驱改为node的前驱
        node.next.pre = node.pre;
    }

    /**
     * 将独立的结点添加到链表头部
     */
    public void addToHead(Node node)
    {
        //头插法
        node.pre = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.pre = node; //原先表首结点的前驱改为node
        dummyHead.next = node;
    }

    /**
     * 将双向链表中的结点移动到表首
     */
    public void moveToHead(Node node)
    {
        remove(node);
        addToHead(node);
    }


    public int get(int key)
    {
        Node node = hashMap.get(key);

        //如果链表没有这个结点,直接返回-1
        if (node == null)
            return -1;

        //存在的话,先将它提到表首,再返回结点的值
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value)
    {
        Node node = hashMap.get(key);

        //如果链表没有这个结点,则生成一个新结点,并放在表首
        if(node == null)
        {
            Node newNode = new Node(key, value);
            addToHead(newNode);

            hashMap.put(key, newNode);  //在哈希表中记录这个新结点

            //只有添加新结点的情况下才会时缓存大小变化
            size++;

            //若put之后超出容量,则在链表中删除尾结点,并在哈希表中除名
            if (size > capacity)
            {
                Node tail = dummyTail.pre;
                remove(tail);

                hashMap.remove(tail.key);
            }
        }
        else    //如果已经存在,则将node提到表首,并更新value值
        {
            moveToHead(node);
            node.value = value;
        }
    }
}

文章来源:https://blog.csdn.net/cjj2543107638/article/details/135396629
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。