what's LRU?

LRU，百度或者谷歌一下，就可以，大概是一种缓存的算法，你最近存过或者取过的值，就排序在最新，当你的数据存储达到最大值得时候，就要删掉最不常用的那些数据。

前几天电话面，面试官问了我一个问题：LocalStorage等缓存是有大小限制的，那么如果去限制存储的数据呢，我就想到了LRU，正好最近准备学习一下，就写一篇博客记录一下。

LRU缓存在力扣中也有一题。昨天晚上刷了一下，发现其实有简单的解法，就是有一点hack.

首先，按照正统的解法，是采用一个哈希表和一个双向链表来实现的。

但是，我们可以根据，对象的key迭代顺序来想一个解法。

我们可以知道，使用Object.keys的时候，对象的key的顺序首先是将所有为int型的key按顺序打印出来，再按照其他key的创建顺序打印，那么，创建顺序，其实我们可以想象一下， 最早创建的，其实就是最不常用的 我们只需要迭代，然后删除第一个key，然后将新的key再放入对象或者Map中。并且在get的时候也删除该key，然后重新set一下即可。那么，代码可以写成以下这种形式

class LRUCache {
constructor(size) {
this.size = size;
this.map = new Map();
}

get(key) {
let value;
if (this.map.has(key)) {
value = this.map.get(key);
this.put(key, value);
} else {
value = -1;
}
return value;
};

put(key, value) {
if (this.map.has(key)) {
this.map.delete(key);
this.map.set(key, value);
return;
}
if (this.map.size >= this.size) {
const firstKey= this.map.keys().next().value;
this.map.delete(firstKey);
}
this.map.set(key, value);
}
}

利用这一特性，实现了一个LRU缓存的结构。

待补充。。。