共计 4270 个字符，预计需要花费 11 分钟才能阅读完成。
leetcode 中的一道题目：
设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和 写入数据 put。
获取数据 get(key) – 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) – 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache(2 /* 缓存容量 */);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4实现一
解题思路不多说了，主要是 hash 加双向链表，具体详见如下代码：
type node struct {
key int
value uint
pre *node
next *node
}
type LRUcache struct {
cap int
m map[int]*node
header *node
rear *node
}
func NewLRUcache(len int) *LRUcache {
if len <= 0 {return nil}
m := make(map[int]*node, len)
return &LRUcache{cap: len, m: m}
}
func (c *LRUcache) Get(key int) int {if v, ok := c.m[key]; ok {
//delete this node
if v.pre != nil {
v.pre.next = v.next
if v.next != nil {v.next.pre = v.pre} else {
// set new rear
c.rear = v.pre
}
//move to head
v.next = c.header
v.pre = nil
c.header.pre = v
c.header = v
}
//else do nothing
return int(v.value)
}
return -1
}
func (c *LRUcache) Put(key int, value uint) {
// modify
if v, ok := c.m[key]; ok {
//delete this node
if v.pre != nil {
v.pre.next = v.next
if v.next != nil {v.next.pre = v.pre} else {
// set new rear
c.rear = v.pre
}
//move to head
v.next = c.header
v.pre = nil
c.header.pre = v
c.header = v
}
//else do nothing
v.value = value
}
// check capacity before adding
if len(c.m) >= c.cap {
// remove the last
if c.rear != nil {
// header == rear while c.rear.pre == nil
if c.rear.pre != nil {
c.rear.pre.next = nil
delete(c.m, c.rear.key)
c.rear = c.rear.pre
} else {
c.rear = nil
c.header = nil
}
}
}
// add
if c.header == nil {c.header = &node{key: key, value: value}
c.rear = c.header
c.m[key] = c.header
} else {newnode := &node{key: key, value: value}
newnode.next = c.header
c.header.pre = newnode
c.header = newnode
c.m[key] = newnode
}
return
}调试代码：
func main() {obj := NewLRUcache(2)
if obj == nil {return}
fmt.Println("Set 1")
obj.Put(1, 1)
fmt.Println("Set 2")
obj.Put(2, 2)
fmt.Println("Get 1 return", obj.Get(1))
fmt.Println("Set 3")
obj.Put(3, 3)
fmt.Println("Get 2 return", obj.Get(2))
fmt.Println("Set 4")
obj.Put(4, 4)
fmt.Println("Get 1 return", obj.Get(1))
fmt.Println("Get 3 return", obj.Get(3))
fmt.Println("Get 4 return", obj.Get(4))
}输出：
Set 1
Set 2
Get 1 return 1
Set 3
Get 2 return -1
Set 4
Get 1 return -1
Get 3 return 3
Get 4 return 4 编码很容易，调试的时候倒是遇到了几个小问题，各种指针指来指去，很容易出错，还到处判断头指针是否是空，尾指针是否为空等等。。。
想起之前看过 Linux 大神 Linus Torvalds 的代码的品味问题，提到如何优雅的写链表，故重新优化如下：
实现二
直接上代码：
type node struct {
key int
value uint
pre *node
next *node
}
type LRUcache struct {
cap int
m map[int]*node
header *node
rear *node
}
func NewLRUcache(len int) *LRUcache {
if len <= 0 {return nil}
m := make(map[int]*node, len)
head := &node{}
tail := &node{}
head.next = tail
tail.pre = head
return &LRUcache{cap: len, m: m, header:head, rear:tail}
}
func (c *LRUcache) Get(key int) int {if v, ok := c.m[key]; ok {
//remove
v.pre.next = v.next
v.next.pre = v.pre
//add to head
v.pre = c.header
v.next = c.header.next
c.header.next.pre = v
c.header.next = v
return int(v.value)
}
return -1
}
func (c *LRUcache) Put(key int, value uint) {
// modify
if v, ok := c.m[key]; ok {
//remove
v.pre.next = v.next
v.next.pre = v.pre
//add to head
v.pre = c.header
v.next = c.header.next
c.header.next.pre = v
c.header.next = v
v.value = value
}
// check capacity before adding
if len(c.m) >= c.cap {
// remove the last
remove := c.rear.pre
remove.pre.next = remove.next
remove.next.pre = remove.pre
//delete from hash
delete(c.m, remove.key)
}
// add
newnode := &node{key: key, value: value}
c.header.next.pre = newnode
newnode.next = c.header.next
c.header.next = newnode
newnode.pre = c.header
c.m[key] = newnode
return
}再重新提取公共函数，进一步去优化：
type node struct {
key int
value uint
pre *node
next *node
}
type LRUcache struct {
cap int
m map[int]*node
header *node
rear *node
}
func NewLRUcache(len int) *LRUcache {
if len <= 0 {return nil}
m := make(map[int]*node, len)
head := &node{}
tail := &node{}
head.next = tail
tail.pre = head
return &LRUcache{cap: len, m: m, header:head, rear:tail}
}
func (c *LRUcache) moveToHeader(v *node) {
//remove
v.pre.next = v.next
v.next.pre = v.pre
//add to head
v.pre = c.header
v.next = c.header.next
c.header.next.pre = v
c.header.next = v
}
func (c *LRUcache) Get(key int) int {if v, ok := c.m[key]; ok {c.moveToHeader(v)
return int(v.value)
}
return -1
}
func (c *LRUcache) Put(key int, value uint) {
// modify
if v, ok := c.m[key]; ok {c.moveToHeader(v)
v.value = value
}
// check capacity before adding
if len(c.m) >= c.cap {
// remove the last
remove := c.rear.pre
remove.pre.next = remove.next
remove.next.pre = remove.pre
//delete from hash
delete(c.m, remove.key)
}
// add
newnode := &node{key: key, value: value}
c.header.next.pre = newnode
newnode.next = c.header.next
c.header.next = newnode
newnode.pre = c.header
c.m[key] = newnode
return
} 大功告成！！
从代码可以看到，在操作链表的时候已经不需要判断指针是否为空了，因为利用两个空节点来存储头和尾。
即链表变化为：
to
正文完
