再谈LRU双链表内存管理

N年前我写了个双链表也发了博客，还添了代码。但是那个代码不但复杂，而且还有有问题的，一直懒得整理，放在空间误导别人。最近在写服务端，今天抽点空补一篇。

关于LRU网上随便搜，有过后端经验的人应该很多都研究过。所谓双链表一个是哈希表，用于通过Key来查数据，另一个表是用来表示顺序，越前面的元素越新（也可以理解为越接近当前系统时间）。我以前写那个LRU，用一个哈希和一个数组，查哈希没什么问题，但是查数组用了indexof和splice就问题大了，呵呵，每次get数据都splice一次，那效率烂shi了。

正确的做法只需要一个哈希数组就可以了，另一个链表并不需要另开数组存，只需要给入库的哈希对象包一个新对象，新对象有prev和next即上一个下一个两节点即可表示先后顺序。另外再需要top和bottom两个变量来存头尾。

用一行代码表达：map[key] = {target=target,key=key,prev=XX,next=XX}。

最近在写lua，贴一段lua版本的lru

-- 双链表LRU内存管理
-- 充分利用空间来换时间查找和删除过期数据
-- 哈希cacheMap用于主键存取查找，另一个链表是每个节点的prev和next来表示时间先后
-- Author: Pelephone
-- Date:2016-04-16 16:53:36

LRUMgr = class(LRUMgr)

-- 初始
function LRUMgr:__init()
    -- 过期时间(多少秒之后过期)
    self.expireTime = 60*60*2

    -- 顶部节点，最新访问
    self.top = nil
    -- 最后节点，最旧的元素
    self.bottom = nil

    -- 过期时间(多少秒之后过期)
    self.expireTime = 60*60*2
    -- 最大缓存个数
    self.maxLen = 9999

    -- 目标对象的映射
    self.cacheMap = {}
     setmetatable(self.cacheMap,{__mode = "k"})

    -- 总共缓存的数量
    self.totLen = 0
end

-- 添加一个缓存对象
function LRUMgr:set(key,target)
    local cacheObj = self.cacheMap[key]
    if not cacheObj then
        cacheObj = {key=key,target=target}
        self.cacheMap[key] = cacheObj

        if not self.top and not self.bottom then
            self.top = cacheObj
            self.bottom = cacheObj
        end
        self.totLen = self.totLen + 1
    end

    -- get一下放直队顶
    self:get(key)

    -- 超过最大缓存量，移出一下队尾
    if self.totLen > self.maxLen then
        self:remove(self.bottom.key)
    end
end

-- 获取缓存，返回对象的同时把对象移动队顶
function LRUMgr:get(key)
    local cacheObj = self.cacheMap[key]
    if not cacheObj then
        return nil
    end

    if cacheObj == self.top then
        cacheObj.time = self:getNowTime()
        return cacheObj.target
    end

    -- 上下节点连接，然后把当前节放到队顶
    if cacheObj.prev and cacheObj.next then
        local tmpNext = cacheObj.prev
        cacheObj.prev.next = cacheObj.next
        cacheObj.next.prev = tmpNext
    end

    -- 新对象插入队头，队头是最新命中的节点
    if self.top then
        self.top.prev = cacheObj
    end
    cacheObj.next = self.top
    cacheObj.prev = nil
    self.top = cacheObj
    cacheObj.time = self:getNowTime()
    return cacheObj.target
end

-- 移出缓存
function LRUMgr:remove(key)
    local cacheObj = self.cacheMap[key]
    if not cacheObj then
        return nil
    end

    -- 上下节点连接，然后把当前节放到队顶
    if cacheObj == self.top then
        self.top = self.top.next
        if self.top then
            self.top.prev = nil
        end
        if self.totLen == 1 then
            self.bottom = nil
        end
    elseif cacheObj == self.bottom then
        self.bottom = self.bottom.prev
        if self.bottom then
            self.bottom.next = nil
        end
        if self.totLen == 1 then
            self.top = nil
        end
    else
        local tmpNext = cacheObj.prev
        cacheObj.prev.next = cacheObj.next
        cacheObj.next.prev = tmpNext
    end
    self.totLen = self.totLen - 1
    self.cacheMap[key] = nil
    cacheObj.prev = nil
    cacheObj.next = nil
    cacheObj.target = nil
end

-- 清理过期对象
function LRUMgr:clearExpire()
    local nExpireTime = self:getNowTime() - self.expireTime
    -- 从队尾开始删除缓存，直到删到没到期的对象
    while self.totLen > 0 and self.bottom.time < nExpireTime do
        local newBtm = self.bottom.prev
        if newBtm then
            newBtm.next = nil
        end

        self.cacheMap[self.bottom.key] = nil
        self.bottom.prev = nil
        self.bottom.next = nil
        self.bottom.target = nil

        self.totLen = self.totLen - 1
        self.bottom = newBtm
    end
end

-- 清除所有缓存
function LRUMgr:removeALl()
    -- for k,v in pairs(self.cacheMap) do
    --     self.cacheMap[k] = nil
    -- end
    self.cacheMap = {}
     setmetatable(self.cacheMap,{__mode = "k"})
     self.top = nil
     self.bottom = nil
end

-- 获取当前时间点
function LRUMgr:getNowTime()
    return os.time()
end

-- 获取缓存长度
function LRUMgr:getLength()
    return self.totLen
end

-- 创建一次数组返回（此方法有性能问题，甚用，仅用于查看顺序）
function LRUMgr:getList()
    if self.totLen == 0 then
        return {}
    end

    local ls = {}
    local cacheObj = self.top
    table.insert(ls,cacheObj.target)
    while cacheObj.next ~= nil do
        table.insert(ls,cacheObj.next.target)
        cacheObj = cacheObj.next
    end
    return ls
end

对象池的话也可以在这个的基础上封装，代码就懒得粘了。 

除了双链外我以前还搞过一种时间块三链的存储结构，性能效率也不错，不过算法有些复杂，也不知道是不是我独创，总之网是搜不到。思路是把缓存分时间块存取，例如十分钟内的缓存在第一块，十到二十分钟的缓存在第二块，类堆。每次访问缓存就把缓存对象放到最新的时间块，过期处理是把过期时间块里所有缓存对象清了，例如五十到六十分钟时间块过期了，就把时间块置空即可，时间块LRU的好处是十分钟内的缓存被访问是不需要进行上下节点处理的，而且清内存的时候不需要对多个对象进行置空清除，只需要对时间块清除即可。

具体做法是取当前时间戳除以一个时间段数值(例如十分钟是60*10)，取整数部份做为时间块的id，用这个id做为这个时间段的内存块加入链表头。每调用对象就把对象放到放到最新的时间块去。这个方法不是判断对象过期，而是判断时间块过期。时间块过期就把块id对应的对象置空。懒筋抽搐，改天有空再弄上来。