LRU 實現緩存

LRU:Least Recently used 最近最少使用

?

1.使用LinkedHashMap實現 inheritance實現方式 繼承map類 可以使用Collections.synchronizedMap方式實現線程安全的操作

public class LruCache<K,V> extends LinkedHashMap<K,V> {private final int MAX_CACHE_SIZE;public LruCache(int cacheSize) {super((int)Math.ceil(cacheSize/0.75)+1,0.75f,true );MAX_CACHE_SIZE = cacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry eldest){return size()> MAX_CACHE_SIZE;}@Overridepublic String toString(){StringBuilder sb= new StringBuilder();for(Map.Entry<K,V> entry : entrySet()){sb.append(String.format("%s:%s",entry.getKey(),entry.getValue()));}return sb.toString();}
}

2、LinkedHashMap 使用delegation方式實現

沒有map接口?

public class LruByDelegation<K,V> {private final int MAX_CACHE_SIZE;private final float DEFAULT_LOAD_FACTOR = 0.75f;LinkedHashMap<K,V> map;public LruByDelegation(int cacheSize) {this.MAX_CACHE_SIZE = cacheSize;int capacity = (int) (Math.ceil(MAX_CACHE_SIZE/DEFAULT_LOAD_FACTOR)+1);map= new LinkedHashMap(capacity,DEFAULT_LOAD_FACTOR,true){@Overrideprotected boolean removeEldestEntry(Map.Entry eldest){return size()>MAX_CACHE_SIZE;}};}public synchronized void put(K key,V value){map.put(key,value);}public synchronized V get(K key){return map.get(key);}public synchronized void remove(K key){map.remove(key);}public synchronized Set<Map.Entry<K,V>> getAll(){return map.entrySet();}public synchronized int size(){return map.size();}public synchronized void clear(){map.clear();}@Overridepublic String toString(){StringBuilder sb= new StringBuilder();for(Map.Entry entry : map.entrySet()){sb.append(String.format("%s:%s",entry.getKey(),entry.getValue()));}return sb.toString();}}

2 Cache鏈表+HashMap實現? ?Entry自己定義? 總結一下就是各種pre 和 next指針的變換

public class LruCache01<K,V> {private final int MAX_CACHE_SIZE;private Entry first;private Entry last;private HashMap<K, Entry<K,V>> hashMap;public LruCache01(int MAX_CACHE_SIZE) {this.MAX_CACHE_SIZE = MAX_CACHE_SIZE;hashMap=new HashMap<>();}public void put(K key, V value){Entry entry = getEntry(key);if(entry==null){if(hashMap.size()>=MAX_CACHE_SIZE){hashMap.remove(last.key);//removeLast
                removeLast();}entry=new Entry();entry.key=key;}entry.value=value;moveToFirst(entry);hashMap.put(key,entry);}public V get(K  key){Entry entry  = getEntry(key);if(entry==null)return null;moveToFirst(entry);return (V) entry.value;}public void remove(K key){Entry entry = getEntry(key);if(entry!=null){if(entry.pre!=null)entry.pre.next=entry.next;if(entry.next!=null)entry.next.pre=entry.pre;if(entry==first)first=entry.next;if(entry==last)last=entry.pre;}hashMap.remove(key);}public void moveToFirst(Entry entry){if(entry==first)return;if(entry.pre!=null)entry.pre.next=entry.next;if(entry.next!=null)entry.next.pre=entry.pre;if(entry==last)last=last.pre;if(first==null || last==null){first=last=entry;return;}entry.next=first;first.pre=entry;first=entry;entry.pre=null;}public void removeLast(){if(last!=null){last=last.pre;if(last==null)first=null;elselast.next=null;}}public Entry<K,V> getEntry(K key){return hashMap.get(key);}@Overridepublic String toString(){StringBuilder sb= new StringBuilder();Entry entry = first;while(entry!=null){sb.append(String.format("%s:%s",entry.key,entry.value));entry=entry.next;}return sb.toString();}
}
class Entry<K,V>{public Entry pre;public Entry next;public K key;public V value;
}

LinkedHashMap的FIFO實現

只需要重新removeEldestEntry方法可以實現FIFO緩存

final int cacheSize=5;
LinkedHashMap<Integer,String> lru = new LinkedHashMap<Integer,String>(){@Override
protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest){
return size()>cacheSize;}  
}

?