溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了Java實現一個基于LRU時間復雜度為O(1)的緩存的方法，內容清晰明了，對此有興趣的小伙伴可以學習一下，相信大家閱讀完之后會有幫助。
LRU：Least Recently Used最近最少使用，當緩存容量不足時，先淘汰最近最少使用的數據。就像JVM垃圾回收一樣，希望將存活的對象移動到內存的一端，然后清除其余空間。
緩存基本操作就是讀、寫、淘汰刪除。
讀操作時間復雜度為O(1)的那就是hash操作了，可以使用HashMap索引 key。
寫操作時間復雜度為O(1)，使用鏈表結構，在鏈表的一端插入節點，是可以完成O(1)操作，但是為了配合讀，還要再次將節點放入HashMap中，put操作最優是O(1)，最差是O(n)。
不少童鞋就有疑問了，寫入時又使用map進行了put操作，為何緩存不直接使用map？沒錯，首先使用map存儲了節點數據就是采用空間換時間，但是淘汰刪除不好處理，使用map如何去記錄最近最少使用(涉及到時間、頻次問題)。so，使用鏈表可以將活躍節點移動到鏈表的一端，淘汰時直接從另一端進行刪除。
public class LruCache<K,V> {
/** 這里簡單點直接初始化了*/
private int capacity = 2;
private int size = 0;
private HashMap<K,DoubleListNode<K,V>> cache = new HashMap<>(capacity);
private DoubleListNode<K,V> lruNode = new DoubleListNode<K, V>(null,null,null,null);
private DoubleListNode<K,V> mruNode = new DoubleListNode<K, V>(null,null,null,null);
public V get(K key){
DoubleListNode<K,V> target = cache.get(key);
if (target == null) {
return null;
}
/** 使用過就移動到右側 */
move2mru(target);
return target.value;
}
public void put(K key,V value){
if(cache.containsKey(key)){
DoubleListNode<K,V> temp = cache.get(key);
temp.value = value;
/** 使用過就移動到右側 */
move2mru(temp);
return;
}
/** 容量滿了清除左側 */
if(size >= capacity){
evict4lru();
}
DoubleListNode<K,V> newNode = new DoubleListNode<>(mruNode,null,key,value);
if(size == 0){
lruNode.next = newNode;
}
mruNode.next = newNode;
mruNode = newNode;
cache.put(key,newNode);
size++;
}
private void move2mru(DoubleListNode<K,V> newMru){
DoubleListNode<K,V> pre = newMru.pre;
DoubleListNode<K,V> next = newMru.next;
pre.next = next;
newMru.pre = mruNode;
mruNode.next = newMru;
mruNode = newMru;
}
private void evict4lru(){
cache.remove(lruNode.next.key);
lruNode.next = lruNode.next.next;
size--;
}
public String toString(){
StringBuffer sb = new StringBuffer("lru -> ");
DoubleListNode<K,V> temp = lruNode;
while(temp!=null){
sb.append(temp.key).append(":").append(temp.value);
sb.append(" -> ");
temp = temp.next;
}
sb.append(" -> mru ");
return sb.toString();
}
public static void main(String[] args) {
LruCache<String,String> cache = new LruCache<>();
cache.put("1","1");
System.out.println(cache);
cache.get("1");
cache.put("2","2");
System.out.println(cache);
cache.put("3","3");
System.out.println(cache);
cache.put("4","4");
System.out.println(cache);
}
}
class DoubleListNode<K,V>{
K key;
V value;
DoubleListNode<K,V> pre;
DoubleListNode<K,V> next;
public DoubleListNode(K key,V value){
this.key = key;
this.value = value;
}
public DoubleListNode(DoubleListNode<K,V> pre,DoubleListNode<K,V> next,K key,V value){
this.pre = pre;
this.next = next;
this.key = key;
this.value = value;
}
}這里使用鏈表，及HashMap完成了基于LRU的緩存，其中HashMap主要用來快速索引key，鏈表用來完成LRU機制。當然尚有許多不足，包括緩存移除remove，緩存ttl，線程安全等。
看完上述內容，是不是對Java實現一個基于LRU時間復雜度為O(1)的緩存的方法有進一步的了解，如果還想學習更多內容，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
