Java数据结构_LinkedHashMap 的工作原理

2019-06-03  本文已影响0人  未见哥哥
image.png

缓存算法的基本概念

源码基于JDK1.7

缓存机制

本节记录的是内存缓存

什么是内存缓存？

将数据写到了容器(list,map,set)等数据存储单元中。

缓存淘汰机制

缓存是不能无限制缓存的，所以就有一套缓存淘汰机制

LRU 的工作原理

链表表头就表示最近访问的数据，链表尾表示即将被淘汰的数据

LinkedHashMap 是如何实现 LruCache 算法的？

LinkedHashMap的使用

final LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<Integer, String>(0, 0.75f, true) {
    //3.当链表满的时候，将链表尾部的数据丢弃
    @Override
    protected boolean removeEldestEntry(Entry eldest) {
        if (size() > 5) {
            System.out.println("remove ：" + eldest.getKey());
            return true;
        }
        return false;
    }
};
//1.新数据插入到链表头部
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);
}

-----打印结果----

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

LinkedHashMap 的内部实现原理

LinkedHashMap 是继承至 HashMap ，它工作原理是是由 HashMap 的散列表和 LinkedHashMap 的双链表组成。

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

因为 LinkedHashMap 没有重写 put 方法，因此会走 HashMap 的 put 方法，最终执行 LinkedHashMap 的 createEntry 函数，将要插入地数据添加到链表表头。

HashMap 的实现

public V put(K key, V value) {
    //hashMap 存储逻辑，找到 hash,key,value,i 等值
    addEntry(hash, key, value, i);
    return null;
}
//扩容判断
//createEntry将数据插入到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 的实现

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.当链表满的时候，将链表尾部的数据丢弃
    //在插入数据时回调给外层是否要移除该数据
    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.将要插入数据移到链表头部
    e.addBefore(header);
    size++;
}

当缓存命中(即缓存数据被访问)，数据要移到表头

//LinkedHashMap#get
public V get(Object key) {
    //从 hashmap 中获取对应的 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;
    //如果是按照访问顺序进行存储
    if (lm.accessOrder) {
        lm.modCount++;
        //先将该 Entry进行移除
        remove();
        //将该 Entry 添加到表头
        addBefore(lm.header);
    }
}

当链表满的时候，将链表尾部的数据丢弃

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;
}

这里就需要开发者去定义什么时候，缓存已满，这里官方文档有一个栗子：

//重写 LinkedHashMap 的这个方法，实现 removeEldestEntry 的逻辑即可。
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

ImageLoader 的 LruCache 算法的实现

源码地址：LruMemoryCache.java

LruMemoryCache的初始化

LruMemoryCache 内部就是根据 LinkedHashMap 来进行 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);
}

存储数据

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

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

        throw new NullPointerException("key == null || value == null");
    }
    synchronized (this) {
    
    //计算要缓存图片的大小
        size += sizeOf(key, value);
    
    //将图片存储到 LinkedHashMap 中
    //previous 不为 null 表示之前存在相同 key
    //previous 为 null 表示 key 是第一次存储
        Bitmap previous = map.put(key, value);

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

    return true;
}

取数据

缓存命中

@Override
public final Bitmap get(String key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }
    synchronized (this) {
    //通过上面分析的 LinkedHashMap 的 get 函数可以知道
    //它内部将从散列表中查询到数据Entry 从双向链表移除，然后添加到双向链表的表头
        return map.get(key);
    }
}

移除数据

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);
      //将数据的 size 更新
            size -= sizeOf(key, value);
        }
    }
}

本文是笔者学习之后的总结，方便日后查看学习，有任何不对的地方请指正。

记录于 2019年6月3号

上一篇下一篇

猜你喜欢

热点阅读