关于lrucache:哈希表-leetcode-416-LRU缓存机制-512

题目

解题的关键在于
LRU 构造体和双向链表构造体的设计
以及双向链表的四个性能函数的拆分
这使得题解优雅而简洁

（想起来上学期苦楚的课程）

type LRUCache struct {
    size int
    capacity int
    cache map[int]*DLinkedNode
    head, tail *DLinkedNode
}

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

func initDLinkedNode(key, value int) *DLinkedNode {
    return &DLinkedNode{
        key: key,
        value: value,
    }
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{cache: map[int]*DLinkedNode{},
        head: initDLinkedNode(0, 0),
        tail: initDLinkedNode(0, 0),
        capacity: capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

//int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。// 对于 get 操作，首先判断 key 是否存在：// 如果 key 不存在，则返回 -1−1；// 如果 key 存在，则 key 对应的节点是最近被应用的节点。通过哈希表定位到该节点在双向链表中的地位，并将其挪动到双向链表的头部，最初返回该节点的值。func (this *LRUCache) Get(key int) int {if _, ok := this.cache[key]; !ok {return -1}
    node := this.cache[key]
    this.moveToHead(node)
    return node.value
}

//void put(int key, int value)如果关键字 key 曾经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该 逐出 最久未应用的关键字。// 对于 put 操作，首先判断 key 是否存在：// 如果 key 不存在，应用 key 和 value 创立一个新的节点，在双向链表的头部增加该节点，并将 key 和该节点增加进哈希表中。而后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；// 如果 key 存在，则与 get 操作相似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。func (this *LRUCache) Put(key int, value int)  {if _, ok := this.cache[key]; !ok {node := initDLinkedNode(key, value)
        this.cache[key] = node
        this.addToHead(node)
        this.size++
        if this.size > this.capacity {removed := this.removeTail()
            delete(this.cache, removed.key)
            this.size--
        }
    } else {node := this.cache[key]
        node.value = value
        this.moveToHead(node)
    }
}

func (this *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
}

func (this *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.tail.prev
    this.removeNode(node)
    return node
}