• ㊗️
• 大家
• 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.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4


1. 检查是不是 tail
3. map 的添加和删除
4. capacity 的添加和删除

## Code

### 方法 1

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 tail;

public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
tail = null;
}

public int get(int key) {
Node node = map.get(key);
if (node == null) {
return -1;
}
// 如果node已经是最新的元素了，那就可以直接返回了
if (node != tail) {
} else {
// 要把它取出来，然后把它前边和后边的点连在一起
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) {
} 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) {
// 后边会减少容量
capacity++;
}
// 如果是链表中的第一个点
} else {
tail.next = newNode;
newNode.pre = tail;
newNode.next = null;
}

tail = newNode;
map.put(key, newNode);
// 减少一个容量
capacity--;
}
}
}


### 方法 2

class Solution{
int initialCapacity,
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 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);
}
}


ranking 通过 API 得到的. 原本 LRU cache 是根据 data 的使用次数来做 rank 的, 但是现在 rank 是直接调用 API 得到的. 当 cache 满了, 新的数据要进来, 要比较新数据的 rank 和 cache 里面最小的 rank, 把最小 rank 的数据去掉, 大的留下

import java.util.concurrent.locks.Lock;

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;

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) {
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 {
}

}

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.