LeetCode刷题-LRU - LeetCode刷题 | Windlinxy's Blog = 沨临 = 记录回忆，分享经验，慢慢进步

# LRU 缓存

146.LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

一开始想到是使用双向链表，但是双向链表的查询是 O (n) 的，O (1) 的查询自然就是哈希表了

PUT操作 ：

添加元素时判断 key 是否存在（HashMap 查找）

存在
1. 重新赋值
2. 将节点从原有位置抽离
3. 节点放到链表头部
不存在
1. 判断容量已经满了？（用 count 变量记录 cache 中元素数量）
  - 没满：新建一个节点 newNode 插入链表头部
  - 满了：
    1. 将尾部节点删除
    2. 新建节点 newNode 插入头部
2. HashMap 存放 < key, newNode >

GET操作 ：

从 HashMap 取节点
- 为 null 返回 - 1
- 不为 null
  1. 将节点从原有位置抽离
  2. 节点放到链表头部

AC 之后考虑并发问题，LRU 本身就是操作系统的内存淘汰机制，需要考虑并发问题：如果 get 的同时

在多线程的情况下， get() 移动节点操作和 put() 整个方法加锁来保证节点的顺序正常。

import java.util.HashMap;

import java.util.HashMap;
import java.util.concurrent.locks.LockSupport;

class LRUCache {
    /**
     * 容量
     */
    private final int capacity;
    /**
     * head.next 指向的是最近最多使用的节点
     */
    private final Node head;
    /**
     * tail.prev 指向的是最近最少使用的节点
     */
    private final Node tail;
    private final HashMap<Integer, Node> hash;

    class Node {
        Node next, prev;
        int key, val;

        public Node() {
        }

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

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

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.hash = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 查找节点
        Node nNode = hash.get(key);
        if (nNode != null) {
            unLinkedNode(nNode);
            moveToHead(nNode);
            return nNode.val;
        }
        return -1;
    }

    public synchronized void put(int key, int value) {
        Node nNode = hash.get(key);
        if (nNode == null) {
            if (hash.size() == capacity) {
                hash.remove(tail.prev.key);
                removeTail();
            }
            nNode = new Node(key, value);
            hash.put(key, nNode);
        } else {
            nNode.val = value;
            unLinkedNode(nNode);
        }
        moveToHead(nNode);
    }

    /**
     * 将节点放到链表头部
     */
    private void moveToHead(Node cur) {
        head.next.prev = cur;
        cur.next = head.next;
        head.next = cur;
        cur.prev = head;
    }

   /**
    * 将节点从原有链表拿出来
    */
    private void unLinkedNode(Node cur) {
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
    }

    /**
     * 淘汰最近最少使用的节点（尾节点）
     */
    private void removeTail() {
        unLinkedNode(tail.prev);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

# 引申

LRU 全程 Least Recently Used，即最近最少使用的页面置换算法，是服务虚拟页式存储管理服务的，实现思想是读取的数据会更新到 LRU 列表最前端，当容量满的时候会淘汰尾部数据，来达到一个最近最少使用的数据淘汰功能。

根据局部性原理（包括空间局部性和时间局部性，一条指令执行后在将来的一段时间内可能会再次执行（热点代码），一个数据被访问后可能会再次访问，或者这个数据相邻的数据很大概率会再次访问到）。

CSAPP 关于局部性的论述：

在一个具有良好时间局部性的程序中，被引用过的内存位置很可能在不远的将来再被多次引用。
在一个具有良好空间局部性的程序中，一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

个人思考：局部性原理是无处不在的，LRU 就是基于局部性原理的一个体现。

# LRU 缓存

# 引申

3月2日LeetCode刷题

缺失的第一个正数-LeetCode刷题