# LRU: Least recently used，最近最少使用

【一般使用链表+map这两个数据结构来实现】

# 使用map来加快缓存数据的查找

# 使用链表来记录最近的访问情况，最近被访问了(Get和Put都属于是最近访问了)，就会被移到链表头

# 当Put进去的数据超过缓存容量时，链表尾部的元素就会被移出缓存

local LRUCache = {}
LRUCache.__index = LRUCache

function LRUCache.new(capacity)
    local obj = {}
    setmetatable(obj, LRUCache)
    obj:ctor(capacity)
    return obj
end

function LRUCache:ctor(capacity)
    self.capacity = capacity
    self.cache = {}
    self.list = LinkedList.new()
end

function LRUCache:Put(key, value)
    local node = self.cache[key]
    if nil == node then --缓存中没有
        node = self.list:AddFirst({k=key, v=value})
        self.cache[key] = node
        --如果超过了容量, 移除链表尾部元素
        if self.list:GetCount() > self.capacity then
            local nodeValue = self.list:RemoveLast():GetValue()
            self.cache[nodeValue.k] = nil
            --print(">capacity", nodeValue.k, nodeValue.v)
        end
    else --缓存中已经有了
        node:GetValue().v = value
        --最近被访问了, 放到链表最前面
        self.list:MoveToFirst(node)
    end
end

function LRUCache:Get(key)
    local node = self.cache[key]
    if nil == node then return nil end --缓存中没有
    self.list:MoveToFirst(node)
    return node:GetValue().v
end

function LRUCache:Remove(key)
    local node = self.cache[key]
    if nil == node then return end --缓存中没有
    self.cache[key] = nil
    self.list:MoveToFirst(node)
end

function LRUCache:Clear()
    self.cache = {}
    self.list:Clear()
end

【链表部分】

local Node = {}
Node.__index = Node

function Node.new(list, value)
    local obj = {}
    setmetatable(obj, Node)
    obj:ctor(list, value)
    return obj
end

function Node:ctor(list, value)
    self.list = list
    self.value = value
    self.next = nil
    self.prev = nil
end

function Node:SetValue(value)
    self.value = value
end
function Node:GetValue()
    return self.value
end

function Node:GetNext()
    return self.next
end
function Node:GetPrev()
    return self.prev
end

local LinkedList = {}
LinkedList.__index = LinkedList

function LinkedList.new()
    local obj = {}
    setmetatable(obj, LinkedList)
    obj:ctor()
    return obj
end

function LinkedList:ctor()
    self.head = nil
    self.tail = nil
    self.count = 0
end

function LinkedList:GetCount()
    return self.count
end

function LinkedList:Clear()
    if 0 == self.count then return end

    local allNodes = {}
    local node = self.head
    while nil ~= node do
        node.list = nil
        node.prev = nil
        local tempNext = node.next
        node.next = nil
        table.insert(allNodes, node)
        node = tempNext
    end
    self.head = nil
    self.tail = nil
    self.count = 0
    return allNodes --所有游离状nodes
end

function LinkedList:GetFirst()
    if 0 == self.count then return nil end
    return self.head
end
function LinkedList:GetFirstValue()
    if 0 == self.count then return nil end
    return self.head:GetValue()
end

function LinkedList:GetLast()
    if 0 == self.count then return nil end
    return self.tail
end
function LinkedList:GetLastValue()
    if 0 == self.count then return nil end
    return self.tail:GetValue()
end

function LinkedList:AddFirst(value)
    if 0 == self.count then
        self.count = 1
        self.head = Node.new(self, value)
        self.tail = self.head
        return self.head
    end
    self.count = self.count + 1
    local newHead = Node.new(self, value)
    newHead.next = self.head
    self.head.prev = newHead
    self.head = newHead
    return newHead
end

function LinkedList:AddLast(value)
    if 0 == self.count then
        self.count = 1
        self.head = Node.new(self, value)
        self.tail = self.head
        return self.head
    end
    self.count = self.count + 1
    local newTail = Node.new(self, value)
    newTail.prev = self.tail
    self.tail.next = newTail
    self.tail = newTail
    return newTail
end

---移动到链表头
function LinkedList:MoveToFirst(node)
    if node.list ~= self then return end
    if self.head == node then return end
    --断开原来的位置
    if self.tail == node then
        local newTail = node.prev
        newTail.next = nil --断开旧tail
        node.prev = nil --旧tail清除prev
        self.tail = newTail --设置新tail
    else
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = nil
    end

    --变成新的head
    node.next = self.head
    self.head.prev = node
    self.head = node
end

function LinkedList:RemoveFirst()
    if 0 == self.count then return nil end

    local ret = self.head
    if 1 == self.count then
        self.head = nil
        self.tail = nil
        self.count = 0
    else
        local newHead = self.head.next
        newHead.prev = nil --断开旧head
        self.head.next = nil--旧head清除next
        self.head = newHead --设置新head
        self.count = self.count - 1
    end
    ret.list = nil
    return ret
end

---移除链表尾
function LinkedList:RemoveLast()
    if 0 == self.count then return nil end

    local ret = self.tail
    if 1 == self.count then
        self.head = nil
        self.tail = nil
        self.count = 0
    else
        local newTail = self.tail.prev
        newTail.next = nil --断开旧tail
        self.tail.prev = nil --旧tail清除prev
        self.tail = newTail --设置新tail
        self.count = self.count - 1
    end
    ret.list = nil
    return ret
end

function LinkedList:Remove(node)
    if node.list ~= self then return end
    if self.head == node then
        self:RemoveFirst()
    elseif self.tail == node then
        self:RemoveLast()
    else
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = nil
        node.next = nil
        node.list = nil
    end
end

function LinkedList:__tostring()
    if 0 == self.count then return "" end

    local strTb = {}
    local node = self.head
    while nil ~= node do
        if nil == node.value then
            table.insert(strTb, "nil")
        else
            table.insert(strTb, tostring(node.value))
        end
        node = node.next
    end
    return table.concat(strTb, ",")
end

【参考】

LRU算法 - Yrion - 博客园 (cnblogs.com)