实现LRU缓存算法

发布于2024年2月19日 17:09:10

LRU缓存算法

LRU 的全称是Least Recently Used, 即最久未使用的,属于典型的内存管理算法。

实现思路

因缓存空间是有限的,最近使用的放在最前,最久未使用的放在最后。当缓存空间已满时,新增一条数据时,需删除最后一条。每次取用缓存数据时,都需要更新一次排序。

示例代码

class LRUCache {
    #map;
    #length;
    constructor(len = 10) {
        this.#map = new Map();
        this.#length = len;
    }

    has(key) {
        return this.#map.has(key);
    }
    get(key) {
        if (!this.has(key)) return null;
        const value = this.#map.get(key);
        // 更新排序,使最近使用的排序最前
        this.#map.delete(key);
        this.#map.set(key, value);
        return value;
    }
    set(key, value) {
        if (this.has(key)) {
            this.#map.delete(key);
        }
        this.#map.set(key, value);
        // 如果超过最大长度,删除最后一项
        if (this.#map.size > this.#length) {
            this.#map.delete(this.#map.keys().next().value)
        }
    }
}

应用场景

  • 一般的缓存服务,memcache/redis之类
  • 部分业务场景

本文共 3 个回复

发表评论