LRU的多线程版本，这个答案有问题吗 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

LRU的多线程版本，这个答案有问题吗

LRU的多线程版本，这个答案有问题吗# JobHunting - 待字闺中

y*r2017-01-21 08:01

1 楼

买点啥好呢？

S*C2017-01-21 08:01

2 楼

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

}

m*r2017-01-21 08:01

3 楼

taotao

【在 y***r 的大作中提到】

: 买点啥好呢？

S*C2017-01-21 08:01

4 楼

这题很常见，但没有公认正确的好答案啊
下面一种答案用了JAVA的API，而且时间复杂度较高

m*l2017-01-21 08:01

5 楼

晶晶

【在 y***r 的大作中提到】

: 买点啥好呢？

S*C2017-01-21 08:01

6 楼

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