LRU：Least Recently Used最近最少使用，當(dāng)緩存容量不足時(shí)，先淘汰最近最少使用的數(shù)據(jù)。就像JVM垃圾回收一樣，希望將存活的對(duì)象移動(dòng)到內(nèi)存的一端，然后清除其余空間。

緩存基本操作就是讀、寫(xiě)、淘汰刪除。

讀操作時(shí)間復(fù)雜度為O(1)的那就是hash操作了，可以使用HashMap索引 key。

寫(xiě)操作時(shí)間復(fù)雜度為O(1)，使用鏈表結(jié)構(gòu)，在鏈表的一端插入節(jié)點(diǎn)，是可以完成O(1)操作，但是為了配合讀，還要再次將節(jié)點(diǎn)放入HashMap中，put操作最優(yōu)是O(1)，最差是O(n)。

不少童鞋就有疑問(wèn)了，寫(xiě)入時(shí)又使用map進(jìn)行了put操作，為何緩存不直接使用map？沒(méi)錯(cuò)，首先使用map存儲(chǔ)了節(jié)點(diǎn)數(shù)據(jù)就是采用空間換時(shí)間，但是淘汰刪除不好處理，使用map如何去記錄最近最少使用(涉及到時(shí)間、頻次問(wèn)題)。so，使用鏈表可以將活躍節(jié)點(diǎn)移動(dòng)到鏈表的一端，淘汰時(shí)直接從另一端進(jìn)行刪除。

public class LruCache<K,V> {/** 這里簡(jiǎn)單點(diǎn)直接初始化了*/ 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; } /** 使用過(guò)就移動(dòng)到右側(cè) */ 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; /** 使用過(guò)就移動(dòng)到右側(cè) */ move2mru(temp); return; }/** 容量滿了清除左側(cè) */ 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主要用來(lái)快速索引key，鏈表用來(lái)完成LRU機(jī)制。當(dāng)然尚有許多不足，包括緩存移除remove，緩存ttl，線程安全等。

到此這篇關(guān)于淺談Java如何實(shí)現(xiàn)一個(gè)基于LRU時(shí)間復(fù)雜度為O(1)的緩存的文章就介紹到這了,更多相關(guān)Java基于LRU時(shí)間復(fù)雜度為O(1)的緩存內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！