设计LFU缓存结构

利用两个hash就可以实现时间o(1)的操作，如果用js写的话，hash数据结构需要自己实现，如果是c++的话，有内置的数据结构，这里大致说一下思路：（推荐思路不清晰的可以看看leetcode的官方题解，写的非常明白清楚）

一个hash1记录相同操作频率的记录，记录通过双向循环链表记录，子所以使用双向循环链表，是为了实现删除第一个和最后一个链表元素的时间复杂度都为o(1)。

另外一个hash2记录key和此key在第一个hash中的链表地址。

get操作：查找hash2，如果没有则返回-1，如果有，则更新hash1中记录的频率，并返回val

set操作：查找hash2，如果没有则检查hash2是否超出了范围，如果没有超出范围则直接在hash1中添加记录，并将链表位置记录在hash1中，如果超出，则删除hash1中最低频率中最早被使用的(即链表尾的元素)，然后在将元素添加到hash1中对应频率的链表头；如果有，则改变频率

function LFU( operators , k ) {
    let obj = new F(k);
    const res = [];
    for (let v of operators) {
        if (v[0] === 1) {
            obj.set(v[1], v[2]);
        }else {
            res.push(obj.get(v[1]))
        }
    }
    return res;
}
class F{
    constructor(n) {
        this.hash1 = {};
        this.hash2 = {}; 
        this.size = n;
    }
    _update(p) {
        const fre = p.frequency + 1;
        const pre = p.pre;
        const next = p.next;
        pre.next = next;
        next.pre = pre;
        if (this.hash1[fre-1].next === this.hash1[fre-1].pre) {
            delete this.hash1[fre-1];
        }
        if (!this.hash1[fre]) {
            this._init(fre);
        }
        const h1 =  this.hash1[fre], h2 = h1.next;
        h1.next = p;
        p.next = h2;
        h2.pre = p;
        p.pre = h1;
    }
    _init(fre) {
        const p1 = {next: null, pre: null};
        const p2 = {next: null, pre: null};
        p1.next = p2;
        p2.next = p1;
        p1.pre= p2;
        p2.pre = p1;
        this.hash1[fre] = p1;
    }
    get(key) {
        const p = this.hash2[key];
        if (p) {
            this._update(p);
            return p.val
        }
        return -1;
    }
    set(key, value) {
        const p = this.hash2[key];
        if (p) {
            p.val = value;
            ++(p.frequency);
            this._update(p);
        } else {
            if (Object.keys(this.hash2).length >= this.size) {
                this.del();
            }
            if (!this.hash1[1]) {
                this._init(1);
            }
            const p = {next: null, pre: null, val: value, key, frequency: 1};
            const h1 = this.hash1[1], p1 = this.hash1[1].next;
            h1.next = p;
            p.next = p1;
            p1.pre = p;
            p.pre = h1;
            this.hash2[key] = p;
        };
    }
    del() {
        const min = Object.keys(this.hash1)[0];
        const h = this.hash1[min]
        const p1 = h.pre, p2 = p1.pre.pre;
        const key = p1.pre.key;
        p2.next = p1;
        p1.pre = p2;
        if (h.next === h.pre) {
            delete this.hash1[min];
        }
        delete this.hash2[key];
    }
}

class Node {
    constructor(key, value, freq) {
        this.key = key;
        this.value = value;
        this.freq = freq;
        this.prev = null;
        this.next = null;
    }
}

class DoubleList {
    constructor() {
        this.headNode = new Node();
		this.tailNode = new Node();
		this.headNode.next = this.tailNode;
		this.tailNode.prev = this.headNode;
    }
    isEmpty() {
		return this.headNode.next.next === null;
	}
    addFirst(node) {
		node.next = this.headNode.next;
		node.prev = this.headNode;
		this.headNode.next.prev = node;
		this.headNode.next = node;
	}
    remove(node) {
		node.next.prev = node.prev;
		node.prev.next = node.next;
	}
    peekLast() {
		return this.tailNode.prev;
	}
}

class LFUCache {
    constructor(k) {
        this.size = k;
        this.minFreq = 0;
        this.keyTable = new Map();
        this.freqTable = new Map();
    }
    get(key) {
        if (this.size <= 0 || !this.keyTable.has(key)) return -1;
        const node = this.keyTable.get(key);
        const { freq, value } = node;
        this.freqTable.get(freq).remove(node);
        if (this.freqTable.get(freq).isEmpty()) {
            if (this.minFreq === freq) this.minFreq++;
        }
        const newNode = new Node(key, value, freq + 1);
        const freqList = this.freqTable.get(newNode.freq);
        if (!freqList) {
            this.freqTable.set(newNode.freq, new DoubleList());
        }
        this.freqTable.get(newNode.freq).addFirst(newNode);
        this.keyTable.set(key, newNode);
        return value;
    }
    set(key, value) {
        if (this.size <= 0) return;
        if (this.keyTable.has(key)) {
            const node = this.keyTable.get(key);
            const { freq } = node;
            this.freqTable.get(freq).remove(node);
            if (this.freqTable.get(freq).isEmpty()) {
                if (this.minFreq === freq) this.minFreq++;
            }
            const newNode = new Node(key, value, freq + 1);
            const freqList = this.freqTable.get(newNode.freq);
            if (!freqList) {
                this.freqTable.set(newNode.freq, new DoubleList());
            }
            this.freqTable.get(newNode.freq).addFirst(newNode);
            this.keyTable.set(key, newNode);
        } else {
            const node = new Node(key, value, 1);
            if (this.size === this.keyTable.size) {
                const freqList = this.freqTable.get(this.minFreq);
                this.keyTable.delete(freqList.peekLast().key);
                freqList.remove(freqList.peekLast());
            }
            const freqList = this.freqTable.get(node.freq);
            if (!freqList) {
                this.freqTable.set(node.freq, new DoubleList());
            }
            this.freqTable.get(node.freq).addFirst(node);
            this.minFreq = 1;
            this.keyTable.set(key, node);
        }
    }
}

/**
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LFU( operators ,  k ) {
    const res = [];
    const lfu = new LFUCache(k);
    operators.forEach(op => {
        if (op[0] === 1) lfu.set(op[1], op[2]);
        else if (op[0] === 2) res.push(lfu.get(op[1]));
    });
    return res;
}