在JavaScript中,Map是一种数据结构,用于存储键值对的集合。如果要删除Map中最旧的条目,并且要求时间复杂度为O(1),可以使用以下方法:
以下是一个示例代码:
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = null;
this.tail = null;
}
get(key) {
if (this.map.has(key)) {
const node = this.map.get(key);
this.moveToHead(node);
return node.value;
}
return -1;
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this.moveToHead(node);
} else {
const newNode = { key, value, prev: null, next: null };
if (this.map.size >= this.capacity) {
this.removeTail();
}
this.addToHead(newNode);
this.map.set(key, newNode);
}
}
moveToHead(node) {
if (node === this.head) {
return;
}
if (node.prev) {
node.prev.next = node.next;
}
if (node.next) {
node.next.prev = node.prev;
}
if (node === this.tail) {
this.tail = node.prev;
}
node.prev = null;
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
}
removeTail() {
if (!this.tail) {
return;
}
this.map.delete(this.tail.key);
if (this.tail.prev) {
this.tail.prev.next = null;
} else {
this.head = null;
}
this.tail = this.tail.prev;
}
addToHead(node) {
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
if (!this.tail) {
this.tail = node;
}
}
}
const cache = new LRUCache(5);
cache.put("key1", "value1");
cache.put("key2", "value2");
cache.put("key3", "value3");
cache.put("key4", "value4");
cache.put("key5", "value5");
console.log(cache.get("key3")); // 输出:value3
console.log(cache.get("key1")); // 输出:value1
cache.put("key6", "value6"); // 删除最旧的条目
console.log(cache.get("key2")); // 输出:-1,已被删除
console.log(cache.get("key6")); // 输出:value6
在上述示例代码中,LRUCache类实现了一个基于LRU(最近最少使用)算法的缓存。LRUCache类使用了Map来存储键值对,并使用双向链表来维护键值对的顺序。通过在每个键值对中添加时间戳属性,并使用双向链表来维护顺序,可以实现删除最旧条目的O(1)时间复杂度。
腾讯云相关产品和产品介绍链接地址:
没有搜到相关的沙龙