S*******C
发帖数: 822 | 1 public class LRUCache {
private int capacity;
//key : key, value : node
private Map map;
private Node prehead = new Node(-1, -1);
private Node posttail = new Node(10, 10);
public LRUCache(int capacity) {
map = new HashMap<>(capacity);
this.capacity = capacity;
connect(prehead, posttail);
}
public int get(int key) {
synchronized(map) {
Node p = map.get(key);
if(p == null) {
return -1;
}
moveToHead(p);
return p.val;
}
}
public void put(int key, int val) {
synchronized(map) {
Node p = map.get(key);
if(p == null) {
if(map.size() == capacity){
removeTail();//tail is the least recently used node, so
we remove it
}
p = new Node(key, val);
insertHeadToList(p);
map.put(key, p);
}else{
p.val = val;
moveToHead(p);
}
}
}
private void moveToHead(Node p){
removeNodeFromList(p);
insertHeadToList(p);
}
//remove a given node p from doubly linked list, but we don't delete it
from map
private void removeNodeFromList(Node p){
p.pre.next = p.next;
p.next.pre = p.pre;
}
//remove tail from doubly linked list. Moreover, we delete it from map
void removeTail() {
Node tail = posttail.pre;
removeNodeFromList(tail);
map.remove(tail.key);
}
private void insertHeadToList(Node p) {
Node oldHead = prehead.next;
connect(prehead, p);
connect(p, oldHead);
}
private void connect(Node p, Node q) {
p.next = q;
q.pre = p;
}
//Doubly Linked List node
private class Node {
public Node pre;
public Node next;
public int key;
public int val;
Node(int key, int val) {
this.key = key;
this.val = val;
pre = null;
next = null;
}
}
} | S*******C
发帖数: 822 | 2 这题很常见，但没有公认正确的好答案啊
下面一种答案用了JAVA的API，而且时间复杂度较高 | S*******C
发帖数: 822 | 3 import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
public class LRUCache {
private final int capacity;
private ConcurrentLinkedQueue queue;
private ConcurrentHashMap map;
public LRUCache(final int capacity) {
this.capacity = capacity;
this.queue = new ConcurrentLinkedQueue();
this.map = new ConcurrentHashMap(capacity);
}
//Check whether the items exists in the cache. Returns null if key doesn't
exists in the cache.
public V get(final K key) {
V val = map.get(key);
if(val != null) {
queue.remove(key);
queue.add(key);
}
return val;
}
//Add new val to the LRU Cache. If the key already exists, the key will be
promoted to the front of the cache.
//Neither the key nor the val can be null.
public synchronized void set(final K key, final V val) {
if(key == null || val == null) {
throw new NullPointerException();
}
if (map.containsKey(key)) {
queue.remove(key);
}
while (queue.size() >= capacity) {
K expiredKey = queue.remove();
if (expiredKey != null) {
map.remove(expiredKey);
}
}
queue.add(key);
map.put(key, val);
}
} | c******f
发帖数: 243 | 4 purge / expire 的function呢? | S*******C
发帖数: 822 | 5 leetcode上没要求
expire是要定期清除expired keys
purge是要干啥？
【在 c******f 的大作中提到】
: purge / expire 的function呢?
| z*****6
发帖数: 16 | 6 楼主的map不是synchronizedMap或concurrentMap没问题吗？你lock的是map，但是不
lock内部的node啊？面试官没有challenge你？ |
|
