Java - 快速手撕 LRU 算法

importjava.util.LinkedHashMap;
importjava.util.Map;
/*** @author Lux Sun* @date 2021/4/27*/publicclassLruCache<K, V>extendsLinkedHashMap<K, V> {
privateintcapacity;
/*** 构造函数* @param capacity: 初始容量* loadFactor: 加载因子, 一般是 0.75f* accessOrder: false 基于插入顺序; true 基于访问顺序(get一个元素后, 这个元素被加到最后, 使用了LRU最近最少被使用的调度算法)*/publicLruCache(intcapacity) {
super(16, 0.75f, true);
this.capacity=capacity;
    }
/*** LinkedHashMap 重写该函数, 详情见源码* @param eldest*/@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<K, V>eldest) {
returnsize() >this.capacity;
    }
publicstaticvoidmain(String[] args) {
LruCache<String, Object>cache=newLruCache<>(2);
cache.put("1", 1);
cache.put("2", 2);
cache.put("3", 3);
cache.entrySet().forEach(System.out::println);
    }
}

/*** Returns <tt>true</tt> if this map should remove its eldest entry.* This method is invoked by <tt>put</tt> and <tt>putAll</tt> after* inserting a new entry into the map.  It provides the implementor* with the opportunity to remove the eldest entry each time a new one* is added.  This is useful if the map represents a cache: it allows* the map to reduce memory consumption by deleting stale entries.** <p>Sample use: this override will allow the map to grow up to 100* entries and then delete the eldest entry each time a new entry is* added, maintaining a steady state of 100 entries.* <pre>*     private static final int MAX_ENTRIES = 100;**     protected boolean removeEldestEntry(Map.Entry eldest) {*        return size() &gt; MAX_ENTRIES;*     }* </pre>** <p>This method typically does not modify the map in any way,* instead allowing the map to modify itself as directed by its* return value.  It <i>is</i> permitted for this method to modify* the map directly, but if it does so, it <i>must</i> return* <tt>false</tt> (indicating that the map should not attempt any* further modification).  The effects of returning <tt>true</tt>* after modifying the map from within this method are unspecified.** <p>This implementation merely returns <tt>false</tt> (so that this* map acts like a normal map - the eldest element is never removed).** @param    eldest The least recently inserted entry in the map, or if*           this is an access-ordered map, the least recently accessed*           entry.  This is the entry that will be removed it this*           method returns <tt>true</tt>.  If the map was empty prior*           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting*           in this invocation, this will be the entry that was just*           inserted; in other words, if the map contains a single*           entry, the eldest entry is also the newest.* @return   <tt>true</tt> if the eldest entry should be removed*           from the map; <tt>false</tt> if it should be retained.*/protectedbooleanremoveEldestEntry(Map.Entry<K,V>eldest) {
returnfalse;
}
voidafterNodeInsertion(booleanevict) { // possibly remove eldestLinkedHashMap.Entry<K,V>first;
if (evict&& (first=head) !=null&&removeEldestEntry(first)) {
Kkey=first.key;
removeNode(hash(key), key, null, false, true);
    }
}