146. LRU Cache
JIAKAOBO
LeetCode
感谢赞助!
- ㊗️
- 大家
- offer
- 多多！
Problem
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up: Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /_ capacity _/ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
需要的步骤
- 检查是不是 tail
- 检查是不是 head
- map 的添加和删除
- capacity 的添加和删除
Code
实现 LRU 通常使用 HashMap + double Linked List
方法 1
自己构建 double linked list 实现
class LRUCache {
class Node {
int key;
int value;
Node next;
Node pre;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private HashMap<Integer, Node> map;
private int capacity;
// 整个链表的头部，也就是最老的元素
private Node head;
// 整个链表的尾部，也就是最新的元素
private Node tail;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
head = null;
tail = null;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) {
return -1;
}
// 如果node已经是最新的元素了，那就可以直接返回了
if (node != tail) {
// 如果node是head，需要把它移到末尾
if (node == head) {
head = head.next;
} else {
// node不是head
// 要把它取出来，然后把它前边和后边的点连在一起
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 把这个点放到最后
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
// 已经存在这个node
// 只需要更新node的值
if (node != null) {
node.value = value;
if (node != tail) {
if (node == head) {
head = head.next;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
} else {
// 需要插入新的节点了
Node newNode = new Node(key, value);
if (capacity == 0) {
map.remove(head.key);
head = head.next;
// 后边会减少容量
capacity++;
}
// 如果是链表中的第一个点
if (head == null) {
head = newNode;
} else {
tail.next = newNode;
newNode.pre = tail;
newNode.next = null;
}
tail = newNode;
map.put(key, newNode);
// 减少一个容量
capacity--;
}
}
}
方法 2
使用 Java 自带的 LinkedHashMap 数据结构够实现 LRU
class Solution{
public void LinkedHashMap(
int initialCapacity,
float loadFactor,
boolean accessOrder){
}
}
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
Parameters: initialCapacity - the initial capacity
loadFactor - the load factor, loadFactor is a metric that determines when to increase the size of the LinkedHashMap automatically. By default, this value is 0.75 which means that the size of the map is increased when the map is 75% full.
accessOrder - the ordering mode - true for access-order, false for insertion-order
Throws: IllegalArgumentException - if the initial capacity is negative or the load factor is nonpositive
class LRUCache {
private LinkedHashMap<Integer, Integer> map;
private final int CAPACITY;
public LRUCache(int capacity) {
CAPACITY = capacity;
map = new LinkedHashMap<Integer, Integer>(CAPACITY, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > CAPACITY;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}
Follow up
ranking 通过 API 得到的. 原本 LRU cache 是根据 data 的使用次数来做 rank 的, 但是现在 rank 是直接调用 API 得到的. 当 cache 满了, 新的数据要进来, 要比较新数据的 rank 和 cache 里面最小的 rank, 把最小 rank 的数据去掉, 大的留下
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
class Item {
public int key;
public int val;
public int rank;
}
class DataSource {
public DataSource() {
}
public Item getItem(int key) {
return new Item();
}
}
class BestFirstCache {
int capacity;
HashMap<Integer, Integer> map;
PriorityQueue<Item> queue;
DataSource dataSource;
private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
private Lock readLock = readWriteLock.readLock();
private Lock writeLock = readWriteLock.writeLock();
public init(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.queue = new PriorityQueue<Item>((a, b) -> {
return a.rank - b.rank;
});
dataSource = new DataSource();
}
public int get(int key) {
readLock.lock();
try{
if (!map.containsKey(key)) {
Item item = dataSource.getItem(key);
put(item);
}
if (map.containsKey(key)) {
return map.get(key);
} else {
throw new NoSuchElementException();
}
} finally {
readLock.unlock();
}
}
public void put(Item item) {
int key = item.key;
int value = item.val;
map.put(key, value);
queue.offer(item);
if (map.size() >= capacity) {
Item minRank = queue.poll();
map.remove(minRank.key);
}
}
}
multi access 保证读写安全
- Happen in highly concurrent environment
- Assume counter=3
- Two requests read counter from Redis at the same time
- After that, count is updated to 4, but it should be 5
- Common solution
- Lock
- System becomes slow
- Better solution
- Lua script and sorted sets data structure in Redis
- Lua (/ˈluːə/) is a lightweight, high-level, multi-paradigm programming language designed primarily for embedded use in applications.