Java容器解析系列(17) LruCache详解

Wesley13
• 阅读 401

在之前讲LinkedHashMap的时候,我们说起可以用来实现LRU(least recent used)算法,接下来我看一下其中的一个具体实现-----android sdk 中的LruCache.

关于Lru算法,请参考漫画:什么是LRU算法?

talk is cheap, I am gonna show you something really expensive.

package android.util;// 该类是从Android sdk 中摘录

public class LruCache<K, V> {

    private final LinkedHashMap<K, V> map;// 这里的 LinkedHashMap 为 android.jar 中的类,与jdk中的有所区别,这里不做区分
    private int size;// 当前 cache 的大小
    private int maxSize;// cache 最大容量
    private int putCount;// put() 调用的次数
    private int createCount;// get()未命中,成功构建新 key:value 的次数
    private int evictionCount;// 因cache大小超过容量限制,将 key:value 从 cache 中驱逐的次数
    private int hitCount;// get()命中的次数
    private int missCount;// get()未命中的次数

    // 构造时设置最大容量
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        // 这里传入的 LinkedHashMap 的 accessOrder 为true,表示 其中的链表中的结点顺序为 "按访问顺序"
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

    // 重新设置 cache 最大容量
    public void resize(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        synchronized (this) {
            this.maxSize = maxSize;
        }
        trimToSize(maxSize);
    }

    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V mapValue;
        synchronized (this) {// 同步访问
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;// 命中次数 + 1
                return mapValue;
            }
            missCount++;// 未命中次数 + 1
        }
        V createdValue = create(key);// 通过 key 构建一个value(比如从文件中读入value)
        if (createdValue == null) {// 创建失败
            return null;
        }
        synchronized (this) {
            createCount++;// 构建 value 成功次数 + 1
            mapValue = map.put(key, createdValue);// 添加到 LinkedHashMap 中
            if (mapValue != null) {
                // LinkedHashMap 原来有该key的值(在构建value的时候,被其他线程添加进去的),这里重新把原来的值放进去,cache大小没有增加
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);// cache 大小增加
            }
        }
        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);// 大小增加了,保证在最大容量范围内
            return createdValue;
        }
    }

    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }
        V previous;
        synchronized (this) {
            putCount++;// put 次数
            size += safeSizeOf(key, value);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);// 替换已有的value
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        trimToSize(maxSize);
        return previous;
    }

    // 移除LRU键值对,保证 cache 的大小在 maxSize 范围内
    public void trimToSize(int maxSize) {
        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!");
                }
                if (size <= maxSize) {
                    break;
                }
                Map.Entry<K, V> toEvict = map.eldest();// 最老的结点,返回head结点,也即 LRU结点
                if (toEvict == null) {// 没有可以删除的key:value了
                    break;
                }
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);// 大小降低
                evictionCount++;// 驱逐次数 + 1
            }
            entryRemoved(true, key, value, null);
        }
    }

    public final V remove(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V previous;
        synchronized (this) {
            previous = map.remove(key);// 通过 LinkedHashMap 移除
            if (previous != null) {
                size -= safeSizeOf(key, previous);// cache总大小降低
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, null);
        }
        return previous;
    }

    // key:oldValue 被 移除 或 驱逐 时回调
    protected void entryRemoved(boolean evicted/*是否是被驱逐(因cache大小超过容量限制被删除)*/,
                                K key, V oldValue, V newValue) {
    }

    // 根据指定 key,构建 value
    protected V create(K key) {
        return null;
    }

    private int safeSizeOf(K key, V value) {
        int result = sizeOf(key, value);
        if (result < 0) {
            throw new IllegalStateException("Negative size: " + key + "=" + value);
        }
        return result;
    }

    // key:value 键值对大小,用于计算cache大小
    // 可根据情况自定义,默认为 1
    // 该 key:value 在 cache 中时大小不应该变化
    protected int sizeOf(K key, V value) {
        return 1;
    }

    public final void evictAll() {
        trimToSize(-1); // -1 will evict 0-sized elements
    }

    // 各种方法,返回成员变量,省略
    public synchronized final Map<K, V> snapshot() {
        return new LinkedHashMap<K, V>(map);
    }

    @Override
    public synchronized final String toString() {
        int accesses = hitCount + missCount;
        int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
        return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
                maxSize, hitCount, missCount, hitPercent);
    }

}
点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Wesley13 Wesley13
2年前
1. 容器化部署一套云服务 第一讲 Jenkins(Docker + Jenkins + Yii2 + 云服务器))
容器化部署一套云服务系列1\.容器化部署一套云服务之Jenkins(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.cnblogs.com%2Fjackson0714%2Fp%2Fdeploy1.html)一、购买服务器服务器!caeef00
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
2年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这