LRU算法及Apache LRUMap源碼實例解析
1. 什麼是LRU
LRU(least recently used) : 最近最少使用
LRU就是一種經典的算法,在容器中,對元素定義一個最後使用時間,當新的元素寫入的時候,如果容器已滿,則淘汰最近最少使用的元素,把新的元素寫入。
1.1 自定義實現LRU的要求
比如redis,如何自己實現簡易版的redis緩存。
那麼我們需要一種數據結構,支持set和get操作。
1) get操作時間復雜度O(1);
2)需要支持RLU算法,空間不足時,需要將使用最少的元素移除,為新元素讓空間;
3)時間失效remove(這個先不談,比較麻煩)。
1.2 Apache LRUMap示例
1.2.1 pom依賴
<dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-collections4</artifactId> <version>4.2</version> </dependency>
1.2.2 demo
LRUMap<String, String> map = new LRUMap<>(3); map.put("1", "1"); map.put("2", "2"); map.put("3", "3"); map.get("2"); System.out.println("---------------------------------"); map.forEach((k,v)-> System.out.println(k+"\t"+v) ); map.put("4", "4"); map.put("5", "5"); System.out.println("---------------------------------"); map.forEach((k,v)-> System.out.println(k+"\t"+v) ); map.put("6", "6"); System.out.println("---------------------------------"); map.forEach((k,v)-> System.out.println(k+"\t"+v) );
結果如下:
———————————
1 1
3 3
2 2
———————————
2 2
4 4
5 5
———————————
4 4
5 5
6 6
可以看出在get(“2”),2的位置挪後,然後移除的順序就延後。
容量不足時,總是移除,使用最少的,時間最遠的。
2. 源碼解析
2.1 設計
public class LRUMap<K, V> extends AbstractLinkedMap<K, V> implements BoundedMap<K, V>, Serializable, Cloneable {
進一步查看AbstractLinkedMap,AbstractHashedMap
public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> {
public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> {
本質是自定義AbstractMap
我們看看HashMap LinkedHashMap
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
可以看出AbstractMap,AbstractHashedMap,LRUMap的本質其實也是HashMap。
2.2 數據結構
protected static final int DEFAULT_MAX_SIZE = 100; public LRUMap() { this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false); }
可以看出默認初始化容量100,最大容量也是100.
進一步跟蹤
public LRUMap(final int maxSize, final float loadFactor, final boolean scanUntilRemovable) { this(maxSize, maxSize, loadFactor, scanUntilRemovable); } /** * Constructs a new, empty map with the specified max / initial capacity and load factor. * * @param maxSize the maximum size of the map * @param initialSize the initial size of the map * @param loadFactor the load factor * @param scanUntilRemovable scan until a removeable entry is found, default false * @throws IllegalArgumentException if the maximum size is less than one * @throws IllegalArgumentException if the initial size is negative or larger than the maximum size * @throws IllegalArgumentException if the load factor is less than zero * @since 4.1 */ public LRUMap(final int maxSize, final int initialSize, final float loadFactor, final boolean scanUntilRemovable) { super(initialSize, loadFactor); if (maxSize < 1) { throw new IllegalArgumentException("LRUMap max size must be greater than 0"); } if (initialSize > maxSize) { throw new IllegalArgumentException("LRUMap initial size must not be greather than max size"); } this.maxSize = maxSize; this.scanUntilRemovable = scanUntilRemovable; }
跟蹤super(initialSize, loadFactor);
public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> { protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) { super(initialCapacity, loadFactor); } //又super,再上一層追蹤 public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> { //定義一些基本初始化數據 /** The default capacity to use */ protected static final int DEFAULT_CAPACITY = 16; /** The default threshold to use */ protected static final int DEFAULT_THRESHOLD = 12; /** The default load factor to use */ protected static final float DEFAULT_LOAD_FACTOR = 0.75f; /** The maximum capacity allowed */ protected static final int MAXIMUM_CAPACITY = 1 << 30; /** Load factor, normally 0.75 */ transient float loadFactor; /** The size of the map */ transient int size; /** Map entries */ transient HashEntry<K, V>[] data; /** Size at which to rehash */ transient int threshold; /** Modification count for iterators */ transient int modCount; /** Entry set */ transient EntrySet<K, V> entrySet; /** Key set */ transient KeySet<K> keySet; /** Values */ transient Values<V> values; protected AbstractHashedMap(int initialCapacity, final float loadFactor) { super(); if (initialCapacity < 0) { throw new IllegalArgumentException("Initial capacity must be a non negative number"); } if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) { throw new IllegalArgumentException("Load factor must be greater than 0"); } this.loadFactor = loadFactor; initialCapacity = calculateNewCapacity(initialCapacity); this.threshold = calculateThreshold(initialCapacity, loadFactor); this.data = new HashEntry[initialCapacity]; init(); } /** * Initialise subclasses during construction, cloning or deserialization. */ protected void init() { //沒有任何邏輯,僅用於子類構造 }
DEFAULT_LOAD_FACTOR = 0.75f; 負載因子0.75
可以看出LRUMap的本質,HashEntry數組。
上面的init方法沒有實現邏輯,但是在他的子類中AbstractLinkedMap有相關的定義。
/** Header in the linked list */ transient LinkEntry<K, V> header; /** * Creates an entry to store the data. * <p> * This implementation creates a new LinkEntry instance. * * @param next the next entry in sequence * @param hashCode the hash code to use * @param key the key to store * @param value the value to store * @return the newly created entry */ @Override protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) { return new LinkEntry<>(next, hashCode, convertKey(key), value); } protected static class LinkEntry<K, V> extends HashEntry<K, V> { /** The entry before this one in the order */ protected LinkEntry<K, V> before; /** The entry after this one in the order */ protected LinkEntry<K, V> after; /** * Constructs a new entry. * * @param next the next entry in the hash bucket sequence * @param hashCode the hash code * @param key the key * @param value the value */ protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) { super(next, hashCode, key, value); } } /** * Initialise this subclass during construction. * <p> * NOTE: As from v3.2 this method calls * {@link #createEntry(HashEntry, int, Object, Object)} to create * the map entry object. */ @Override protected void init() { header = createEntry(null, -1, null, null); header.before = header.after = header; }
這個很關鍵。可以看出LRUMap是持有LinkEntry header,的雙鏈表結構,初始header為null,前後節點都是自身。將HashEntry轉成LinkEntry。
解析HashEntry
transient HashEntry<K, V>[] data; //構造初始化 this.data = new HashEntry[initialCapacity];
再跟蹤
protected static class HashEntry<K, V> implements Map.Entry<K, V>, KeyValue<K, V> { /** The next entry in the hash chain */ protected HashEntry<K, V> next; /** The hash code of the key */ protected int hashCode; /** The key */ protected Object key; /** The value */ protected Object value;
key,value,next單鏈表。
public int hashCode() { return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()); }
hashCode方法可以看出是key的hash與value的hash按位^運算。
在此我們看透LRU的本質瞭,數組+單鏈表。同時是持有頭結點的雙鏈表結構(怎麼看就是LinkedHashMap的結構,隻是有尾節點)。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { /** * The head (eldest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> head; /** * The tail (youngest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> tail;
那麼LRUMap是如何實現LRU算法的?
2.3 方法解析put get remove
2.3.1 get方法
public V get(final Object key) { return get(key, true); } public V get(final Object key, final boolean updateToMRU) { final LinkEntry<K, V> entry = getEntry(key); if (entry == null) { return null; } if (updateToMRU) { moveToMRU(entry); } return entry.getValue(); } //父類方法獲取值entry protected HashEntry<K, V> getEntry(Object key) { key = convertKey(key); final int hashCode = hash(key); HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)]; // no local for hash index while (entry != null) { if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) { return entry; } entry = entry.next; } return null; }
下面看不一樣的moveToMRU(entry);
/** * Moves an entry to the MRU position at the end of the list. * <p> * This implementation moves the updated entry to the end of the list. * * @param entry the entry to update */ protected void moveToMRU(final LinkEntry<K, V> entry) { if (entry.after != header) { modCount++; // remove if(entry.before == null) { throw new IllegalStateException("Entry.before is null." + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to [email protected] as a bug."); } entry.before.after = entry.after; entry.after.before = entry.before; // add first entry.after = header; entry.before = header.before; header.before.after = entry; header.before = entry; } else if (entry == header) { throw new IllegalStateException("Can't move header to MRU" + " (please report this to [email protected])"); } }
看出LRU的一個本質,每次get方法撥動指針,將get的元素移動到header的前一個位置。
2.3.2 remove方法
remove方法使用的父類的方法
/** * Removes the specified mapping from this map. * * @param key the mapping to remove * @return the value mapped to the removed key, null if key not in map */ @Override public V remove(Object key) { key = convertKey(key); final int hashCode = hash(key); final int index = hashIndex(hashCode, data.length); HashEntry<K, V> entry = data[index]; HashEntry<K, V> previous = null; while (entry != null) { if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) { final V oldValue = entry.getValue(); removeMapping(entry, index, previous); return oldValue; } previous = entry; entry = entry.next; } return null; } /** * Removes a mapping from the map. * <p> * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>. * It also handles changes to <code>modCount</code> and <code>size</code>. * Subclasses could override to fully control removals from the map. * * @param entry the entry to remove * @param hashIndex the index into the data structure * @param previous the previous entry in the chain */ protected void removeMapping(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) { modCount++; removeEntry(entry, hashIndex, previous); size--; destroyEntry(entry); } protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) { if (previous == null) { data[hashIndex] = entry.next; } else { previous.next = entry.next; } } protected void destroyEntry(final HashEntry<K, V> entry) { entry.next = null; entry.key = null; entry.value = null; }
這裡並沒有移除header雙鏈表的數據。
2.3.3 put方法
/** * Puts a key-value mapping into this map. * * @param key the key to add * @param value the value to add * @return the value previously mapped to this key, null if none */ @Override public V put(final K key, final V value) { final Object convertedKey = convertKey(key); final int hashCode = hash(convertedKey); final int index = hashIndex(hashCode, data.length); HashEntry<K, V> entry = data[index]; //僅在元素存在才循環,更新updateEntry,header前一個位置 while (entry != null) { if (entry.hashCode == hashCode && isEqualKey(convertedKey, entry.key)) { final V oldValue = entry.getValue(); updateEntry(entry, value); return oldValue; } entry = entry.next; } addMapping(index, hashCode, key, value); return null; }
updateEntry(entry, value);
/** * Updates an existing key-value mapping. * <p> * This implementation moves the updated entry to the end of the list * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}. * * @param entry the entry to update * @param newValue the new value to store */ @Override protected void updateEntry(final HashEntry<K, V> entry, final V newValue) { moveToMRU((LinkEntry<K, V>) entry); // handles modCount entry.setValue(newValue); }
moveToMRU((LinkEntry<K, V>) entry); // handles modCount
上面get方法有講,更新瞭鏈表的指針,新添加的元素在雙鏈表的header前一個位置,僅在元素存在的時候,while循環才生效。
那麼新增的元素呢?
下面看重點 addMapping(index, hashCode, key, value); 這句代碼定義瞭,容量滿瞭的處理策略。
/** * Adds a new key-value mapping into this map. * <p> * This implementation checks the LRU size and determines whether to * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}. * <p> * From Commons Collections 3.1 this method uses {@link #isFull()} rather * than accessing <code>size</code> and <code>maxSize</code> directly. * It also handles the scanUntilRemovable functionality. * * @param hashIndex the index into the data array to store at * @param hashCode the hash code of the key to add * @param key the key to add * @param value the value to add */ @Override protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) { //容量是否已滿 if (isFull()) { LinkEntry<K, V> reuse = header.after; boolean removeLRUEntry = false; //默認是false if (scanUntilRemovable) { //這裡不知道幹啥,難道是以後擴展? while (reuse != header && reuse != null) { //removeLRU一定返回true,很奇怪,估計以後擴展用 if (removeLRU(reuse)) { removeLRUEntry = true; break; } reuse = reuse.after; } if (reuse == null) { throw new IllegalStateException( "Entry.after=null, header.after" + header.after + " header.before" + header.before + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to [email protected] as a bug."); } } else { //一定返回true removeLRUEntry = removeLRU(reuse); } if (removeLRUEntry) { if (reuse == null) { throw new IllegalStateException( "reuse=null, header.after=" + header.after + " header.before" + header.before + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to [email protected] as a bug."); } reuseMapping(reuse, hashIndex, hashCode, key, value); } else { super.addMapping(hashIndex, hashCode, key, value); } } else { super.addMapping(hashIndex, hashCode, key, value); } } protected boolean removeLRU(final LinkEntry<K, V> entry) { return true; }
先判斷容量
public boolean isFull() { return size >= maxSize; }
未滿就直接添加
super.addMapping(hashIndex, hashCode, key, value);
protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) { modCount++; final HashEntry<K, V> entry = createEntry(data[hashIndex], hashCode, key, value); addEntry(entry, hashIndex); size++; checkCapacity(); }
//這裡調用瞭AbstractLinkedMap的方法
addEntry(entry, hashIndex);
/** * Adds an entry into this map, maintaining insertion order. * <p> * This implementation adds the entry to the data storage table and * to the end of the linked list. * * @param entry the entry to add * @param hashIndex the index into the data array to store at */ @Override protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) { final LinkEntry<K, V> link = (LinkEntry<K, V>) entry; link.after = header; link.before = header.before; header.before.after = link; header.before = link; data[hashIndex] = link; }
放在header的前一個位置,最早的元素鏈接到header。
雙向環回鏈表。
如果容量滿瞭,執行LRU算法 reuseMapping(reuse, hashIndex, hashCode, key, value);
/** * Reuses an entry by removing it and moving it to a new place in the map. * <p> * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}. * * @param entry the entry to reuse * @param hashIndex the index into the data array to store at * @param hashCode the hash code of the key to add * @param key the key to add * @param value the value to add */ protected void reuseMapping(final LinkEntry<K, V> entry, final int hashIndex, final int hashCode, final K key, final V value) { // find the entry before the entry specified in the hash table // remember that the parameters (except the first) refer to the new entry, // not the old one try { //要幹掉的元素下標 final int removeIndex = hashIndex(entry.hashCode, data.length); final HashEntry<K, V>[] tmp = data; // may protect against some sync issues HashEntry<K, V> loop = tmp[removeIndex]; HashEntry<K, V> previous = null; //避免已經被刪除 while (loop != entry && loop != null) { previous = loop; loop = loop.next; } //如果被其他線程刪除,拋異常 if (loop == null) { throw new IllegalStateException( "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to [email protected] as a bug."); } // reuse the entry modCount++; //雙鏈表移除舊元素,AbstractHashedMap移除舊元素 removeEntry(entry, removeIndex, previous); //復用移除的對象,減少創建對象和GC;增加AbstractHashedMap單鏈表next指向 reuseEntry(entry, hashIndex, hashCode, key, value); //復用的元素加AbstractLinkedMap雙鏈表和AbstractHashedMap單鏈表 addEntry(entry, hashIndex); } catch (final NullPointerException ex) { throw new IllegalStateException( "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to [email protected] as a bug."); } }
/** * Removes an entry from the map and the linked list. * <p> * This implementation removes the entry from the linked list chain, then * calls the superclass implementation. * * @param entry the entry to remove * @param hashIndex the index into the data structure * @param previous the previous entry in the chain */ @Override protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) { final LinkEntry<K, V> link = (LinkEntry<K, V>) entry; link.before.after = link.after; link.after.before = link.before; link.after = null; link.before = null; super.removeEntry(entry, hashIndex, previous); } /** * Removes an entry from the chain stored in a particular index. * <p> * This implementation removes the entry from the data storage table. * The size is not updated. * Subclasses could override to handle changes to the map. * * @param entry the entry to remove * @param hashIndex the index into the data structure * @param previous the previous entry in the chain */ protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) { if (previous == null) { data[hashIndex] = entry.next; } else { previous.next = entry.next; } } /** * Reuses an existing key-value mapping, storing completely new data. * <p> * This implementation sets all the data fields on the entry. * Subclasses could populate additional entry fields. * * @param entry the entry to update, not null * @param hashIndex the index in the data array * @param hashCode the hash code of the key to add * @param key the key to add * @param value the value to add */ protected void reuseEntry(final HashEntry<K, V> entry, final int hashIndex, final int hashCode, final K key, final V value) { entry.next = data[hashIndex]; entry.hashCode = hashCode; entry.key = key; entry.value = value; } /** * Adds an entry into this map, maintaining insertion order. * <p> * This implementation adds the entry to the data storage table and * to the end of the linked list. * * @param entry the entry to add * @param hashIndex the index into the data array to store at */ @Override protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) { final LinkEntry<K, V> link = (LinkEntry<K, V>) entry; link.after = header; link.before = header.before; header.before.after = link; header.before = link; data[hashIndex] = link; }
3. 總結
LRU的本質瞭,數組+單鏈表。同時是持有頭結點的環回雙鏈表結構
LRU最新使用的元素放在雙鏈表的header的前一個位置,如果,新增元素容量已滿就會移除header的後一個元素。
到此這篇關於LRU算法及Apache LRUMap源碼實例解析的文章就介紹到這瞭,更多相關LRU算法及Apache LRUMap源碼內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- 一文徹底搞定Java哈希表和哈希沖突
- Java數據結構之散列表詳解
- Java Map.entry案例詳解
- HashMap原理及put方法與get方法的調用過程
- ConcurrentHashMap是如何保證線程安全