? ? 本文主要介紹了Nodejs基于LRU算法實現(xiàn)的緩存處理操作,結(jié)合具體實例形式分析了LRU算法的原理眨攘、功能以及nodejs使用LRU算法實現(xiàn)緩存處理操作的相關(guān)實現(xiàn)技巧,需要的朋友可以參考下：
? ? 本文實例講述了Nodejs基于LRU算法實現(xiàn)的緩存處理操作。分享給大家供大家參考返帕，具體如下：
? ? LRU是Least Recently Used的縮寫替梨，即最近最少使用頁面置換算法，是為虛擬頁式存儲管理服務(wù)的芽卿，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策了双吆。由于無法預(yù)測各頁面將來的使用情況在塔，只能利用“最近的過去”作為“最近的將來”的近似幻件，因此，LRU算法就是將最近最久未使用的頁面予以淘汰蛔溃。
? ? 可以用一個特殊的棧來保存當前正在使用的各個頁面的頁面號绰沥。當一個新的進程訪問某頁面時篱蝇，便將該頁面號壓入棧頂，其他的頁面號往棧底移徽曲，如果內(nèi)存不夠零截，則將棧底的頁面號移除。這樣秃臣，棧頂始終是最新被訪問的頁面的編號涧衙，而棧底則是最近最久未訪問的頁面的頁面號。
如輸入以下序列時：4,7,0,7,1,0,1,2,1,2,6
結(jié)果為：
4
4? ? ? ? 7
4? ? ? ? 7? ? ? ? 0
4? ? ? ? 0? ? ? ? 7
4? ? ? ? 0? ? ? ? 7? ? ? ? 1
4? ? ? ? 7? ? ? ? 1? ? ? ? 0
4? ? ? ? 7? ? ? ? 0? ? ? ? 1
4? ? ? ? 7? ? ? ? 0? ? ? ? 1? ? ? ? 2
4? ? ? ? 7? ? ? ? 0? ? ? ? 2? ? ? ? 1
4? ? ? ? 7? ? ? ? 0? ? ? ? 1? ? ? ? 2
7? ? ? ? 0? ? ? ? 1? ? ? ? 2? ? ? ? 6
適用于Node.js的一個LRU緩存奥此，capacity為緩存容量弧哎，為0時構(gòu)造一般緩存。
```
function CacheLRU(capacity) {
/* 利用Buffer寫的一個LRU緩存稚虎，capacity為緩存容量撤嫩，為0時不限容量。
myCache = new CacheLRU(capacity); //構(gòu)造緩存
myCache.get(key); //讀取名為key的緩存值
myCache.put(key, value); //寫入名為key的緩存值
myCache.remove(key); //刪除名為key的緩存值
myCache.removeAll(); //清空緩存
myCache.info(); //返回myCache緩存信息
LRU原理：對所有緩存數(shù)據(jù)的key構(gòu)建hash鏈表蠢终，當對某一數(shù)據(jù)進行g(shù)et或put操作時序攘，將其key提到鏈表前端（最新）。當進行put數(shù)據(jù)超出容量時寻拂，刪除鏈表尾端（最舊）的緩存數(shù)據(jù)程奠。
hash鏈表操作可直接定位key，無需歷遍整個hash對象祭钉，故讀寫極快瞄沙。緩存容量不再影響讀寫速度。
*/
? this.capacity = capacity || Number.MAX_VALUE;
? this.data = {};
? this.hash = {};
? this.linkedList = {
? ? length: 0,
? ? head: null,
? ? end: null
? }
? if (capacity <= 0) this.capacity = Number.MAX_VALUE;
};
CacheLRU.prototype.get = function(key) {
? key = '_' + key;
? var lruEntry = this.hash[key];
? if (!lruEntry) return;
? refresh(this.linkedList, lruEntry);
? return JSON.parse(this.data[key].toString());
};
CacheLRU.prototype.put = function(key, value) {
? key = '_' + key;
? var lruEntry = this.hash[key];
? if (value === undefined) return this;
? if (!lruEntry) {
? ? this.hash[key] = {key: key};
? ? this.linkedList.length += 1;
? ? lruEntry = this.hash[key];
? }
? refresh(this.linkedList, lruEntry);
? this.data[key] = new Buffer(JSON.stringify(value));
? if (this.linkedList.length > this.capacity) this.remove(this.linkedList.end.key.slice(1));
? return this;
};
CacheLRU.prototype.remove = function(key) {
? key = '_' + key;
? var lruEntry = this.hash[key];
? if (!lruEntry) return this;
? if (lruEntry === this.linkedList.head) this.linkedList.head = lruEntry.p;
? if (lruEntry === this.linkedList.end) this.linkedList.end = lruEntry.n;
? link(lruEntry.n, lruEntry.p);
? delete this.hash[key];
? delete this.data[key];
? this.linkedList.length -= 1;
? return this;
};
CacheLRU.prototype.removeAll = function() {
? this.data = {};
? this.hash = {};
? this.linkedList = {
? ? length: 0,
? ? head: null,
? ? end: null
? }
? return this;
};
CacheLRU.prototype.info = function() {
? var size = 0,
? ? data = this.linkedList.head;
? while (data){
? ? size += this.data[data.key].length;
? ? data = data.p;
? }
? return {
? ? capacity: this.capacity,
? ? length: this.linkedList.length,
? ? size: size
? };
};
// 更新鏈表朴皆，把get或put方法操作的key提到鏈表head，即表示最新
function refresh(linkedList, entry) {
? if (entry != linkedList.head) {
? ? if (!linkedList.end) {
? ? ? linkedList.end = entry;
? ? } else if (linkedList.end == entry) {
? ? ? linkedList.end = entry.n;
? ? }
? ? link(entry.n, entry.p);
? ? link(entry, linkedList.head);
? ? linkedList.head = entry;
? ? linkedList.head.n = null;
? }
}
// 對兩個鏈表對象建立鏈接泛粹，形成一條鏈
function link(nextEntry, prevEntry) {
? if (nextEntry != prevEntry) {
? ? if (nextEntry) nextEntry.p = prevEntry;
? ? if (prevEntry) prevEntry.n = nextEntry;
? }
}
module.exports = CacheLRU;
// test:
/*var user = new CacheLRU(5);
user.put('user1', {name:'admin', age: 30});
user.put('user2', {name:'user', age: 31});
user.put('user3', {name:'guest', age: 32});
user.put('user4', {name:'guest', age: 34});
user.put('user5', {name:'guest', age: 35});
console.log(user.get('user1'));
console.log(user.get('user2'));
console.log(user.get('user3'));
user.put('user6', {name:'guest', age: 36});
console.log(user.info());*/
```
? ? LRU算法也可以用于一些實際的應(yīng)用中遂铡，如你要做一個瀏覽器，或類似于淘寶客戶端的應(yīng)用的就要用到這個原理晶姊。大家都知道瀏覽器在瀏覽網(wǎng)頁的時候會把下載的圖片臨時保存在本機的一個文件夾里扒接，下次再訪問時就會，直接從本機臨時文件夾里讀取们衙。但保存圖片的臨時文件夾是有一定容量限制的钾怔，如果你瀏覽的網(wǎng)頁太多，就會一些你最不常使用的圖像刪除掉蒙挑，只保留最近最久使用的一些圖片宗侦。這時就可以用到LRU算法 了，這時上面算法里的這個特殊的棧就不是保存頁面的序號了忆蚀，而是每個圖片的序號或大蟹姑裂；所以上面這個棧的元素都用Object類來表示，這樣的話這個棧就可以保存的對像了男旗。
