LRU(Least Recently Used)最近最少使用,选择最近最少使用的元素进行淘汰的算法
基于LinkedHashMap进行存储与顺序维护
LinkedHashMap的构造方法中,accessOrder参数传入true,代表按访问顺序排序,每次获取元素,会将该元素放在链表末尾;传入false代表按插入顺序排序,不受获取元素的影响。
LRU借助了LinkedHashMap的使用顺序排序的特性,每次访问时,会将元素放到链表末尾,当存储的size达到限制时,就直接从链表头部移除元素(trimToSize方法),直到size在限制之内。
在通过AndroidStudio看LruCache的源码时,可能会遇到trimToSize方法的实现与我们所想的不同,逻辑写的是移除末尾元素,如:
不必迷茫,正如注释所说,这段代码是无效代码,这样写是为了在不同平台上减少更改。
所以这段代码我们应该去看真正的安卓源码,而不是SDK提供的这段代码。
真正的代码如下:
使用LRU时,一般要继承LRU类,重写sizeOf方法,返回元素对应的大小,用于计算占用
总结
- LruCache借助了LinkedHashMap可根据访问顺序排序的特性,完成自身的实现
- LruCache的总体逻辑是每次访问元素时,将元素放置在链表末尾,当Size不足时,则从链表头部依次删除元素,直到有空余Size