Java數(shù)據(jù)結(jié)構(gòu)_LinkedHashMap 的工作原理

image.png

緩存算法的基本概念

源碼基于JDK1.7

緩存機(jī)制

  • 內(nèi)存緩存

  • 本地緩存

  • 網(wǎng)絡(luò)緩存

本節(jié)記錄的是內(nèi)存緩存

什么是內(nèi)存緩存？

將數(shù)據(jù)寫到了容器(list,map,set)等數(shù)據(jù)存儲(chǔ)單元中。

緩存淘汰機(jī)制

緩存是不能無(wú)限制緩存的，所以就有一套緩存淘汰機(jī)制

  • FIFO （First In, First Out）
  • LFU (Least Frequently Used)
  • LRU (Least Recently Used) 最近最少使用算法

LRU 的工作原理

  • 新數(shù)據(jù)插入到鏈表頭部
  • 當(dāng)緩存命中(即緩存數(shù)據(jù)被訪問(wèn))，數(shù)據(jù)要移到表頭
  • 當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄

鏈表表頭就表示最近訪問(wèn)的數(shù)據(jù)，鏈表尾表示即將被淘汰的數(shù)據(jù)

LinkedHashMap 是如何實(shí)現(xiàn) LruCache 算法的？

LinkedHashMap的使用

final LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<Integer, String>(0, 0.75f, true) {
    //3.當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄
    @Override
    protected boolean removeEldestEntry(Entry eldest) {
        if (size() > 5) {
            System.out.println("remove ：" + eldest.getKey());
            return true;
        }
        return false;
    }
};
//1.新數(shù)據(jù)插入到鏈表頭部
lruCache.put(1, "1");
lruCache.put(2, "2");
lruCache.put(3, "3");
lruCache.put(4, "4");
lruCache.put(5, "5");
lruCache.put(6, "6");
//2.緩存命中
//String s = lruCache.get(3);
Set<Map.Entry<Integer, String>> entries = lruCache.entrySet();
for (Map.Entry<Integer, String> entry : entries) {
    Integer key = entry.getKey();
    String value = entry.getValue();
    System.out.println("key:" + key + ",value = " + value);
}

-----打印結(jié)果----

remove ：1
key:2,value = 2
key:3,value = 3
key:4,value = 4
key:5,value = 5
key:6,value = 6

LinkedHashMap 的內(nèi)部實(shí)現(xiàn)原理

LinkedHashMap 是繼承至 HashMap ，它工作原理是是由 HashMap 的散列表和 LinkedHashMap 的雙鏈表組成。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
  • put(key，value)

因?yàn)?LinkedHashMap 沒(méi)有重寫 put 方法，因此會(huì)走 HashMap 的 put 方法，最終執(zhí)行 LinkedHashMap 的 createEntry 函數(shù)，將要插入地?cái)?shù)據(jù)添加到鏈表表頭。

HashMap 的實(shí)現(xiàn)

public V put(K key, V value) {
    //hashMap 存儲(chǔ)邏輯，找到 hash,key,value,i 等值
    addEntry(hash, key, value, i);
    return null;
}
//擴(kuò)容判斷
//createEntry將數(shù)據(jù)插入到hashmap的散列表中
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

LinkedHashMap 的實(shí)現(xiàn)

void addEntry(int hash, K key, V value, int bucketIndex) {
    super.addEntry(hash, key, value, bucketIndex);
    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    //3.當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄
    //在插入數(shù)據(jù)時(shí)回調(diào)給外層是否要移除該數(shù)據(jù)
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    //1.將要插入數(shù)據(jù)移到鏈表頭部
    e.addBefore(header);
    size++;
}

當(dāng)緩存命中(即緩存數(shù)據(jù)被訪問(wèn))，數(shù)據(jù)要移到表頭

//LinkedHashMap#get
public V get(Object key) {
    //從 hashmap 中獲取對(duì)應(yīng)的 Enrty
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    //2.緩存命中
    e.recordAccess(this);
    return e.value;
}
//LinkedHashMap$Enrty.recordAccess
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //如果是按照訪問(wèn)順序進(jìn)行存儲(chǔ)
    if (lm.accessOrder) {
        lm.modCount++;
        //先將該 Entry進(jìn)行移除
        remove();
        //將該 Entry 添加到表頭
        addBefore(lm.header);
    }
}

當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄

void addEntry(int hash, K key, V value, int bucketIndex) {
    super.addEntry(hash, key, value, bucketIndex);
    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

這里就需要開發(fā)者去定義什么時(shí)候，緩存已滿，這里官方文檔有一個(gè)栗子：

//重寫 LinkedHashMap 的這個(gè)方法，實(shí)現(xiàn) removeEldestEntry 的邏輯即可。
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

ImageLoader 的 LruCache 算法的實(shí)現(xiàn)

源碼地址：LruMemoryCache.java

LruMemoryCache的初始化

LruMemoryCache 內(nèi)部就是根據(jù) LinkedHashMap 來(lái)進(jìn)行 LruCache 算法的

private final LinkedHashMap<String, Bitmap> map;

private final int maxSize;
/** Size of this cache in bytes */
private int size;

/** @param maxSize Maximum sum of the sizes of the Bitmaps in this cache */
public LruMemoryCache(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    this.maxSize = maxSize;
  
    this.map = new LinkedHashMap<String, Bitmap>(0, 0.75f, true);
}

存儲(chǔ)數(shù)據(jù)

@Override
public final boolean put(String key, Bitmap value) {

    if (key == null || value == null) {

        throw new NullPointerException("key == null || value == null");
    }
    synchronized (this) {
    
    //計(jì)算要緩存圖片的大小
        size += sizeOf(key, value);
    
    //將圖片存儲(chǔ)到 LinkedHashMap 中
    //previous 不為 null 表示之前存在相同 key
    //previous 為 null 表示 key 是第一次存儲(chǔ)
        Bitmap previous = map.put(key, value);

        if (previous != null) {
        //把先前的bitmap的大小進(jìn)行移除
                size -= sizeOf(key, previous);
        }
    }
  //判斷是否要 lru 淘汰
    trimToSize(maxSize);

    return true;
}

取數(shù)據(jù)

緩存命中

@Override
public final Bitmap get(String key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }
    synchronized (this) {
    //通過(guò)上面分析的 LinkedHashMap 的 get 函數(shù)可以知道
    //它內(nèi)部將從散列表中查詢到數(shù)據(jù)Entry 從雙向鏈表移除，然后添加到雙向鏈表的表頭
        return map.get(key);
    }
}

移除數(shù)據(jù)

private void trimToSize(int maxSize) {
    while (true) {
        String key;
        Bitmap value;
        synchronized (this) {
            if (size < 0 || (map.isEmpty() && size != 0)) {
                throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
            }
            //緩存夠用
            if (size <= maxSize || map.isEmpty()) {
                break;
            }
    
      //緩存不夠用
            Map.Entry<String, Bitmap> toEvict = map.entrySet().iterator().next();
            if (toEvict == null) {
                break;
            }
            key = toEvict.getKey();
            value = toEvict.getValue();
      //從 linkedHashMap 中移除
            map.remove(key);
      //將數(shù)據(jù)的 size 更新
            size -= sizeOf(key, value);
        }
    }
}

本文是筆者學(xué)習(xí)之后的總結(jié)，方便日后查看學(xué)習(xí)，有任何不對(duì)的地方請(qǐng)指正。

記錄于 2019年6月3號(hào)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容