最新消息:欢迎访问Android开发中文站!商务联系QQ:1304524325

Android 内存缓存:手把手教你学会LrhCache算法

开发进阶 loading 515浏览 1评论

前言

  • 内存缓存知识在Android开发中实现重要
  • 本文将全面介绍内存缓存的所有相关知识(含LrhCache算法、其原理等),希望您们会喜欢

目录

内存缓存


1. 简介

示意图

下面,将详细介绍 LrhCache算法


2. LrhCache算法

示意图


3. 实现原理

  • LrhCache算法的算法核心 = LRU 算法 + LinkedHashMap数据结构
  • 下面,我将先介绍LRU 算法 和 LinkedHashMap数据结构,最后再介绍LrhCache算法

3.1 LRU 算法

  • 定义:Least Recently Used,即 近期最少使用算法
  • 算法原理:当缓存满时,优先淘汰 近期最少使用的缓存对象

    采用 LRU 算法的缓存类型:内存缓存(LrhCache) 、 硬盘缓存(DisLruCache

3.2 LinkedHashMap 介绍

  • 数据结构 = 数组 +单链表 + 双向链表
  • 其中,双向链表 实现了 存储顺序 = 访问顺序 / 插入顺序
    1. 使得LinkedHashMap 中的<key,value>对 按照一定顺序进行排列
    2. 通过 构造函数 指定LinkedHashMap中双向链表的结构是访问顺序 or 插入顺序
/** 
  * LinkedHashMap 构造函数
  * 参数accessOrder = true时,存储顺序(遍历顺序) = 外部访问顺序;为false时,存储顺序(遍历顺序) = 插入顺序
  **/ 
  public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {

        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;

    }
  • 实例演示

当 accessOrder 参数设置为true时,存储顺序(遍历顺序) = 外部访问顺序

  /** 
    * 实例演示
    **/ 
    // 1. accessOrder参数设置为true时
    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 0.75f, true);

    // 2. 插入数据
    map.put(0, 0);
    map.put(1, 1);
    map.put(2, 2);
    map.put(3, 3);
    map.put(4, 4);
    map.put(5, 5);
    map.put(6, 6);

    // 3. 访问数据
        map.get(1);
        map.get(2);

     // 遍历获取LinkedHashMap内的数据
     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());

        }

  /** 
    * 测试结果
    **/ 
   0:0
   3:3
   4:4
   5:5
   6:6
   1:1
   2:2

// 即实现了 最近访问的对象 作为 最后输出
// 该逻辑 = LrhCache缓存算法思想
// 可见LruCache的实现是利用了LinkedHashMap数据结构的实现原理
// 请看LruCache的构造方法

 public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;

        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
        // 创建LinkedHashMap时传入true。即采用了存储顺序 = 外界访问顺序 = 最近访问的对象 作为 最后输出
    }

3.3 LrhCache 算法原理

示意图

  • 示意图

示意图


4. 使用流程

/** 
  * 使用流程(以加载图片为例)
  **/ 

    private LruCache<String, Bitmap> mMemoryCache; 

    // 1. 获得虚拟机能提供的最大内存
    // 注:超过该大小会抛出OutOfMemory的异常 
    final int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024); 

    // 2. 设置LruCache缓存的大小 = 一般为当前进程可用容量的1/8
    // 注:单位 = Kb
    // 设置准则
    //  a. 还剩余多少内存给你的activity或应用使用
    //  b. 屏幕上需要一次性显示多少张图片和多少图片在等待显示
    //  c. 手机的大小和密度是多少(密度越高的设备需要越大的 缓存)
    //  d. 图片的尺寸(决定了所占用的内存大小)
    //  e. 图片的访问频率(频率高的在内存中一直保存)
    //  f. 保存图片的质量(不同像素的在不同情况下显示)
    final int cacheSize = maxMemory / 8; 

    // 3. 重写sizeOf方法:计算缓存对象的大小(此处的缓存对象 = 图片)
    mMemoryCache = new LruCache<String, Bitmap>(cacheSize) { 

        @Override 
        protected int sizeOf(String key, Bitmap bitmap) { 

            return bitmap.getByteCount() / 1024; 
            // 此处返回的是缓存对象的缓存大小(单位 = Kb) ,而不是item的个数
            // 注:缓存的总容量和每个缓存对象的大小所用单位要一致
            // 此处除1024是为了让缓存对象的大小单位 = Kb

        } 
    }; 

    // 4. 将需缓存的图片 加入到缓存
    mMemoryCache.put(key, bitmap); 

    // 5. 当 ImageView 加载图片时,会先在LruCache中看有没有缓存该图片:若有,则直接获取
    mMemoryCache.get(key); 

5. 实例讲解

  • 本实例以缓存图片为实例讲解
  • 具体代码

请看注释
MainActivity.java

public class MainActivity extends AppCompatActivity {

    public static final String TAG = "carsonTest:";
    private LruCache<String, Bitmap> mMemoryCache;
    private ImageView mImageView;
    private Button button;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        // 1. 获得虚拟机能提供的最大内存
        // 注:超过该大小会抛出OutOfMemory的异常
        final int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);

        // 2. 设置LruCache缓存的大小 = 一般为当前进程可用容量的1/8
        // 注:单位 = Kb
        final int cacheSize = maxMemory / 8;

        // 3. 重写sizeOf方法:计算缓存对象的大小(此处的缓存对象 = 图片)
        mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {

            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                return bitmap.getByteCount() / 1024;
                // 此处返回的是缓存对象的缓存大小(单位 = Kb) ,而不是item的个数
                // 注:缓存的总容量和每个缓存对象的大小所用单位要一致
                // 此处除1024是为了让缓存对象的大小单位 = Kb

            }
        };

        // 4. 点击按钮,则加载图片
        mImageView = (ImageView)findViewById(R.id.image);
        button = (Button)findViewById(R.id.btn);
        button.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View view) {
                // 加载图片 ->>分析1
                loadBitmap("test",mImageView);
            }

        });

    }

    /**
     * 分析1:加载图片
     * 加载前,先从内存缓存中读取;若无,则再从数据源中读取
     **/
    public void loadBitmap(String key, ImageView imageView) {

        // 读取图片前,先从内存缓存中读取:即看内存缓存中是否缓存了该图片
        // 1. 若有缓存,则直接从内存中加载
        Bitmap bitmap = mMemoryCache.get(key);

        if (bitmap != null) {
            mImageView.setImageBitmap(bitmap);
            Log.d(TAG, "从缓存中加载图片 ");

            // 2. 若无缓存,则从数据源加载(此处选择在本地加载) & 添加到缓存
        } else {
            Log.d(TAG, "从数据源(本地)中加载: ");

            // 2.1 从数据源加载
            mImageView.setImageResource(R.drawable.test1);

            // 2.1 添加到缓存
            // 注:在添加到缓存前,需先将资源文件构造成1个BitMap对象(含设置大小)
            Resources res = getResources();
            Bitmap bm = BitmapFactory.decodeResource(res, R.drawable.test1);

            // 获得图片的宽高
            int width = bm.getWidth();
            int height = bm.getHeight();

            // 设置想要的大小
            int newWidth = 80;
            int newHeight = 80;

            // 计算缩放比例
            float scaleWidth = ((float) newWidth) / width;
            float scaleHeight = ((float) newHeight) / height;
            // 取得想要缩放的matrix参数
            Matrix matrix = new Matrix();
            matrix.postScale(scaleWidth, scaleHeight);
            // 构造成1个新的BitMap对象
            Bitmap bitmap_s = Bitmap.createBitmap(bm, 0, 0, width, height, matrix, true);

            // 添加到缓存
            if (mMemoryCache.get(key) == null) {
                mMemoryCache.put(key, bitmap_s);
                Log.d(TAG, "添加到缓存: " + (mMemoryCache.get(key)));
            }

        }
    }

}

activity_main.xml

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    android:focusableInTouchMode="true"
    android:orientation="vertical">

    <ImageView
       android:id="@+id/image"
       android:layout_width="200dp"
       android:layout_height="200dp"
       android:layout_gravity="center"

        />

    <Button
        android:id="@+id/btn"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_margin="10dp"
        android:text="点击加载"
        android:layout_gravity="center"
        />

</LinearLayout>
  • 测试结果
    第1次点击加载图片时,由于无缓存则从本地加载
    第2次(以后)点击加载图片时,由于有缓存,所以直接从缓存中读取
    示意图

6. 源码分析

此处主要分析 写入缓存 & 获取缓存 ,即put()、 get()

6.1 添加缓存:put()

  • 源码分析
/** 
  * 使用函数(以加载图片为例)
  **/ 
  mMemoryCache.put(key,bitmap);

/** 
  * 源码分析
  **/ 
 public final V put(K key, V value) {

        // 1. 判断 key 与 value是否为空
        //  若二者之一味空,否则抛出异常
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;

        synchronized (this) {

            // 2. 插入的缓存对象值加1
            putCount++; 

            // 3. 增加已有缓存的大小
            size += safeSizeOf(key, value); 

            // 4. 向map中加入缓存对象
            previous = map.put(key, value);

            // 5. 若已有缓存对象,则缓存大小恢复到之前
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        // 6. 资源回收(移除旧缓存时会被调用)
        // entryRemoved()是个空方法,可自行实现
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }

        // 7. 添加缓存对象后,调用需判断缓存是否已满
        // 若满了就删除近期最少使用的对象-->分析2
        trimToSize(maxSize);

        return previous;
    }

/** 
  * 分析1:trimToSize(maxSize)
  * 原理:不断删除LinkedHashMap中队尾的元素,即近期最少访问的元素,直到缓存大小 < 最大值
  **/ 
  public void trimToSize(int maxSize) {

        //死循环
        while (true) {
            K key;
            V value;
            synchronized (this) {
                // 判断1:若 map为空 & 缓存size ≠ 0 或 缓存size < 0,则抛出异常
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                // 判断2:若缓存大小size < 最大缓存 或 map为空,则不需删除缓存对象,跳出循环
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }

                // 开始删除缓存对象
                // 使用迭代器获取第1个对象,即队尾的元素 = 近期最少访问的元素
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                // 删除该对象 & 更新缓存大小
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            entryRemoved(true, key, value, null);
        }
    }

至此,关于添加缓存:put()的源码分析完毕。

6.2 获取缓存:get()

  • 作用:获取缓存 & 更新队列
    1. 当调用 get() 获取缓存对象时,就代表访问了1次该元素
    2. 访问后将会更新队列,使得整个队列是按照 访问顺序 排列
  • 示意图如下
    示意图

上述更新过程是在 get()中完成

  • 源码分析
/** 
  * 使用函数(以加载图片为例)
  **/ 
  mMemoryCache.get(key);

/** 
  * 源码分析
  **/ 
  public final V get(K key) {

        // 1. 判断输入的合法性:若key为空,则抛出异常
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {

            // 2. 获取对应的缓存对象 & 将访问的元素 更新到 队列头部->>分析3
            mapValue = map.get(key);

            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

/** 
  * 分析1:map.get(key)
  * 实际上是 LinkedHashMap.get() 
  **/ 
  public V get(Object key) {

        // 1. 获取对应的缓存对象
        LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
        if (e == null)
            return null;

        // 2. 将访问的元素更新到队列头部 ->>分析4
        e.recordAccess(this);

        return e.value;
    }
/** 
  * 分析2:recordAccess()
  **/ 
  void recordAccess(HashMap<K,V> m) {

            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;

            // 1. 判断LinkedHashMap存储顺序是否按访问排序排序:根据构造函数传入的参数accessOrder判断
            if (lm.accessOrder) {
                lm.modCount++;
                // 2. 删除此元素
                remove();
                // 3. 将此元素移动到队列的头部
                addBefore(lm.header);
            }
        }

至此,关于获取缓存:get()的源码分析完毕。


7. 总结

本文全面讲解了内存缓存的相关知识,含LrhCache算法、原理等,下面是部分总结

  • 原理
    示意图
  • 示意图
    示意图
  • 源码流程
    示意图

转载请注明:Android开发中文站 » Android 内存缓存:手把手教你学会LrhCache算法

您必须 登录 才能发表评论!

网友最新评论 (1)

  1. 清晰详细
    hello_fhy2018-09-11 07:52