|
作者：勞夫子 （Java知音獲權(quán)轉(zhuǎn)載）
這篇文章我們開(kāi)始分析LinkedHashMap的源碼，LinkedHashMap繼承了HashMap，也就是說(shuō)LinkedHashMap是在HashMap的基礎(chǔ)上擴(kuò)展而來(lái)的。因此在看LinkedHashMap源碼之前，讀者有必要先去了解HashMap的源碼，可以查看我上一篇文章的介紹《集合系列—HashMap源碼分析》。
只要深入理解了HashMap的實(shí)現(xiàn)原理，回過(guò)頭來(lái)再去看LinkedHashMap，HashSet和LinkedHashSet的源碼那都是非常簡(jiǎn)單的。因此，讀者們好好耐下性子來(lái)研究研究HashMap源碼吧，這可是買(mǎi)一送三的好生意啊。
在前面分析HashMap源碼時(shí)，我采用以問(wèn)題為導(dǎo)向?qū)υ创a進(jìn)行分析，這樣使自己不會(huì)像無(wú)頭蒼蠅一樣亂分析一通，讀者也能夠針對(duì)問(wèn)題更加深入的理解。本篇我決定還是采用這樣的方式對(duì)LinkedHashMap進(jìn)行分析。
1. LinkedHashMap內(nèi)部采用了什么樣的結(jié)構(gòu)？ 可以看到，由于LinkedHashMap是繼承自HashMap的，所以LinkedHashMap內(nèi)部也還是一個(gè)哈希表，只不過(guò)LinkedHashMap重新寫(xiě)了一個(gè)Entry，在原來(lái)HashMap的Entry上添加了兩個(gè)成員變量，分別是前繼結(jié)點(diǎn)引用和后繼結(jié)點(diǎn)引用。
這樣就將所有的結(jié)點(diǎn)鏈接在了一起，構(gòu)成了一個(gè)雙向鏈表，在獲取元素的時(shí)候就直接遍歷這個(gè)雙向鏈表就行了。我們看看LinkedHashMap實(shí)現(xiàn)的Entry是什么樣子的。 private static class EntryK,V> extends HashMap.EntryK,V> {
//當(dāng)前結(jié)點(diǎn)在雙向鏈表中的前繼結(jié)點(diǎn)的引用
Entry before;
//當(dāng)前結(jié)點(diǎn)在雙向鏈表中的后繼結(jié)點(diǎn)的引用
Entry after;
Entry(int hash, K key, V value, HashMap.Entry next) {
super(hash, key, value, next);
}
//從雙向鏈表中移除該結(jié)點(diǎn)
private void remove() {
before.after = after;
after.before = before;
}
//將當(dāng)前結(jié)點(diǎn)插入到雙向鏈表中一個(gè)已存在的結(jié)點(diǎn)前面
private void addBefore(Entry existingEntry) {
//當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的引用指向給定結(jié)點(diǎn)
after = existingEntry;
//當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的引用指向給定結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
before = existingEntry.before;
//給定結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的引用指向當(dāng)前結(jié)點(diǎn)
before.after = this;
//給定結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的引用指向當(dāng)前結(jié)點(diǎn)
after.before = this;
}
//按訪問(wèn)順序排序時(shí), 記錄每次獲取的操作
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
//如果是按訪問(wèn)順序排序
if (lm.accessOrder) {
lm.modCount++;
//先將自己從雙向鏈表中移除
remove();
//將自己放到雙向鏈表尾部
addBefore(lm.header);
}
}
void recordRemoval(HashMap m) {
remove();
}
}
2. LinkedHashMap是怎樣實(shí)現(xiàn)按插入順序排序的？ //父類(lèi)put方法中會(huì)調(diào)用的該方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//調(diào)用父類(lèi)的addEntry方法
super.addEntry(hash, key, value, bucketIndex);
//下面操作是方便LRU緩存的實(shí)現(xiàn), 如果緩存容量不足, 就移除最老的元素
Entry eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
//父類(lèi)的addEntry方法中會(huì)調(diào)用該方法
void createEntry(int hash, K key, V value, int bucketIndex) {
//先獲取HashMap的Entry
HashMap.Entry old = table[bucketIndex];
//包裝成LinkedHashMap自身的Entry
Entry e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//將當(dāng)前結(jié)點(diǎn)插入到雙向鏈表的尾部
e.addBefore(header);
size++;
}
LinkedHashMap重寫(xiě)了它的父類(lèi)HashMap的addEntry和createEntry方法。當(dāng)要插入一個(gè)鍵值對(duì)的時(shí)候，首先會(huì)調(diào)用它的父類(lèi)HashMap的put方法。在put方法中會(huì)去檢查一下哈希表中是不是存在了對(duì)應(yīng)的key，如果存在了就直接替換它的value就行了，如果不存在就調(diào)用addEntry方法去新建一個(gè)Entry。
注意，這時(shí)候就調(diào)用到了LinkedHashMap自己的addEntry方法。我們看到上面的代碼，這個(gè)addEntry方法除了回調(diào)父類(lèi)的addEntry方法之外還會(huì)調(diào)用removeEldestEntry去移除最老的元素，這步操作主要是為了實(shí)現(xiàn)LRU算法，下面會(huì)講到。
我們看到LinkedHashMap還重寫(xiě)了createEntry方法，當(dāng)要新建一個(gè)Entry的時(shí)候最終會(huì)調(diào)用這個(gè)方法，createEntry方法在每次將Entry放入到哈希表之后，就會(huì)調(diào)用addBefore方法將當(dāng)前結(jié)點(diǎn)插入到雙向鏈表的尾部。這樣雙向鏈表就記錄了每次插入的結(jié)點(diǎn)的順序，獲取元素的時(shí)候只要遍歷這個(gè)雙向鏈表就行了，下圖演示了每次調(diào)用addBefore的操作。由于是雙向鏈表，所以將當(dāng)前結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之前其實(shí)就是將當(dāng)前結(jié)點(diǎn)插入到雙向鏈表的尾部。 3. 怎樣利用LinkedHashMap實(shí)現(xiàn)LRU緩存？ 我們知道緩存的實(shí)現(xiàn)依賴(lài)于計(jì)算機(jī)的內(nèi)存，而內(nèi)存資源是相當(dāng)有限的，不可能無(wú)限制的存放元素，所以我們需要在容量不夠的時(shí)候適當(dāng)?shù)膭h除一些元素，那么到底刪除哪個(gè)元素好呢？
LRU算法的思想是，如果一個(gè)數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高。所以我們可以刪除那些不經(jīng)常被訪問(wèn)的數(shù)據(jù)。接下來(lái)我們看看LinkedHashMap內(nèi)部是怎樣實(shí)現(xiàn)LRU機(jī)制的。 public class LinkedHashMapK,V> extends HashMapK,V> implements MapK,V> {
//雙向鏈表頭結(jié)點(diǎn)
private transient Entry header;
//是否按訪問(wèn)順序排序
private final boolean accessOrder;
...
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//根據(jù)key獲取value值
public V get(Object key) {
//調(diào)用父類(lèi)方法獲取key對(duì)應(yīng)的Entry
Entry e = (Entry)getEntry(key);
if (e == null) {
return null;
}
//如果是按訪問(wèn)順序排序的話(huà), 會(huì)將每次使用后的結(jié)點(diǎn)放到雙向鏈表的尾部
e.recordAccess(this);
return e.value;
}
private static class EntryK,V> extends HashMap.EntryK,V> {
...
//將當(dāng)前結(jié)點(diǎn)插入到雙向鏈表中一個(gè)已存在的結(jié)點(diǎn)前面
private void addBefore(Entry existingEntry) {
//當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的引用指向給定結(jié)點(diǎn)
after = existingEntry;
//當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的引用指向給定結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
before = existingEntry.before;
//給定結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的引用指向當(dāng)前結(jié)點(diǎn)
before.after = this;
//給定結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的引用指向當(dāng)前結(jié)點(diǎn)
after.before = this;
}
//按訪問(wèn)順序排序時(shí), 記錄每次獲取的操作
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
//如果是按訪問(wèn)順序排序
if (lm.accessOrder) {
lm.modCount++;
//先將自己從雙向鏈表中移除
remove();
//將自己放到雙向鏈表尾部
addBefore(lm.header);
}
}
...
}
//父類(lèi)put方法中會(huì)調(diào)用的該方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//調(diào)用父類(lèi)的addEntry方法
super.addEntry(hash, key, value, bucketIndex);
//下面操作是方便LRU緩存的實(shí)現(xiàn), 如果緩存容量不足, 就移除最老的元素
Entry eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
//是否刪除最老的元素, 該方法設(shè)計(jì)成要被子類(lèi)覆蓋
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
}
為了更加直觀，上面貼出的代碼中我將一些無(wú)關(guān)的代碼省略了，我們可以看到LinkedHashMap有一個(gè)成員變量accessOrder，該成員變量記錄了是否需要按訪問(wèn)順序排序，它提供了一個(gè)構(gòu)造器可以自己指定accessOrder的值。
每次調(diào)用get方法獲取元素式都會(huì)調(diào)用e.recordAccess(this)，該方法會(huì)將當(dāng)前結(jié)點(diǎn)移到雙向鏈表的尾部?，F(xiàn)在我們知道了如果accessOrder為true那么每次get元素后都會(huì)把這個(gè)元素挪到雙向鏈表的尾部。這一步的目的是區(qū)別出最常使用的元素和不常使用的元素，經(jīng)常使用的元素放到尾部，不常使用的元素放到頭部。
我們?cè)倩氐缴厦娴拇a中看到每次調(diào)用addEntry方法時(shí)都會(huì)判斷是否需要?jiǎng)h除最老的元素。判斷的邏輯是removeEldestEntry實(shí)現(xiàn)的，該方法被設(shè)計(jì)成由子類(lèi)進(jìn)行覆蓋并重寫(xiě)里面的邏輯。
注意，由于最近被訪問(wèn)的結(jié)點(diǎn)都被挪動(dòng)到雙向鏈表的尾部，所以這里是從雙向鏈表頭部取出最老的結(jié)點(diǎn)進(jìn)行刪除。下面例子實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的LRU緩存。 public class LRUMap extends LinkedHashMap {
private int capacity;
LRUMap(int capacity) {
//調(diào)用父類(lèi)構(gòu)造器, 設(shè)置為按訪問(wèn)順序排序
super(capacity, 1f, true);
this.capacity = capacity;
}
@Override
public boolean removeEldestEntry(Map.Entry eldest) {
//當(dāng)鍵值對(duì)大于等于哈希表容量時(shí)
return this.size() >= capacity;
}
public static void main(String[] args) {
LRUMap map = new LRUMap(4);
map.put(1, 'a');
map.put(2, 'b');
map.put(3, 'c');
System.out.println('原始集合:' + map);
String s = map.get(2);
System.out.println('獲取元素:' + map);
map.put(4, 'd');
System.out.println('插入之后:' + map);
}
}
結(jié)果如下： 注：以上全部分析基于JDK1.7，不同版本間會(huì)有差異，讀者需要注意
|
