LRU Cache_leetcode_go实现一个LRU缓存，c

LRU Cache_leetcode_go实现一个LRU缓存，container/list.Remove()内存释放的坑，指针传递，container/list元素改值

题目：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

思路：

• 一道设计数据结构的题，不涉及算法，细节多。同时维护哈希表和链表保存数据。哈希实现快速查找，链表记录LRU。每次Put/Get都把节点挪到LRU链表的最后（先删后加）。
• 细节1:可选的面向对象编程，减少形参传递。
• 细节2:自己写双链表，或者用container/list。container/list本身就是双链表实现。root.prev指向尾节点，所以找头尾节点都不需要遍历。list.Front()，list.Back()执行时间均为O(1)。
• 细节3:cap指的是LRU容量，Get不需要修改，Put时超过容量，则踢除最少使用的节点。这也是用双链表的原因。
• 细节4:为什么map的v要用*list.Ellement。

错解（存在无法更新值的问题）：

type LRUCache struct {
    lru   *list.List
    store map[int]*list.Element
    cap   int
}

type LruKv struct {
    lruK int
    lruV int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        lru:   list.New(),
        store: make(map[int]*list.Element, capacity),
        cap:   capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    elem, ok := this.store[key]
    if !ok {
        return -1
    }

    //更新lru
    this.lru.Remove(elem) //map保存指针，方便删除
    node := elem.Value.(LruKv)
    this.lru.PushBack(LruKv{lruK: node.lruK, lruV: node.lruV,})
    
    return elem.Value.(LruKv).lruV
}

func (this *LRUCache) Put(key int, value int) {
    elem, ok := this.store[key]
    if ok {
        lruKvObj := elem.Value.(LruKv)
        lruKvObj.lruV = value //map的v存成指针，方便更新值
        this.lru.Remove(elem)
        this.lru.PushBack(elem.Value.(LruKv))
    } else {
        this.lru.PushBack(LruKv{lruK:key,lruV:value})
        lruKvObj := this.lru.Back()
        this.store[key] = lruKvObj
    }

    //处理cap
    if this.lru.Len() > this.cap {
        elem := this.lru.Front()
        node := elem.Value.(LruKv)
        delete(this.store, node.lruK)
        this.lru.Remove(elem)
    }
}

解决：要注意container/list中的elem.Value.(type)是值传递，而不是引用传递，无法改值。只重重建节点再插入。解决办法是改list.Element.Value的类型为*LruKv。

错解：（有一个关于container/list修改值的坑）

package main

import (
    "container/list"
)

type LRUCache struct {
    lru   *list.List
    store map[int]*list.Element
    cap   int
}

type LruKv struct {
    lruK int
    lruV int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        lru:   list.New(),
        store: make(map[int]*list.Element, capacity),
        cap:   capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    elem, ok := this.store[key]
    if !ok {
        return -1
    }

    //更新lru
    this.lru.Remove(elem) //map保存指针，方便删除
    node := elem.Value.(*LruKv)
    this.lru.PushBack(&LruKv{lruK: node.lruK, lruV: node.lruV,})

    return elem.Value.(*LruKv).lruV
}

func (this *LRUCache) Put(key int, value int) {
    elem, ok := this.store[key]
    if ok {
        lruKvObj := elem.Value.(*LruKv)
        lruKvObj.lruV = value //map的v存成指针，方便更新值
        this.lru.Remove(elem)
        this.lru.PushBack(lruKvObj)
    } else {
        this.lru.PushBack(&LruKv{lruK:key,lruV:value})
        lruKvObj := this.lru.Back()
        this.store[key] = lruKvObj
    }

    //处理cap
    if this.lru.Len() > this.cap {
        elem := this.lru.Front()
        node := elem.Value.(*LruKv)
        delete(this.store, node.lruK)
        this.lru.Remove(elem)
    }
}

问题分析：一个用container/list的坑，this.lru.Remove(e Element)。为避免内存泄露，释放了e的存储空间。实现为利用e的prev next指针进行删除。所以要求Element不仅要有Value，还要附带链表信息。
由于是引用传递，所以会清空map[]中的值。导致出现的问题是map[key]中的*Element仅有Value，没有链表信息。在插入重复元素时删除会失败。产生了冗余元素。

所以矛盾冲突在于list.Remove()方法的形参是引用传递，而本例实现map也是引用传递。在调用list.Remove()时，会析构形参*Element，影响其作为map的value被使用。影响的结果是清空了*Element所属的链表信息。进而导致更新value时，执行失败。元素个数多于预期。进而触发了扩容清理，从而导致逻辑错误。

解决：调用l.Remove()之后，更新map[]的对应值。

package main

import (
    "container/list"
    "fmt"
)

type LRUCache struct {
    lru   *list.List
    store map[int]*list.Element
    cap   int
}

type LruKv struct {
    lruK int
    lruV int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        lru:   list.New(),
        store: make(map[int]*list.Element, capacity),
        cap:   capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    elem, ok := this.store[key]
    if !ok {
        return -1
    }

    //更新lru
    this.lru.Remove(elem) //map保存指针，方便删除
    node := elem.Value.(*LruKv)
    this.lru.PushBack(&LruKv{lruK: node.lruK, lruV: node.lruV,})
    this.store[key] = this.lru.Back()

    return elem.Value.(*LruKv).lruV
}

func (this *LRUCache) Put(key int, value int) {
    elem, ok := this.store[key]
    if ok {
        lruKvObj := elem.Value.(*LruKv)
        lruKvObj.lruV = value //map的v存成指针，方便更新值
        this.lru.Remove(elem)
        this.lru.PushBack(lruKvObj)
        //特殊应对l.Remove()
        this.store[key] = this.lru.Back()
    } else {
        this.lru.PushBack(&LruKv{lruK:key,lruV:value})
        lruKvObj := this.lru.Back()
        this.store[key] = lruKvObj
    }

    //处理cap
    if this.lru.Len() > this.cap {
        elem := this.lru.Front()
        node := elem.Value.(*LruKv)
        delete(this.store, node.lruK)
        this.lru.Remove(elem)
    }
}

这个题测试输入太长，并且链表的变量跟踪进入的很深。调试了半天，所以mark一下Accepted。还有需要改进的地方。附注*Element存入map是指针，*Element.Value的值也是指针，才能实现改值。要不就要重新构建，并给map赋值。这也带了上述的问题。

Runtime: 176 ms, faster than 75.26% of Go online submissions for LRU Cache.

//TODO 需要做的优化，直接用双链表实现。container/list的Element很难用，编程变量都是一大串。还要做类型判断，简便地不要用.(type)，直接用.(LruKv)一行代码返回对象。