设计LFU缓存结构

双哈希表

func LFU(operators [][]int, k int) []int {
    lfuCache, ans := NewLFUCache(k), []int{}
    for _, item := range operators {
        switch item[0] {
        case 1:
            lfuCache.Set(item[1], item[2])
        case 2:
            ans = append(ans, lfuCache.Get(item[1]))
        }
    }
    return ans
}

type LFUNode struct {
    key   int
    value int
    times int
    prev  *LFUNode
    next  *LFUNode
}

type LFUCache struct {
    mapOne   map[int]*LFUNode
    mapTwo   map[int][2]*LFUNode
    cap      int
    len      int
    minTimes int
}

func NewLFUCache(capacity int) *LFUCache {
    return &LFUCache{
        mapOne:   map[int]*LFUNode{},
        mapTwo:   map[int][2]*LFUNode{},
        cap:      capacity,
        len:      0,
        minTimes: -1,
    }
}

func (lfu *LFUCache) Get(key int) int {
    node, ok := lfu.mapOne[key]
    if !ok {
        return -1
    }
    lfu.delete(node)
    node.times++
    lfu.insert(node)

    return node.value
}

func (lfu *LFUCache) Set(key, value int) {
    if node, ok := lfu.mapOne[key]; ok {
        lfu.delete(node)
        node.value = value
        node.times++
        lfu.insert(node)
    } else {
        if lfu.len == lfu.cap {
            headTail := lfu.mapTwo[lfu.minTimes]
            delete(lfu.mapOne, headTail[1].prev.key)
            lfu.delete(headTail[1].prev)
            lfu.len--
        }
        node := &LFUNode{key: key, value: value, times: 1}
        lfu.mapOne[key] = node
        lfu.insert(node)
        lfu.minTimes = 1
        lfu.len++
    }
}

func (lfu *LFUCache) delete(node *LFUNode) {
    headTail := lfu.mapTwo[node.times]
    if node.prev == headTail[0] && node.next == headTail[1] && node.times == lfu.minTimes {
        lfu.minTimes++
    }
    node.prev.next, node.next.prev = node.next, node.prev
}

func (lfu *LFUCache) insert(node *LFUNode) {
    if headTail, ok := lfu.mapTwo[node.times]; ok {
        head := headTail[0]
        head.next, node.prev, node.next, head.next.prev = node, head, head.next, node
    } else {
        head, tail := &LFUNode{}, &LFUNode{}
        head.next, tail.prev = tail, head
        lfu.mapTwo[node.times] = [2]*LFUNode{head, tail}
        head.next, node.prev, node.next, head.next.prev = node, head, head.next, node
    }
}

package main

/**
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LFU( operators [][]int ,  k int ) []int {
    // 参考：https://blog.csdn.net/helen920318/article/details/105324533
    result := make([]int, 0)
    s := Constructor(k)
    for _, v := range operators {
        if v[0] == 1 {
            s.Put(v[1], v[2])
        } else { //v[0] ==2
            result = append(result, s.Get(v[1]))
        }
    }
    return result
}

type LFUCache struct {
    cache map[int]*Node
    freq map[int]*DoubleList
    ncap,si***Freq int
}


func Constructor(capacity int) LFUCache {
    return LFUCache{
        cache:make(map[int]*Node),
        freq:make(map[int]*DoubleList),
        ncap:capacity,
    }
}


func (this *LFUCache) Get(key int) int {
    if node,ok := this.cache[key];ok {
        this.IncFreq(node)
        return node.val
    }
    return -1
}


func (this *LFUCache) Put(key int, value int)  {
    if this.ncap==0 {
        return
    }
    if node,ok := this.cache[key];ok {
        node.val = value
        this.IncFreq(node)
    } else {
        if this.size>=this.ncap {
            node := this.freq[this.minFreq].RemoveLast()
            delete(this.cache,node.key)
            this.size--
        }
        x := &Node{key:key,val:value,freq:1}
        this.cache[key] = x
        if this.freq[1] == nil {
            this.freq[1] = CreateDL()
        }
        this.freq[1].AddFirst(x)
        this.minFreq = 1
        this.size++
    }
}
//结点的频次增加
func (this *LFUCache) IncFreq(node *Node) {
    _freq := node.freq
    this.freq[_freq].Remove(node)
    if this.minFreq==_freq&&this.freq[_freq].IsEmpty() {
        this.minFreq++
        delete(this.freq,_freq)
    }

    node.freq++
    if this.freq[node.freq]==nil {
        this.freq[node.freq]=CreateDL()
    }
    this.freq[node.freq].AddFirst(node)
}
type DoubleList struct {
    head,tail *Node
}
type Node struct {
    prev,next *Node
    key,val,freq int
}
//新建双向链表
func CreateDL() *DoubleList {
    head,tail := &Node{},&Node{}
    head.next,tail.prev = tail,head
    return &DoubleList {
        head:head,
        tail:tail,
    }
}
func (this *DoubleList) AddFirst(node *Node) {
    node.next = this.head.next
    node.prev = this.head

    this.head.next.prev = node
    this.head.next = node
}

func (this *DoubleList) Remove (node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev

    node.next = nil
    node.prev = nil
}

func (this *DoubleList) RemoveLast() *Node {
    if this.IsEmpty() {
        return nil
    }

    last := this.tail.prev
    this.Remove(last)
    return last
}
func (this *DoubleList) IsEmpty() bool {
    return this.head.next==this.tail
}