标签搜索

基于双向链表的LRU算法

Pop.Kite
2023-09-04 / 0 评论 / 86 阅读 / 正在检测是否收录...

LRU-least recently used-最近最少使用算法,是一种内存数据淘汰策略,使用常见是当内存不足时,需要淘汰最近最少使用的数据。LRU常用于缓存系统的淘汰策略。

下面是一个基于哈希链表的LRU算法展示

/**
 * [capacity] the capacity of cache
 */
class LRUFunc(private val capacity: Int) {

    companion object {
        private const val HEAD = "HEAD_NODE"
        private const val TAIL = "TAIL_NODE"
    }

    /**
     * A map for store data.
     */
    public val mCacheContentMap = ConcurrentHashMap<Any, LruNode<*, *>>()

    /**
     * the head of double LinkedList.
     */
    private var head: LruNode<String, String> = LruNode(HEAD, "")

    /**
     * the last of double LinkedList.
     */
    private var tail: LruNode<String, String> = LruNode(TAIL, "")

    /**
     * current content size .
     */
    private var count = 0

    init {
        head.preNode = null
        head.nextNode = tail
        tail.preNode = head
        tail.nextNode = null
    }

    /**
     * save data into map
     * if already contains the key, update.
     */
    inline fun <reified K, reified V> put(key: K, value: V) {
        if (mCacheContentMap[key as Any] == null) {
            with(LruNode(key, value)) {
                mCacheContentMap[key] = this
                addNode(this)
            }
        } else {
            mCacheContentMap[key]?.let { updateNode(it) }
        }
    }

    /**
     * get data from map
     */
    fun <K, V> get(key: K): V? {
        return mCacheContentMap[key as Any]?.let {
            updateNode(it)
            it.value as V
        }
    }

    /**
     * add a node to double LinkedList.
     * the last node should be added to the first position in list.
     */
    fun <K, V> addNode(node: LruNode<K, V>) {
        ++count
        val preNode = head
        val nextNode = head.nextNode

        node.preNode = head
        node.nextNode = nextNode
        nextNode?.preNode = node
        preNode.nextNode = node

        if (count > capacity) {
            mCacheContentMap.remove(popTail())
        }
    }

    /**
     * the node should be updated to the first position in list.
     */
    fun <K, V> updateNode(node: LruNode<K, V>) {
        removeNode(node)
        addNode(node)
    }

    /**
     * the least used data should be removed.
     * the node located on the tail node before.
     */
    private fun <K, V> removeNode(node: LruNode<K, V>) {
        --count
        node.nextNode?.preNode = node.preNode
        node.preNode?.nextNode = node.nextNode
    }

    private fun <T> popTail(): T? {
        val node = tail.preNode?.apply {
            removeNode(this)
        }
        return node?.key as T
    }
}

/**
 * Node Data Clas
 */
data class LruNode<K, V>(val key: K, val value: V) {
    var preNode: LruNode<*, *>? = null
    var nextNode: LruNode<*, *>? = null
}

fun log(msg: String) {
//    println("logcat: ${msg}")
}
LRU原理与算法实现 - 知乎 (zhihu.com)
0

评论 (0)

取消