LruCache

先说结论吧:
由此可见LruCache中维护了一个集合LinkedHashMap,该LinkedHashMap是以访问顺序排序的。当调用put()方法时,就会在结合中添加元素,并调用trimToSize()判断缓存是否已满,如果满了就用LinkedHashMap的迭代器删除队尾元素,即最近最少访问的元素。当调用get()方法访问缓存对象时,就会调用LinkedHashMap的get()方法获得对应集合元素,同时会更新该元素到队头。
下面的问题,怎么实现的?

LinkedHashMap

Lru的算法就是通过LinkedHashMap来实现的。

public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder)

initialCapacity,初始容量
loadFactor,碰撞因子,0.75f
accessOrder,是否控制访问更新排序,false,就是默认插入的顺序。
我们要实现LruCache,就需要依赖LinkedHashMap这个特性。

源码分析

以下是kotlin实现的LruCache的简单版本

class AlgoLruCache<K,V> {
    private lateinit var linkedHashMap:LinkedHashMap<K,V>
    private var size = 0
    private var maxSize = 0

    constructor(maxSize:Int){
        require(maxSize>0){"maxSize <=0"}
        this.maxSize = maxSize
        linkedHashMap = LinkedHashMap(0,0.75f,true)
    }

    fun reSize(size:Int){
        synchronized(this){
            this.maxSize = size
        }
        trimToSize(maxSize)
    }

    @Throws(IllegalArgumentException::class)
    private fun trimToSize(maxSize: Int) {
        lit@ while(true) {
            synchronized(this){
                if(size<0|| linkedHashMap.isEmpty() && size!=0){
                    throw IllegalArgumentException("size is wrong")
                }

                if(size<=maxSize){
                    return@lit
                }

                //find end one of hashMap
                var toEvict: Map.Entry<K, V>? = null
                linkedHashMap.forEach {
                    toEvict = it
                }

                if(toEvict == null){
                    return@lit
                }
                var key = toEvict!!.key
                var value = toEvict!!.value
                linkedHashMap.remove(key)
                size -=1
            }
        }
    }

    fun remove(key:K):V?{
        var previous:V? = null
        synchronized(this){
            previous = linkedHashMap.remove(key)
            if(previous !=null){
                size -=1
            }
        }
        return previous
    }

    fun put(key:K,value:V):V?{
        var previous:V? = null
        synchronized(this){
            size +=1
            previous = linkedHashMap.put(key, value)
            if(previous!=null){
                size -=1
            }
        }
        trimToSize(maxSize)
        return previous
    }

    fun get(key: K):V?{
        var mapValue: V? = null
        synchronized(this){
            mapValue = linkedHashMap[key]
            if(mapValue!=null){
                return mapValue
            }
        }
        return null
    }
}

依次来分析,这样我们对于LruCache的基本实现也就了解了。

constructor

干了2件事件,设置maxSize。这格式cache的大小。
初始化LinkedHashMap,这个已经解释过了。

reSize & trimToSize

重新设置maxSize的大小,也就是cache的大小。
这个设置其实很好理解,maxSize扩大,就不做任何调整。如果maxSize减少,或者如代码理解的,如果size>maxSize,我们就需要删除最后一个数据,直到size小于等于maxSize。

remove

直接调用LinkedHashMap的接口remove,根据remove的结果,判断size接口。

put

put其实分2种情况,这个上面代码参考了官方实现,先

            size +=1
            previous = linkedHashMap.put(key, value)
            if(previous!=null){
                size -=1
            }

这个设计的很nice。

get

也设计的很简单,对linkedHashMap的调用而已。那所谓的最近使用,放在map的最上面是在哪里实现的呢。从LruCache源码看,并没有这部分功能的实现,so,linkedHashMap内部实现了get和put的关键操作。
即get的时候,把当前的V移到map的最前面,put的时候,如果有需要,就把map最后一个位置内容清除。
为什么是linkedHashMap,在下一篇文章来解释。

发表评论

电子邮件地址不会被公开。 必填项已用*标注