您的当前位置：首页正文

[TypeScript]手撸LFU

来源：欧得旅游网

[TypeScript]手撸LFU

最近做笔试的时候遇到了要手撸LFU的题目，LFU在vue源码里还是有使用的，例如keep-alive的实现机制就是基于它来搞的。不多说了，直接上代码。

代码

// 双向链表node
class DoubleLinkNode {
    key: number;
    val: number;
    freq: number;
    prev?: DoubleLinkNode | null;
    next?: DoubleLinkNode | null;

    constructor(key, val, freq) {
        this.freq = freq;
        this.key = key;
        this.val = val;
    }
}

// 双向链表
class DoubleLink {
    size: number;
    head: DoubleLinkNode | null;
    tail: DoubleLinkNode | null;

    constructor() {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    // 删除一个节点
    remove(node: DoubleLinkNode) {
        // 空链表
        if (this.size < 1) {
            return;
        }

        // 只有一个元素
        if (this.size === 1) {
            this.size = 0;
            this.head = null;
            this.tail = null;
            return;
        }

        // 删的是头结点
        if (node === this.head) {
            const nextNode = node.next;
            nextNode.prev = null;
            this.head = nextNode;

            this.size--;
            return;
        }

        // 删的是尾结点
        if (node === this.tail) {
            const prevNode = node.prev;
            prevNode.next = null;
            this.tail = prevNode;
            this.size--;
            return;
        }

        // 正常删中间节点
        const prevNode = node.prev;
        const nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        this.size--;
    }

    // 在尾部插入一个节点
    addLast(node: DoubleLinkNode) {
        // 空链表
        if (this.size === 0) {
            this.head = node;
            this.tail = node;
        } else {
            // 非空链表
            const curTail = this.tail;
            curTail.next = node;
            node.prev = curTail;
            this.tail = node;
        }
        this.size++;
    }

    // 是否是空链表
    isEmpty() {
        return this.size === 0;
    }
}

// 实现LFU缓存
class LFUCache {
    keyToNodeMap: Map<number, DoubleLinkNode>;
    freqToKeysMap: Map<number, DoubleLink>;
    capacity: number;
    minFreq: number;

    constructor(capacity: number) {
        this.keyToNodeMap = new Map();
        this.freqToKeysMap = new Map();

        this.capacity = capacity;
        this.minFreq = 0;
    }

    get(key: number): number {
        if (!this.keyToNodeMap.has(key)) {
            return -1;
        }

        const node = this.keyToNodeMap.get(key);

        // 增加频次
        this.increaseFreq(node);

        return node.val;
    }

    put(key: number, value: number): void {
        // key已经存在
        if (this.keyToNodeMap.has(key)) {
            // 修改对应的node的val即可
            const node = this.keyToNodeMap.get(key);
            node.val = value;
            this.increaseFreq(node);
        } else {
            // key不存在
            // 容量满了
            if (this.keyToNodeMap.size >= this.capacity) {
                // 删除最小频次中最久没使用的
                this.removeMinFreqKey();
            }

            // ------------正式开始插入------------
            const newNode = new DoubleLinkNode(key, value, 1);
            this.keyToNodeMap.set(key, newNode);

            if (!this.freqToKeysMap.get(1)) {
                this.freqToKeysMap.set(1, new DoubleLink());
            }

            // 维护频次表
            const link = this.freqToKeysMap.get(1);
            link.addLast(newNode);

            // 插入新 key 后最小的 freq 肯定是 1
            this.minFreq = 1;
        }
    }

    // 增加频次
    increaseFreq(node: DoubleLinkNode) {
        const oldFreq = node.freq;
        const newFreq = node.freq + 1;
        node.freq = newFreq;

        // 维护频次表
        const oldFreqLink = this.freqToKeysMap.get(oldFreq);

        // 从旧频次表中删除这个node
        oldFreqLink.remove(node);
        if (oldFreqLink.isEmpty()) {
            this.freqToKeysMap.delete(oldFreq);

            // 如果这个频次正好是最低频次，记得更新最小频次
            if (this.minFreq === oldFreq) {
                this.minFreq = newFreq;
            }
        }

        // 维护新频次表
        if (!this.freqToKeysMap.get(newFreq)) {
            this.freqToKeysMap.set(newFreq, new DoubleLink());
        }
        const newFreqLink = this.freqToKeysMap.get(newFreq);
        newFreqLink.addLast(node);
    }

    // 删除最小频次中最久没使用的
    removeMinFreqKey() {
        const minFreqLink = this.freqToKeysMap.get(this.minFreq);

        // 其中最先被插入的那个 node 就是该被淘汰的 node
        const deletedNode = minFreqLink.head;

        // 维护最小频次map
        minFreqLink.remove(deletedNode);
        if (minFreqLink.isEmpty()) {
            this.freqToKeysMap.delete(this.minFreq);
        }

        // key表中删除对应Node
        this.keyToNodeMap.delete(deletedNode.key);
    }

    // log调试方法
    print() {
        console.log('keyToNodeMap: ', this.keyToNodeMap);
        console.log('freqToKeysMap: ', this.freqToKeysMap);
    }
}