小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

圖解LinkedHashMap原理

 liang1234_ 2020-02-16

1 前言

LinkedHashMap繼承于HashMap，如果對(duì)HashMap原理還不清楚的同學(xué)，請(qǐng)先看上一篇：圖解HashMap原理

2 LinkedHashMap使用與實(shí)現(xiàn)

先來(lái)一張LinkedHashMap的結(jié)構(gòu)圖，不要虛，看完文章再來(lái)看這個(gè)圖，就秒懂了，先混個(gè)面熟：


LinkedHashMap結(jié)構(gòu).png

2.1 應(yīng)用場(chǎng)景

HashMap是無(wú)序的，當(dāng)我們希望有順序地去存儲(chǔ)key-value時(shí)，就需要使用LinkedHashMap了。

Map<String, String> hashMap = new HashMap<String, String>(); hashMap.put('name1', 'josan1'); hashMap.put('name2', 'josan2'); hashMap.put('name3', 'josan3'); Set<Entry<String, String>> set = hashMap.entrySet(); Iterator<Entry<String, String>> iterator = set.iterator(); while(iterator.hasNext()) { Entry entry = iterator.next(); String key = (String) entry.getKey(); String value = (String) entry.getValue(); System.out.println('key:' key ',value:' value); }
image.png

我們是按照xxx1、xxx2、xxx3的順序插入的，但是輸出結(jié)果并不是按照順序的。

同樣的數(shù)據(jù)，我們?cè)僭囋嘗inkedHashMap

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put('name1', 'josan1');
        linkedHashMap.put('name2', 'josan2');
        linkedHashMap.put('name3', 'josan3');
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println('key:'   key   ',value:'   value);
        }
image.png

結(jié)果可知，LinkedHashMap是有序的，且默認(rèn)為插入順序。

2.2 簡(jiǎn)單使用

跟HashMap一樣，它也是提供了key-value的存儲(chǔ)方式，并提供了put和get方法來(lái)進(jìn)行數(shù)據(jù)存取。

LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(); linkedHashMap.put('name', 'josan'); String name = linkedHashMap.get('name');

2.3 定義

LinkedHashMap繼承了HashMap，所以它們有很多相似的地方。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

2.4 構(gòu)造方法

image.png

LinkedHashMap提供了多個(gè)構(gòu)造方法，我們先看空參的構(gòu)造方法。

public LinkedHashMap() { // 調(diào)用HashMap的構(gòu)造方法，其實(shí)就是初始化Entry[] table super(); // 這里是指是否基于訪問(wèn)排序，默認(rèn)為false accessOrder = false; }

首先使用super調(diào)用了父類HashMap的構(gòu)造方法，其實(shí)就是根據(jù)初始容量、負(fù)載因子去初始化Entry[] table，詳細(xì)的看上一篇HashMap解析。

然后把a(bǔ)ccessOrder設(shè)置為false，這就跟存儲(chǔ)的順序有關(guān)了，LinkedHashMap存儲(chǔ)數(shù)據(jù)是有序的，而且分為兩種：插入順序和訪問(wèn)順序。

這里accessOrder設(shè)置為false，表示不是訪問(wèn)順序而是插入順序存儲(chǔ)的，這也是默認(rèn)值，表示LinkedHashMap中存儲(chǔ)的順序是按照調(diào)用put方法插入的順序進(jìn)行排序的。LinkedHashMap也提供了可以設(shè)置accessOrder的構(gòu)造方法，我們來(lái)看看這種模式下，它的順序有什么特點(diǎn)？

                // 第三個(gè)參數(shù)用于指定accessOrder值
        Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
        linkedHashMap.put('name1', 'josan1');
        linkedHashMap.put('name2', 'josan2');
        linkedHashMap.put('name3', 'josan3');
        System.out.println('開(kāi)始時(shí)順序：');
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println('key:'   key   ',value:'   value);
        }
        System.out.println('通過(guò)get方法，導(dǎo)致key為name1對(duì)應(yīng)的Entry到表尾');
        linkedHashMap.get('name1');
        Set<Entry<String, String>> set2 = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator2 = set2.iterator();
        while(iterator2.hasNext()) {
            Entry entry = iterator2.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println('key:'   key   ',value:'   value);
        }
image.png

因?yàn)檎{(diào)用了get('name1')導(dǎo)致了name1對(duì)應(yīng)的Entry移動(dòng)到了最后，這里只要知道LinkedHashMap有插入順序和訪問(wèn)順序兩種就可以，后面會(huì)詳細(xì)講原理。

還記得，上一篇HashMap解析中提到，在HashMap的構(gòu)造函數(shù)中，調(diào)用了init方法，而在HashMap中init方法是空實(shí)現(xiàn)，但LinkedHashMap重寫(xiě)了該方法，所以在LinkedHashMap的構(gòu)造方法里，調(diào)用了自身的init方法，init的重寫(xiě)實(shí)現(xiàn)如下：

/** * Called by superclass constructors and pseudoconstructors (clone, * readObject) before any entries are inserted into the map. Initializes * the chain. */ @Override void init() { // 創(chuàng)建了一個(gè)hash=-1，key、value、next都為null的Entry header = new Entry<>(-1, null, null, null); // 讓創(chuàng)建的Entry的before和after都指向自身，注意after不是之前提到的next // 其實(shí)就是創(chuàng)建了一個(gè)只有頭部節(jié)點(diǎn)的雙向鏈表 header.before = header.after = header; }

這好像跟我們上一篇HashMap提到的Entry有些不一樣，HashMap中靜態(tài)內(nèi)部類Entry是這樣定義的：

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

沒(méi)有before和after屬性?。≡瓉?lái)，LinkedHashMap有自己的靜態(tài)內(nèi)部類Entry，它繼承了HashMap.Entry，定義如下:

/** * LinkedHashMap entry. */ private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); }

所以LinkedHashMap構(gòu)造函數(shù)，主要就是調(diào)用HashMap構(gòu)造函數(shù)初始化了一個(gè)Entry[] table，然后調(diào)用自身的init初始化了一個(gè)只有頭結(jié)點(diǎn)的雙向鏈表。完成了如下操作：


LinkedHashMap構(gòu)造函數(shù).png

2.5 put方法

LinkedHashMap沒(méi)有重寫(xiě)put方法，所以還是調(diào)用HashMap得到put方法，如下：

    public V put(K key, V value) {
        // 對(duì)key為null的處理
        if (key == null)
            return putForNullKey(value);
        // 計(jì)算hash
        int hash = hash(key);
        // 得到在table中的index
        int i = indexFor(hash, table.length);
        // 遍歷table[index]，是否key已經(jīng)存在，存在則替換，并返回舊值
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        
        modCount  ;
        // 如果key之前在table中不存在，則調(diào)用addEntry，LinkedHashMap重寫(xiě)了該方法
        addEntry(hash, key, value, i);
        return null;
    }

我們看看LinkedHashMap的addEntry方法：

void addEntry(int hash, K key, V value, int bucketIndex) { // 調(diào)用父類的addEntry，增加一個(gè)Entry到HashMap中 super.addEntry(hash, key, value, bucketIndex); // removeEldestEntry方法默認(rèn)返回false，不用考慮 Entry<K,V> eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } }

這里調(diào)用了父類HashMap的addEntry方法，如下：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 擴(kuò)容相關(guān)
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        // LinkedHashMap進(jìn)行了重寫(xiě)
        createEntry(hash, key, value, bucketIndex);
    }

前面是擴(kuò)容相關(guān)的代碼，在上一篇HashMap解析中已經(jīng)講過(guò)了。這里主要看createEntry方法，LinkedHashMap進(jìn)行了重寫(xiě)。

void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; // e就是新創(chuàng)建了Entry，會(huì)加入到table[bucketIndex]的表頭 Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; // 把新創(chuàng)建的Entry，加入到雙向鏈表中 e.addBefore(header); size ; }

我們來(lái)看看LinkedHashMap.Entry的addBefore方法：

        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

從這里就可以看出，當(dāng)put元素時(shí)，不但要把它加入到HashMap中去，還要加入到雙向鏈表中，所以可以看出LinkedHashMap就是HashMap 雙向鏈表，下面用圖來(lái)表示逐步往LinkedHashMap中添加數(shù)據(jù)的過(guò)程，紅色部分是雙向鏈表，黑色部分是HashMap結(jié)構(gòu)，header是一個(gè)Entry類型的雙向鏈表表頭，本身不存儲(chǔ)數(shù)據(jù)。

首先是只加入一個(gè)元素Entry1，假設(shè)index為0：


LinkedHashMap結(jié)構(gòu)一個(gè)元素.png

當(dāng)再加入一個(gè)元素Entry2，假設(shè)index為15：


LinkedHashMap結(jié)構(gòu)兩個(gè)元素.png

當(dāng)再加入一個(gè)元素Entry3, 假設(shè)index也是0：


LinkedHashMap結(jié)構(gòu)三個(gè)元素.png

以上，就是LinkedHashMap的put的所有過(guò)程了，總體來(lái)看，跟HashMap的put類似，只不過(guò)多了把新增的Entry加入到雙向列表中。

2.6 擴(kuò)容

在HashMap的put方法中，如果發(fā)現(xiàn)前元素個(gè)數(shù)超過(guò)了擴(kuò)容閥值時(shí)，會(huì)調(diào)用resize方法，如下：

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; // 把舊table的數(shù)據(jù)遷移到新table transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1); }

LinkedHashMap重寫(xiě)了transfer方法，數(shù)據(jù)的遷移，它的實(shí)現(xiàn)如下：

    void transfer(HashMap.Entry[] newTable, boolean rehash) {
        // 擴(kuò)容后的容量是之前的2倍
        int newCapacity = newTable.length;
        // 遍歷雙向鏈表，把所有雙向鏈表中的Entry，重新就算hash，并加入到新的table中
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            if (rehash)
                e.hash = (e.key == null) ? 0 : hash(e.key);
            int index = indexFor(e.hash, newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
        }
    }

可以看出，LinkedHashMap擴(kuò)容時(shí)，數(shù)據(jù)的再散列和HashMap是不一樣的。

HashMap是先遍歷舊table，再遍歷舊table中每個(gè)元素的單向鏈表，取得Entry以后，重新計(jì)算hash值，然后存放到新table的對(duì)應(yīng)位置。

LinkedHashMap是遍歷的雙向鏈表，取得每一個(gè)Entry，然后重新計(jì)算hash值，然后存放到新table的對(duì)應(yīng)位置。

從遍歷的效率來(lái)說(shuō)，遍歷雙向鏈表的效率要高于遍歷table，因?yàn)楸闅v雙向鏈表是N次（N為元素個(gè)數(shù)）；而遍歷table是N table的空余個(gè)數(shù)（N為元素個(gè)數(shù)）。

2.7 雙向鏈表的重排序

前面分析的，主要是當(dāng)前LinkedHashMap中不存在當(dāng)前key時(shí)，新增Entry的情況。當(dāng)key如果已經(jīng)存在時(shí)，則進(jìn)行更新Entry的value。就是HashMap的put方法中的如下代碼：

for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; // 重排序 e.recordAccess(this); return oldValue; } }

主要看e.recordAccess(this)，這個(gè)方法跟訪問(wèn)順序有關(guān)，而HashMap是無(wú)序的，所以在HashMap.Entry的recordAccess方法是空實(shí)現(xiàn)，但是LinkedHashMap是有序的,LinkedHashMap.Entry對(duì)recordAccess方法進(jìn)行了重寫(xiě)。

        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            // 如果LinkedHashMap的accessOrder為true，則進(jìn)行重排序
            // 比如前面提到LruCache中使用到的LinkedHashMap的accessOrder屬性就為true
            if (lm.accessOrder) {
                lm.modCount  ;
                // 把更新的Entry從雙向鏈表中移除
                remove();
                // 再把更新的Entry加入到雙向鏈表的表尾
                addBefore(lm.header);
            }
        }

在LinkedHashMap中，只有accessOrder為true，即是訪問(wèn)順序模式，才會(huì)put時(shí)對(duì)更新的Entry進(jìn)行重新排序，而如果是插入順序模式時(shí)，不會(huì)重新排序，這里的排序跟在HashMap中存儲(chǔ)沒(méi)有關(guān)系，只是指在雙向鏈表中的順序。

舉個(gè)栗子：開(kāi)始時(shí)，HashMap中有Entry1、Entry2、Entry3，并設(shè)置LinkedHashMap為訪問(wèn)順序，則更新Entry1時(shí)，會(huì)先把Entry1從雙向鏈表中刪除，然后再把Entry1加入到雙向鏈表的表尾，而Entry1在HashMap結(jié)構(gòu)中的存儲(chǔ)位置沒(méi)有變化，對(duì)比圖如下所示：


LinkedHashMap重排序.png

2.8 get方法

LinkedHashMap有對(duì)get方法進(jìn)行了重寫(xiě)，如下：

public V get(Object key) { // 調(diào)用genEntry得到Entry Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; // 如果LinkedHashMap是訪問(wèn)順序的，則get時(shí)，也需要重新排序 e.recordAccess(this); return e.value; }

先是調(diào)用了getEntry方法，通過(guò)key得到Entry，而LinkedHashMap并沒(méi)有重寫(xiě)getEntry方法，所以調(diào)用的是HashMap的getEntry方法，在上一篇文章中我們分析過(guò)HashMap的getEntry方法：首先通過(guò)key算出hash值，然后根據(jù)hash值算出在table中存儲(chǔ)的index，然后遍歷table[index]的單向鏈表去對(duì)比key，如果找到了就返回Entry。

后面調(diào)用了LinkedHashMap.Entry的recordAccess方法，上面分析過(guò)put過(guò)程中這個(gè)方法，其實(shí)就是在訪問(wèn)順序的LinkedHashMap進(jìn)行了get操作以后，重新排序，把get的Entry移動(dòng)到雙向鏈表的表尾。

2.9 遍歷方式取數(shù)據(jù)

我們先來(lái)看看HashMap使用遍歷方式取數(shù)據(jù)的過(guò)程：


HashMap遍歷.png

很明顯，這樣取出來(lái)的Entry順序肯定跟插入順序不同了，既然LinkedHashMap是有序的，那么它是怎么實(shí)現(xiàn)的呢？
先看看LinkedHashMap取遍歷方式獲取數(shù)據(jù)的代碼：

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put('name1', 'josan1');
        linkedHashMap.put('name2', 'josan2');
        linkedHashMap.put('name3', 'josan3');
                // LinkedHashMap沒(méi)有重寫(xiě)該方法，調(diào)用的HashMap中的entrySet方法
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println('key:'   key   ',value:'   value);
        }

LinkedHashMap沒(méi)有重寫(xiě)entrySet方法，我們先來(lái)看HashMap中的entrySet，如下：

public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); } // 無(wú)關(guān)代碼 ...... }

可以看到，HashMap的entrySet方法，其實(shí)就是返回了一個(gè)EntrySet對(duì)象。

我們得到EntrySet會(huì)調(diào)用它的iterator方法去得到迭代器Iterator，從上面的代碼也可以看到，iterator方法中直接調(diào)用了newEntryIterator方法并返回，而LinkedHashMap重寫(xiě)了該方法

    Iterator<Map.Entry<K,V>> newEntryIterator() { 
        return new EntryIterator();
    }

這里直接返回了EntryIterator對(duì)象，這個(gè)和上一篇HashMap中的newEntryIterator方法中一模一樣，都是返回了EntryIterator對(duì)象，其實(shí)他們返回的是各自的內(nèi)部類。我們來(lái)看看LinkedHashMap中EntryIterator的定義：

private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } }

該類是繼承LinkedHashIterator，并重寫(xiě)了next方法；而HashMap中是繼承HashIterator。
我們?cè)賮?lái)看看LinkedHashIterator的定義：

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        // 默認(rèn)下一個(gè)返回的Entry為雙向鏈表表頭的下一個(gè)元素
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        public boolean hasNext() {
            return nextEntry != header;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
        // 不相關(guān)代碼
        ......
    }

我們先不看整個(gè)類的實(shí)現(xiàn)，只要知道在LinkedHashMap中，Iterator<Entry<String, String>> iterator = set.iterator()，這段代碼會(huì)返回一個(gè)繼承LinkedHashIterator的Iterator，它有著跟HashIterator不一樣的遍歷規(guī)則。

接著，我們會(huì)用while(iterator.hasNext())去循環(huán)判斷是否有下一個(gè)元素，LinkedHashMap中的EntryIterator沒(méi)有重寫(xiě)該方法，所以還是調(diào)用LinkedHashIterator中的hasNext方法，如下：

public boolean hasNext() { // 下一個(gè)應(yīng)該返回的Entry是否就是雙向鏈表的頭結(jié)點(diǎn) // 有兩種情況：1.LinkedHashMap中沒(méi)有元素；2.遍歷完雙向鏈表回到頭部 return nextEntry != header; }

nextEntry表示下一個(gè)應(yīng)該返回的Entry，默認(rèn)值是header.after，即雙向鏈表表頭的下一個(gè)元素。而上面介紹到，LinkedHashMap在初始化時(shí)，會(huì)調(diào)用init方法去初始化一個(gè)before和after都指向自身的Entry，但是put過(guò)程會(huì)把新增加的Entry加入到雙向鏈表的表尾，所以只要LinkedHashMap中有元素，第一次調(diào)用hasNext肯定不會(huì)為false。

然后我們會(huì)調(diào)用next方法去取出Entry，LinkedHashMap中的EntryIterator重寫(xiě)了該方法，如下：

 public Map.Entry<K,V> next() { 
    return nextEntry(); 
}

而它自身又沒(méi)有重寫(xiě)nextEntry方法，所以還是調(diào)用的LinkedHashIterator中的nextEntry方法：

Entry<K,V> nextEntry() { // 保存應(yīng)該返回的Entry Entry<K,V> e = lastReturned = nextEntry; //把當(dāng)前應(yīng)該返回的Entry的after作為下一個(gè)應(yīng)該返回的Entry nextEntry = e.after; // 返回當(dāng)前應(yīng)該返回的Entry return e; }

這里其實(shí)遍歷的是雙向鏈表，所以不會(huì)存在HashMap中需要尋找下一條單向鏈表的情況，從頭結(jié)點(diǎn)Entry header的下一個(gè)節(jié)點(diǎn)開(kāi)始，只要把當(dāng)前返回的Entry的after作為下一個(gè)應(yīng)該返回的節(jié)點(diǎn)即可。直到到達(dá)雙向鏈表的尾部時(shí)，after為雙向鏈表的表頭節(jié)點(diǎn)Entry header，這時(shí)候hasNext就會(huì)返回false，表示沒(méi)有下一個(gè)元素了。LinkedHashMap的遍歷取值如下圖所示：


LinkedHashMap遍歷.png

易知，遍歷出來(lái)的結(jié)果為Entry1、Entry2...Entry6。
可得，LinkedHashMap是有序的，且是通過(guò)雙向鏈表來(lái)保證順序的。

2.10 remove方法

LinkedHashMap沒(méi)有提供remove方法，所以調(diào)用的是HashMap的remove方法，實(shí)現(xiàn)如下：

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount  ;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                // LinkedHashMap.Entry重寫(xiě)了該方法
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

在上一篇HashMap中就分析了remove過(guò)程，其實(shí)就是斷開(kāi)其他對(duì)象對(duì)自己的引用。比如被刪除Entry是在單向鏈表的表頭，則讓它的next放到表頭，這樣它就沒(méi)有被引用了；如果不是在表頭，它是被別的Entry的next引用著，這時(shí)候就讓上一個(gè)Entry的next指向它自己的next，這樣，它也就沒(méi)被引用了。

在HashMap.Entry中recordRemoval方法是空實(shí)現(xiàn)，但是LinkedHashMap.Entry對(duì)其進(jìn)行了重寫(xiě)，如下：

void recordRemoval(HashMap<K,V> m) { remove(); } private void remove() { before.after = after; after.before = before; }

易知，這是要把雙向鏈表中的Entry刪除，也就是要斷開(kāi)當(dāng)前要被刪除的Entry被其他對(duì)象通過(guò)after和before的方式引用。

所以，LinkedHashMap的remove操作。首先把它從table中刪除，即斷開(kāi)table或者其他對(duì)象通過(guò)next對(duì)其引用，然后也要把它從雙向鏈表中刪除，斷開(kāi)其他對(duì)應(yīng)通過(guò)after和before對(duì)其引用。

3 HashMap與LinkedHashMap的結(jié)構(gòu)對(duì)比

再來(lái)看看HashMap和LinkedHashMap的結(jié)構(gòu)圖，是不是秒懂了。LinkedHashMap其實(shí)就是可以看成HashMap的基礎(chǔ)上，多了一個(gè)雙向鏈表來(lái)維持順序。


HashMap結(jié)構(gòu).png
LinkedHashMap結(jié)構(gòu).png

4 LinkedHashMap在Android中的應(yīng)用

在Android中使用圖片時(shí)，一般會(huì)用LruCacha做圖片的內(nèi)存緩存，它里面就是使用LinkedHashMap來(lái)實(shí)現(xiàn)存儲(chǔ)的。

public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException('maxSize <= 0');
        }
        this.maxSize = maxSize;
        // 注意第三個(gè)參數(shù)，是accessOrder，這里為true，后面會(huì)講到
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

前面提到了，accessOrder為true，表示LinkedHashMap為訪問(wèn)順序，當(dāng)對(duì)已存在LinkedHashMap中的Entry進(jìn)行g(shù)et和put操作時(shí)，會(huì)把Entry移動(dòng)到雙向鏈表的表尾（其實(shí)是先刪除，再插入）。
我們拿LruCache的put方法舉例：

public final V put(K key, V value) { if (key == null || value == null) { throw new NullPointerException('key == null || value == null'); } V previous; // 對(duì)map進(jìn)行操作之前，先進(jìn)行同步操作 synchronized (this) { putCount ; size = safeSizeOf(key, value); previous = map.put(key, value); if (previous != null) { size -= safeSizeOf(key, previous); } } if (previous != null) { entryRemoved(false, key, previous, value); } // 整理內(nèi)存，看是否需要移除LinkedHashMap中的元素 trimToSize(maxSize); return previous; }

之前提到了，HashMap是線程不安全的，LinkedHashMap同樣是線程不安全的。所以在對(duì)調(diào)用LinkedHashMap的put方法時(shí)，先使用synchronized 進(jìn)行了同步操作。

我們最關(guān)心的是倒數(shù)第一行代碼，其中maxSize為我們給LruCache設(shè)置的最大緩存大小。我們看看該方法：

    /**
     * Remove the eldest entries until the total of remaining entries is at or
     * below the requested size.
     *
     * @param maxSize the maximum size of the cache before returning. May be -1
     *            to evict even 0-sized elements.
     */
    public void trimToSize(int maxSize) {
        // while死循環(huán)，直到滿足當(dāng)前緩存大小小于或等于最大可緩存大小
        while (true) {
            K key;
            V value;
            // 線程不安全，需要同步
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                              '.sizeOf() is reporting inconsistent results!');
                }
                // 如果當(dāng)前緩存的大小，已經(jīng)小于等于最大可緩存大小，則直接返回
                // 不需要再移除LinkedHashMap中的數(shù)據(jù)
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }
                // 得到的就是雙向鏈表表頭header的下一個(gè)Entry
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                // 移除當(dāng)前取出的Entry
                map.remove(key);
                // 從新計(jì)算當(dāng)前的緩存大小
                size -= safeSizeOf(key, value);
                evictionCount  ;
            }

            entryRemoved(true, key, value, null);
        }
    }

從注釋上就可以看出，該方法就是不斷移除LinkedHashMap中雙向鏈表表頭的元素，直到當(dāng)前緩存大小小于或等于最大可緩存的大小。

由前面的重排序我們知道，對(duì)LinkedHashMap的put和get操作，都會(huì)讓被操作的Entry移動(dòng)到雙向鏈表的表尾，而移除是從map.entrySet().iterator().next()開(kāi)始的，也就是雙向鏈表的表頭的header的after開(kāi)始的，這也就符合了LRU算法的需求。

下圖表示了LinkedHashMap中刪除、添加、get/put已存在的Entry操作。
紅色表示初始狀態(tài)
紫色表示緩存圖片大小超過(guò)了最大可緩存大小時(shí)，才能夠表頭移除Entry1
藍(lán)色表示對(duì)已存在的Entry3進(jìn)行了get/put操作，把它移動(dòng)到雙向鏈表表尾
綠色表示新增一個(gè)Entry7，插入到雙向鏈表的表尾（暫時(shí)不考慮在HashMap中的位置）


LinkedHashMap之Lru.png

5 總結(jié)

  1. LinkedHashMap是繼承于HashMap，是基于HashMap和雙向鏈表來(lái)實(shí)現(xiàn)的。
  2. HashMap無(wú)序；LinkedHashMap有序，可分為插入順序和訪問(wèn)順序兩種。如果是訪問(wèn)順序，那put和get操作已存在的Entry時(shí)，都會(huì)把Entry移動(dòng)到雙向鏈表的表尾(其實(shí)是先刪除再插入)。
  3. LinkedHashMap存取數(shù)據(jù)，還是跟HashMap一樣使用的Entry[]的方式，雙向鏈表只是為了保證順序。
  4. LinkedHashMap是線程不安全的。

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多