1.LRU 缓存机制可以通过哈希表辅以双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对
public class SingleLRU {
public class DlinkNode{
private int key;
private int value;
private DlinkNode pre;
private DlinkNode next;
public DlinkNode(){};
public DlinkNode(int key, int value){
this.key= key;
this.value = value;
}
}
private Map<Integer,DlinkNode> cache = new HashMap<>();
private int size;
private int capacity;
private DlinkNode head,tail;
public SingleLRU(int capacity){
this.size = 0;
this.capacity = capacity;
head = new DlinkNode();
tail = new DlinkNode();
head.next = tail;
tail.pre = head;
}
public int get(int key){
DlinkNode node = cache.get(key);
if(node == null){
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key,int value){
DlinkNode node = cache.get(key);
if(node != null){
node.value = value;
moveToHead(node);
}else{
node = new DlinkNode(key,value);
cache.put(key,node);
addToHead(node);
size++;
if(size > capacity){
DlinkNode dTail = removeTail();
cache.remove(dTail.key);
--size;
}
}
}
private void moveToHead(DlinkNode node){
removeNode(node);
addToHead(node);
}
private void removeNode(DlinkNode node){
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void addToHead(DlinkNode node){
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private DlinkNode removeTail(){
DlinkNode node = tail.pre;
removeNode(node);
return node;
}
public static void main(String[] args) {
SingleLRU lRUCache = new SingleLRU(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
int a = lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
int b = lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
int c = lRUCache.get(1); // 返回 -1 (未找到)
int d =lRUCache.get(3); // 返回 3
int e =lRUCache.get(4); // 返回 4
}
}
2.使用 ConcurrentHashMap+双向链表+ReadWriteLock实现线程安全的 LRU 缓存
public class ConcurrentCache<K,V> {
class DLinkNode<K,V>{
private K key;
private V value;
private DLinkNode<K,V> pre;
private DLinkNode<K,V> next;
public DLinkNode(){};
public DLinkNode(K key, V value){
this.key = key;
this.value = value;
}
}
private ConcurrentHashMap<K, DLinkNode<K,V>> cache = new ConcurrentHashMap<>();
private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
private Lock readLock = readWriteLock.readLock();
private Lock writeLock = readWriteLock.writeLock();
private int capacity;
private int size;
private DLinkNode<K,V> head,tail;
public ConcurrentCache(int capacity) {
this.capacity = capacity;
size = 0;
head = new DLinkNode();
tail = new DLinkNode();
head.next = tail;
tail.pre = head;
}
public <V> V get(K key) {
readLock.lock();
try {
DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
if(node != null){
moveToHead(node);
return node.value;
}
}finally {
readLock.unlock();
}
return null;
}
public void put(K key, V value) {
writeLock.lock();
try{
DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
if(node == null){
node = new DLinkNode(key,value);
addToHead(node);
cache.put(key,node);
size++;
if(size > capacity){
DLinkNode rNode = removeTail();
cache.remove(rNode.key);
size--;
}
}else{
node.value = value;
moveToHead(node);
}
}finally {
writeLock.unlock();
}
}
private void moveToHead(DLinkNode node){
removeNode(node);
addToHead(node);
}
private void removeNode(DLinkNode node){
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void addToHead(DLinkNode node){
node.pre = this.head;
node.next = this.head.next;
this.head.next.pre = node;
this.head.next = node;
}
private DLinkNode removeTail(){
DLinkNode rNode = this.tail.pre;
removeNode(rNode);
return rNode;
}
}
- 实现一个线程安全并且带有过期时间的 LRU 缓存
ScheduledExecutorService ：定时器线程池定时删除缓存
public class ConcurrentCache<K,V> {
public static void main(String[] args) {
ConcurrentCache<Integer,String> concurrentCache = new ConcurrentCache<>(3);
concurrentCache.put(1,"Java",3000);
concurrentCache.put(2,"C++",3000);
concurrentCache.put(3,"Python",1500);
System.out.println(concurrentCache.size());//3
try {
Thread.sleep(2000);
}catch (Exception e){
}
System.out.println(concurrentCache.size());//2
}
class DLinkNode<K,V>{
private K key;
private V value;
private DLinkNode<K,V> pre;
private DLinkNode<K,V> next;
public DLinkNode(){};
public DLinkNode(K key, V value){
this.key = key;
this.value = value;
}
}
private ConcurrentHashMap<K, DLinkNode<K,V>> cache = new ConcurrentHashMap<>();
private ScheduledExecutorService scheduledExecutorService;
private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
private Lock readLock = readWriteLock.readLock();
private Lock writeLock = readWriteLock.writeLock();
private int capacity;
private int size;
private DLinkNode<K,V> head,tail;
public ConcurrentCache(int capacity) {
this.capacity = capacity;
size = 0;
head = new DLinkNode();
tail = new DLinkNode();
head.next = tail;
tail.pre = head;
scheduledExecutorService = Executors.newScheduledThreadPool(3);
}
public <V> V get(K key) {
readLock.lock();
try {
DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
if(node != null){
moveToHead(node);
return node.value;
}
}finally {
readLock.unlock();
}
return null;
}
public void put(K key, V value,long expireTime) {
writeLock.lock();
try{
DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
if(node == null){
node = new DLinkNode(key,value);
addToHead(node);
cache.put(key,node);
size++;
if(size > capacity){
DLinkNode rNode = removeTail();
cache.remove(rNode.key);
size--;
}
if (expireTime > 0){
removeAfterExpireTime(key,expireTime);
}
}else{
node.value = value;
moveToHead(node);
}
}finally {
writeLock.unlock();
}
}
public int size() {
return cache.size();
}
private void removeAfterExpireTime(K key,long expireTime){
scheduledExecutorService.schedule(new Runnable() {
@Override
public void run() {
cache.remove(key);
removeKey(key);
}
},expireTime, TimeUnit.MILLISECONDS);
}
private void moveToHead(DLinkNode node){
removeNode(node);
addToHead(node);
}
private void removeKey(K key){
DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void removeNode(DLinkNode node){
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void addToHead(DLinkNode node){
node.pre = this.head;
node.next = this.head.next;
this.head.next.pre = node;
this.head.next = node;
}
private DLinkNode removeTail(){
DLinkNode rNode = this.tail.pre;
removeNode(rNode);
return rNode;
}
}
