LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择距离最近时间最久未使用的页面予以淘汰。其核心思想是“如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小”。
常见使用场景:内存管理中的页面置换算法、缓存淘汰中的淘汰策略等。
设计的LRU数据结构需要实现get和set方法
get(key):若缓存中存在key,返回对应的value,否则返回-1
set(key,value):若缓存中存在key,替换其value,否则插入key及其value,如果插入时缓存已经满了,应该使用LRU算法把最近最久没有使用的key踢出缓存。
LRU原理和Redis实现——一个今日头条的面试题
实现1:使用双向链表+HashMap
整体设计思路是使用HashMap的key存储key,这样可以做到set和get的时间复杂度都是O(1),而HashMap的Value指向双向链表实现的LRU的Node节点,如图所示:
class DLinkedNode {
String key;
int value;
DLinkedNode pre;
DLinkedNode post;
}
public class LRUCache {
private Hashtable<String, DLinkedNode> cache = new Hashtable<>();
private int count;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
public int get(String key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1; // should raise exception here.
}
// move the accessed node to the head;
this.moveToHead(node);
return node.value;
}
public void set(String key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
this.cache.put(key, newNode);
this.addNode(newNode);
++count;
if (count > capacity) {
// pop the tail
DLinkedNode tail = this.popTail();
this.cache.remove(tail.key);
--count;
}
} else {
// update the value.
node.value = value;
this.moveToHead(node);
}
}
/**
* Always add the new node right after head;
*/
private void addNode(DLinkedNode node) {
node.pre = head;
node.post = head.post;
head.post.pre = node;
head.post = node;
}
/**
* Remove an existing node from the linked list.
*/
private void removeNode(DLinkedNode node) {
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;
pre.post = post;
post.pre = pre;
}
/**
* Move certain node in between to the head.
*/
private void moveToHead(DLinkedNode node) {
this.removeNode(node);
this.addNode(node);
}
// pop the current tail.
private DLinkedNode popTail() {
DLinkedNode res = tail.pre;
this.removeNode(res);
return res;
}
}
实现2:直接使用LinkedHashMap
public class LRU<K, V> {
/**
* LinkedHashMap负载因子默认0.75
*/
private static final float hashLoadFactory = 0.75f;
private LinkedHashMap<K, V> map;
private int cacheSize;
/**
* @param cacheSize
* 容量
*/
public LRU(int cacheSize) {
this.cacheSize = cacheSize;
int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;
//如果accessOrder为true的话,则会把访问过的元素放在链表后面,放置顺序是访问的顺序
//(LinkedHashMap里面的get方法,当accessOrder为true,会走afterNodeAccess方法将节点移到最后)
//如果accessOrder为flase的话,则按插入顺序来遍历
map = new LinkedHashMap<K, V>(capacity, hashLoadFactory, true) {
private static final long serialVersionUID = -5291175172111746517L;
/*
* 当map容量大于LRU的容量时,删除最近最少使用的数据
*/
@Override
protected boolean removeEldestEntry(Entry<K, V> eldest) {
return size() > LRU.this.cacheSize;
}
};
}
public synchronized V get(K key) {
return map.get(key);
}
public synchronized void put(K key, V value) {
map.put(key, value);
}
public synchronized void clear() {
map.clear();
}
public synchronized int usedSize() {
return map.size();
}
public void print() {
for (Map.Entry<K, V> entry : map.entrySet()) {
System.out.print(entry.getValue() + "--");
}
System.out.println();
}
}
网友评论