當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

JDK1.8源码分析：LinkedHashMap与LRU缓存设计思路

發(fā)布時(shí)間：2024/1/18 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了 JDK1.8源码分析：LinkedHashMap与LRU缓存设计思路小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

概述

LinkedHashMap繼承于HashMap，在HashMap的基礎(chǔ)上，新增了兩個(gè)特性：

支持以節(jié)點(diǎn)的插入順序來迭代該map內(nèi)的所有節(jié)點(diǎn)；

支持緩存設(shè)計(jì)中LRU的特性，即LinkedHashMap支持按訪問順序來排序節(jié)點(diǎn)，具體在內(nèi)部實(shí)現(xiàn)為如果開啟了這個(gè)特性，則每次通過get方法訪問了一個(gè)節(jié)點(diǎn)，則該節(jié)點(diǎn)會(huì)被移動(dòng)到內(nèi)部的雙向鏈表的末尾，故雙向鏈表的頭結(jié)點(diǎn)是最近最少訪問的節(jié)點(diǎn)，尾節(jié)點(diǎn)為剛剛訪問過的節(jié)點(diǎn)，中間節(jié)點(diǎn)依次類推。

以上兩個(gè)特性是互斥存在的，默認(rèn)是以節(jié)點(diǎn)插入順序來排序節(jié)點(diǎn)，可以通過設(shè)置構(gòu)造函數(shù)中的accessOrder為true來開啟按節(jié)點(diǎn)訪問順序排序。
/*** Constructs an empty <tt>LinkedHashMap</tt> instance with the* specified initial capacity, load factor and ordering mode.** @param initialCapacity the initial capacity* @param loadFactor the load factor* @param accessOrder the ordering mode - <tt>true</tt> for* access-order, <tt>false</tt> for insertion-order* @throws IllegalArgumentException if the initial capacity is negative* or the load factor is nonpositive*/ public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder; }
以上兩個(gè)特性都是基于在LinkedHashMap中額外維護(hù)了一個(gè)雙向鏈表來實(shí)現(xiàn)。
以上兩個(gè)特性都是在迭代器中體現(xiàn)，具體為entrySet方法，keySet方法，values方法，在for循環(huán)遍歷這些方法返回的集合。

數(shù)據(jù)結(jié)構(gòu)與核心字段

LinkedHashMap繼承于HashMap，節(jié)點(diǎn)數(shù)據(jù)也是存儲(chǔ)在HashMap的哈希表table數(shù)組中。
為了支持以上兩個(gè)特性，在LinkedHashMap內(nèi)部額外維護(hù)了一個(gè)雙向鏈表的數(shù)據(jù)結(jié)構(gòu)：對(duì)HashMap的節(jié)點(diǎn)Node進(jìn)行了拓展，定義了雙向鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)Entry，增加了before和after兩個(gè)指針，分別為指向前節(jié)點(diǎn)和后節(jié)點(diǎn)，從而實(shí)現(xiàn)雙向鏈表的特性。
如下為在LinkedHashMap內(nèi)部定義的雙向鏈表的鏈表節(jié)點(diǎn)Entry，雙向鏈表的頭結(jié)點(diǎn)指針head，雙向鏈表的尾節(jié)點(diǎn)指針tail：
// 雙向鏈表數(shù)據(jù)結(jié)構(gòu) /*** HashMap.Node subclass for normal LinkedHashMap entries.*/ static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);} }/*** 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;
注意LinkedHashMap在HashMap的哈希表table數(shù)組內(nèi)的鏈表的鏈表數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，使用的是這個(gè)拓展的Entry類；而對(duì)于紅黑樹節(jié)點(diǎn)，則還是使用HashMap中定義的。
由于雙向鏈表節(jié)點(diǎn)是LinkedHashMap額外的維護(hù)的結(jié)構(gòu)，所以在增刪改父類HashMap中的哈希表table數(shù)組中的數(shù)據(jù)節(jié)點(diǎn)時(shí)，需要回調(diào)LinkedHashMap中的對(duì)該雙向鏈表增刪改的方法來保持?jǐn)?shù)據(jù)同步。

accessOrder：訪問順序排序開關(guān)

在LinkedHashMap中定義了accessOrder字段來控制是否以訪問順序排序雙向鏈表的節(jié)點(diǎn)：默認(rèn)為false，不使用，使用雙向鏈表節(jié)點(diǎn)插入順序來排序。
/*** The iteration ordering method for this linked hash map: <tt>true</tt>* for access-order, <tt>false</tt> for insertion-order.** @serial*/ final boolean accessOrder;
accessOrder主要是在LinkedHashMap的get方法中使用，即在訪問某個(gè)key對(duì)應(yīng)的節(jié)點(diǎn)時(shí)，判斷是否需要將在雙向鏈表中對(duì)應(yīng)的節(jié)點(diǎn)移動(dòng)到雙向鏈表末尾，具體在以下分析。

核心方法

由于LinkedHashMap繼承于HashMap，在內(nèi)部也是使用HashMap的哈希表table數(shù)組來存儲(chǔ)數(shù)據(jù)，LinkedHashMap主要是覆蓋HashMap的相關(guān)方法或者實(shí)現(xiàn)HashMap的增刪改回調(diào)方法，來對(duì)自身的雙向鏈表進(jìn)行調(diào)整，或者是利用自身維護(hù)的雙向鏈表來對(duì)HashMap中的相關(guān)方法進(jìn)行重寫優(yōu)化。

覆蓋HashMap的方法

新增節(jié)點(diǎn)：newNode方法，覆蓋HashMap的新增節(jié)點(diǎn)方法，返回的是LinkedHashMap內(nèi)部定義的Entry節(jié)點(diǎn)，故在HashMap的哈希表table數(shù)組內(nèi)部的鏈表的鏈表節(jié)點(diǎn)類型為Entry了。同時(shí)調(diào)用linkNodeLast方法將該節(jié)點(diǎn)放到內(nèi)部的雙向鏈表的末尾。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p);return p; }// 將該節(jié)點(diǎn)放到雙向鏈表的末尾 // link at the end of list private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;} }
訪問節(jié)點(diǎn)：get方法，在內(nèi)部調(diào)用了HashMap的getNode方法來從HashMap的哈希表table數(shù)組查找該指定key對(duì)應(yīng)的節(jié)點(diǎn)。額外增加通過accessOrder的判斷來決定是否對(duì)自身的雙向鏈表節(jié)點(diǎn)進(jìn)行調(diào)整。
/*** Returns the value to which the specified key is mapped,* or {@code null} if this map contains no mapping for the key.** More formally, if this map contains a mapping from a key* {@code k} to a value {@code v} such that {@code (key==null ? k==null :* key.equals(k))}, then this method returns {@code v}; otherwise* it returns {@code null}. (There can be at most one such mapping.)** A return value of {@code null} does not necessarily* indicate that the map contains no mapping for the key; it's also* possible that the map explicitly maps the key to {@code null}.* The {@link #containsKey containsKey} operation may be used to* distinguish these two cases.*/ public V get(Object key) {Node<K,V> e;// getNode為在HashMap中定義的方法if ((e = getNode(hash(key), key)) == null)return null;// 判斷是否以訪問順序排序雙向鏈表節(jié)點(diǎn)if (accessOrder)afterNodeAccess(e);return e.value; }// 將當(dāng)前訪問的節(jié)點(diǎn)，調(diào)整到雙向鏈表的末尾，實(shí)現(xiàn)按訪問順序排序的功能 void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;} }
containsValue：判斷map中是否存在指定value的節(jié)點(diǎn)，重寫了hashMap的containsValue方法，利用雙向鏈表來查找。在HashMap中需要遍歷哈希表table數(shù)組，然后遍歷數(shù)組中每個(gè)元素對(duì)應(yīng)的鏈表，即從鏈表頭開始一個(gè)個(gè)比較。
/*** Returns <tt>true</tt> if this map maps one or more keys to the* specified value.** @param value value whose presence in this map is to be tested* @return <tt>true</tt> if this map maps one or more keys to the* specified value*/ public boolean containsValue(Object value) {for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {V v = e.value;if (v == value || (value != null && value.equals(v)))return true;}return false; }
清空數(shù)據(jù)方法：clear，主要是調(diào)用父類HashMap的clear來完成對(duì)哈希表table數(shù)組內(nèi)部所有數(shù)據(jù)的清空，在LinkedHashMap中需要將雙向鏈表的頭指針和尾指針均置為null。
/*** {@inheritDoc}*/ public void clear() {super.clear();head = tail = null; }

HashMap的增刪改的回調(diào)方法

以上方法由于HashMap沒有提供回調(diào)方法來進(jìn)行拓展，故需要在LinkedHashMap中顯式重寫來加入對(duì)雙向鏈表的操作。在HashMap中對(duì)于增刪改節(jié)點(diǎn)對(duì)應(yīng)了回調(diào)方法，故可以在LinkedHashMap中實(shí)現(xiàn)這些回調(diào)方法即可。

如下為在HashMap中聲明的回調(diào)方法：
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }
afterNodeAccess：節(jié)點(diǎn)訪問回調(diào)，主要在get方法中調(diào)用，可以參見以上get方法的分析。
afterNodeInsertion：節(jié)點(diǎn)插入回調(diào)，主要是在HashMap的putVal方法實(shí)現(xiàn)中最后調(diào)用，即在往HashMap的哈希表table數(shù)組插入數(shù)據(jù)相關(guān)查找完成后，最后調(diào)用afterNodeInsertion。LinkedHashMap的afterNodeInsertion回調(diào)實(shí)現(xiàn)如下：
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;// 判斷是否刪除最近最少訪問的節(jié)點(diǎn)if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;// removeNode內(nèi)部會(huì)調(diào)用afterNodeRemoval方法來調(diào)整該雙向鏈表removeNode(hash(key), key, null, false, true);} }
主要用于在基于LinkedHashMap來實(shí)現(xiàn)緩存時(shí)，實(shí)現(xiàn)緩存的LRU特性使用。
afterNodeRemoval：在HashMap刪除某個(gè)節(jié)點(diǎn)時(shí)，回調(diào)afterNodeRemoval方法。LinkedHashMap的實(shí)現(xiàn)為在自身維護(hù)的雙向鏈表中刪除對(duì)應(yīng)的鏈表節(jié)點(diǎn)：
// 在HashMap中的鏈表節(jié)點(diǎn)e刪除后，同步調(diào)整該雙向鏈表，刪除該節(jié)點(diǎn) void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b; }

迭代器

在LinkedHashMap中，迭代器相關(guān)的操作是基于自身的雙向鏈表，而不是父類HashMap的哈希表table數(shù)組來實(shí)現(xiàn)的，故迭代順序是基于雙向鏈表的順序?qū)崿F(xiàn)的，即以插入順序（從前到后：最先插入->最后插入）排序或者訪問順序排序（從前到后：最近最少訪問 -> 剛剛訪問）。
LinkedHashMap的方法包括：entrySet方法，keySet方法，values方法
LinkedHashMap的迭代器定義：主要在構(gòu)造函數(shù)中將next初始化為雙向鏈表的頭結(jié)點(diǎn)head。
// Iteratorsabstract class LinkedHashIterator {LinkedHashMap.Entry<K,V> next;LinkedHashMap.Entry<K,V> current;int expectedModCount;LinkedHashIterator() {// 初始化為雙向鏈表頭結(jié)點(diǎn)headnext = head;expectedModCount = modCount;current = null;}public final boolean hasNext() {return next != null;}final LinkedHashMap.Entry<K,V> nextNode() {LinkedHashMap.Entry<K,V> e = next;// 并發(fā)修改異常if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();current = e;next = e.after;return e;}public final void remove() {Node<K,V> p = current;if (p == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();current = null;K key = p.key;removeNode(hash(key), key, null, false, false);expectedModCount = modCount;} }

LRU緩存

由于LinkedHashMap支持按訪問順序排序雙向鏈表的特性，故可以基于LinkedHashMap來實(shí)現(xiàn)一個(gè)LRU緩存，具體為拓展LinkedHashMap，在緩存類中，重寫removeEldestEntry方法來定義刪除最近最少訪問的節(jié)點(diǎn)的條件。
/*** 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.** 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() > MAX_ENTRIES;* }* </pre>** 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 is permitted for this method to modify* the map directly, but if it does so, it must 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.** 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.*/ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false; }
由以上分析可知，removeEldestEntry主要是在HashMap的新增節(jié)點(diǎn)的回調(diào)afterNodeInsertion中調(diào)用。在LinkedHashMap的afterNodeInsertion方法實(shí)現(xiàn)如下：
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;// 判斷是否刪除最近最少訪問的節(jié)點(diǎn)if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;// removeNode內(nèi)部會(huì)調(diào)用afterNodeRemoval方法來調(diào)整該雙向鏈表removeNode(hash(key), key, null, false, true);} }
在afterNodeInsertion中，head頭結(jié)點(diǎn)就是最近最少訪問的節(jié)點(diǎn)，故在該緩存類中，需要設(shè)置accessOrder為true來開啟按訪問順序排序；
在afterNodeInsertion中會(huì)調(diào)用HashMap的removeNode方法來刪除雙向鏈表頭結(jié)點(diǎn)head對(duì)應(yīng)的哈希表table的鏈表的鏈表節(jié)點(diǎn)，在HashMap的removeNode會(huì)回調(diào)LinkedHashMap的afterNodeRemoval來刪除LinkedHashMap內(nèi)部的雙向鏈表的鏈表節(jié)點(diǎn)；
故在繼承了LinkedHashMap的緩存類只需實(shí)現(xiàn)removeEldestEntry方法即可。
removeEldestEntry的方法實(shí)現(xiàn)例子：
public class LRUCache extends LinkedHashMap {private static final int MAX_ENTRIES = 100;public LRUCache(int initialCapacity, float loadFactor) {// 第三個(gè)參數(shù)為accessOrdersuper(initialCapacity, loadFactor, true);}protected boolean removeEldestEntry(Map.Entry eldest) {return size() > MAX_ENTRIES;} }

總結(jié)

以上是生活随笔為你收集整理的JDK1.8源码分析：LinkedHashMap与LRU缓存设计思路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：数据连接相关类简介
下一篇：离散数学——最大、小元超详细结合例题理