美文网首页
LinkedHashMap和LruCache

LinkedHashMap和LruCache

作者: 蓝灰_q | 来源:发表于2017-12-11 11:00 被阅读116次

    LinkedHashMap是LruCache的基础,可以认为,LinkedHashMap是不限容量的Lru,Lru是限制了容量的LinkedHashMap。

    LinkedHashMap

    LinkedHashMap扩展自HashMap,而且数据存储对象改为扩展自HashMapEntry的LinkedHashMapEntry,主要是增加了before和after,实现双向链表。
    LinkedHashMap持有一个LinkedHashMapEntry类型的header,作为链表的表头。

    所以LinkedHashMap既有HashMap的数组+链表的二维存储结构,又有链表的前后关系的查找结构。
    所以,清空数据集合时,既要调用父类HashMap的数据清空,又要调用自身链表的前后关系清空(把header的before和after全都指向header自己)。

    LinkedHashMap自带部分LRU功能,构造函数:

        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }
    

    其中,第三个参数就代表是否开启LRU,如果为true,在get时,会挪到header前面,注意,header是不变的

            void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                if (lm.accessOrder) {
                    lm.modCount++;
                    remove();//从当前链表节点挪走
                    addBefore(lm.header);//添加为新的header
                }
            }
    

    所以,多次访问后,链表的数据关系为:
    -第一个访问--第二个访问--第三个访问--header--最久没有访问-(这是一个双向链表)
    所以,header前面是最近访问的,header后面是最久没有访问的。

    因为遍历地时候会从header开始:

        private abstract class LinkedHashIterator<T> implements Iterator<T> {
            LinkedHashMapEntry<K,V> nextEntry    = header.after;
    

    所以,最前面取得的数据就是最久没有访问的数据。

    LruCache

    因为LinkedHashMap可以根据最近访问进行排序,所以LruCache使用LinkedHashMap来存储数据:

        public LruCache(int maxSize) {
            ...
            this.maxSize = maxSize;
            this.map = new LinkedHashMap<K, V>(0, 0.75f, true);//开启LinkedHashMap的访问排序
        }
    

    LinkeHashMap是可以自动扩容的,所以在LruCache中需要限制数据集合的上限,主要方法就是在put时,挤走最久没有访问的数据:

        public final V put(K key, V value) {
            ...
            trimToSize(maxSize);//挤走最久没有访问的数据
            return previous;
        }
    

    其实就是从header头开始遍历LinkedHashMap,依次从最久没有访问的数据开始清理:

        public void trimToSize(int maxSize) {
            while (true) {
                K key;
                V value;
                synchronized (this) {
                    ...
                    if (size <= maxSize) {
                        break;
                    }
                    Map.Entry<K, V> toEvict = map.eldest();
                    if (toEvict == null) {
                        break;
                    }
                    ...
                    map.remove(key);
                    ...
                }
    
                entryRemoved(true, key, value, null);
            }
        }
    

    相关文章

      网友评论

          本文标题:LinkedHashMap和LruCache

          本文链接:https://www.haomeiwen.com/subject/ydqiixtx.html