LruCache 使用及原理

5,102 阅读5分钟

1. LruCache 是什么?

要搞清楚 LruCache 是什么之前,首先要知道 Android 的缓存策略。其实缓存策略很简单,举个例子,就是用户第一次使用网络加载一张图片后,下次加载这张图片的时候,并不会从网络加载,而是会从内存或者硬盘加载这张图片。

缓存策略分为添加、获取和删除,为什么需要删除缓存呢?因为每个设备都会有一定的容量限制,当容量满了的话就需要删除。

那什么是 LruCache 呢?其实 LRU(Least Recently Used) 的意思就是近期最少使用算法,它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。

2. LruCache 怎么用?

现在使用 okhttp 加载网上的一张图片:

新建一个 ImageLoader 类:

public class ImageLoader {

    private LruCache<String, Bitmap> lruCache;

    public ImageLoader() {
        int maxMemory = (int)(Runtime.getRuntime().maxMemory() / 1024);
        int cacheSize = maxMemory / 8;
        lruCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
            }
        };
    }

    public void addBitmap(String key, Bitmap bitmap) {
        if (getBitmap(key) == null) {
            lruCache.put(key, bitmap);
        }
    }

    public Bitmap getBitmap(String key) {
        return lruCache.get(key);
    }

}

重写 sizeOf() 就是来计算一个元素的缓存的大小的,当存放的元素的总缓存大小大于 cacheSize 的话,LruCache 就会删除最近最少使用的元素。

MainActivity:

public class MainActivity extends AppCompatActivity {

    private String Path = "https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1532852517262&di=bcbc367241183c39d6e6c9ea2f879166&imgtype=0&src=http%3A%2F%2Fimg4q.duitang.com%2Fuploads%2Fitem%2F201409%2F07%2F20140907002919_eCXPM.jpeg";

    private Button btn;

    private ImageView imageView;

    private ImageLoader imageLoader;

    private static final int SUCCESS = 1;
    private static final int FAIL = 2;

    Handler handler = new Handler() {
        @Override
        public void handleMessage(Message msg) {
            switch (msg.what) {
                case SUCCESS:
                    byte[] Picture = (byte[]) msg.obj;
                    Bitmap bitmap = BitmapFactory.decodeByteArray(Picture, 0, Picture.length);
                    imageLoader.addBitmap("bitmap", bitmap);
                    imageView.setImageBitmap(bitmap);

                    break;
                case FAIL:
                    break;
            }
        }
    };

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

        btn = findViewById(R.id.btn);
        imageView = findViewById(R.id.imageview);
        imageLoader = new ImageLoader();
        btn.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                Bitmap bitmap = getBitmapFromCache();
                if(bitmap != null) {
                    imageView.setImageBitmap(bitmap);
                } else {
                    getBitmapFromInternet();
                }
            }
        });

    }

    private Bitmap getBitmapFromCache() {
        Log.e("chan", "===============getBitmapFromCache");
        return imageLoader.getBitmap("bitmap");
    }

    private void getBitmapFromInternet() {
        Log.e("chan", "===============getBitmapFromInternet");
        OkHttpClient okHttpClient = new OkHttpClient();
        Request request = new Request.Builder()
                .url(Path)
                .build();
        Call call = okHttpClient.newCall(request);
        call.enqueue(new Callback() {
            @Override
            public void onFailure(Call call, IOException e) {

            }

            @Override
            public void onResponse(Call call, Response response) throws IOException {
                byte[] Picture_bt = response.body().bytes();
                Message message = handler.obtainMessage();
                message.obj = Picture_bt;
                message.what = SUCCESS;
                handler.sendMessage(message);
            }
        });
    }

}

这个方法很简单,就是使用 okhttp 从网络加载一张图片,如果不过在网络加载前就会先查看缓存里面是否有这张图片,如果存在就直接从缓存加载。

3. LruCache 原理

LruCache 其实使用了 LinkedHashMap 双向链表结构,现在分析下 LinkedHashMap 使用方法。

构造方法:

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

当 accessOrder 为 true 时,这个集合的元素顺序就会是访问顺序,也就是访问了之后就会将这个元素放到集合的最后面。

LinkedHashMap < Integer, Integer > map = new LinkedHashMap < > (0, 0.75f, true);
map.put(0, 0);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.get(1);
map.get(2);

for (Map.Entry < Integer, Integer > entry: map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());

}

打印结果:

0:0
3:3
1:1
2:2

以下分别来分析 LruCache 的 put 和 get 方法。

3.1 put 方法分析:

现在以注释的方式来解释该方法的原理。

public final V put(K key, V value) {
    // 如果 key 或者 value 为 null,则抛出异常
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }

    V previous;
    synchronized(this) {
        // 加入元素的数量,在 putCount() 用到
        putCount++;

        // 回调用 sizeOf(K key, V value) 方法,这个方法用户自己实现,默认返回 1
        size += safeSizeOf(key, value);

        // 返回之前关联过这个 key 的值,如果没有关联过则返回 null
        previous = map.put(key, value);

        if (previous != null) {
            // safeSizeOf() 默认返回 1
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        // 该方法默认方法体为空
        entryRemoved(false, key, previous, value);
    }

    trimToSize(maxSize);

    return previous;
}

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!");
            }

            // 直到缓存大小 size 小于或等于最大缓存大小 maxSize,则停止循环
            if (size <= maxSize) {
                break;
            }

            // 取出 map 中第一个元素
            Map.Entry < K, V > toEvict = map.eldest();
            if (toEvict == null) {
                break;
            }

            key = toEvict.getKey();
            value = toEvict.getValue();
            // 删除该元素
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
        }

        entryRemoved(true, key, value, null);
    }
}

public Map.Entry<K, V> eldest() {
    return head;
}

put() 方法其实重点就在于 trimToSize() 方法里面,这个方法的作用就是判断加入元素后是否超过最大缓存数,如果超过就清除掉最少使用的元素。

3.2 get 方法分析

public final V get(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized(this) {
        // 获取 Value
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }

    ......
}

// LinkedHashMap get 方法
public V get(Object key) {
    Node < K, V > e;
    if ((e = getNode(hash(key), key)) == null) return null;
    if (accessOrder) afterNodeAccess(e);
    return e.value;
}

static class Node < K, V > implements Map.Entry < K, V > {
    final int hash;
    final K key;
    V value;
    Node < K, V > next;

    Node(int hash, K key, V value, Node < K, V > next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey() {
        return key;
    }
    public final V getValue() {
        return value;
    }
    public final String toString() {
        return key + "=" + value;
    }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Map.Entry) {
            Map.Entry <? , ?> e = (Map.Entry <? , ?> ) o;
            if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true;
        }
        return false;
    }
}

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

get() 方法其实最关键就是 afterNodeAccess(),现在重点分析:

3.2.1 关键方法 afterNodeAccess()

// 这个方法的作用就是将刚访问过的元素放到集合的最后一位
void afterNodeAccess(Node < K, V > e) { 
    LinkedHashMap.Entry < K, V > last;
    if (accessOrder && (last = tail) != e) {
        // 将 e 转换成 LinkedHashMap.Entry
        // b 就是这个节点之前的节点
        // a 就是这个节点之后的节点
        LinkedHashMap.Entry < K, V > p = (LinkedHashMap.Entry < K, V > ) e, b = p.before, a = p.after;

        // 将这个节点之后的节点置为 null
        p.after = null;

        // b 为 null,则代表这个节点是第一个节点,将它后面的节点置为第一个节点
        if (b == null) head = a;
        // 如果不是,则将 a 上前移动一位
        else b.after = a;
        // 如果 a 不为 null,则将 a 节点的元素变为 b
        if (a != null) a.before = b;
        else last = b;
        if (last == null) head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

链表情况可能性图示:

以下来分析情况一。

3.1.2.1 情况一:

1. p.after = null;

图示:

2. b.after = a; a.before = b;

图示:

3. p.before = last; last.after = p;

图示:

情况一其实与其他情况基本一样,这里就不再赘述了。

4. 总结

  • LruCache 其实使用了 LinkedHashMap 维护了强引用对象
  • 总缓存的大小一般是可用内存的 1/8,当超过总缓存大小会删除最少使用的元素,也就是内部 LinkedHashMap 的头部元素
  • 当使用 get() 访问元素后,会将该元素移动到 LinkedHashMap 的尾部