参考地址 LRU缓存的js实现
LRU缓存原理:
LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
实现
最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:
新数据插入到链表头部;
每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
当链表满的时候,将链表尾部的数据丢弃。
代码
function Node(value, next) { this.value = value; this.next = next; } function LRUCache(initialCapacity, initialValue) { this.size = 0; this.head = null; this.tail = null; this.capacity = initialCapacity; if (initialValue) { var key = Object.keys(initialValue)[0]; //Object.keys()方法会返回一个由一个给定对象的自身可枚举属性组成的数组,数组中属性名的排列顺序和使用 for...in 循环遍历该对象时返回的顺序一致 (两者的主要区别是 一个 for-in 循环还会枚举其原型链上的属性)。 var value = initialValue[key]; this.cache(key, value); } } //是否为空 LRUCache.prototype.isEmpty = function() { return this.head == null && this.tail == null; }; //在头部做添加 LRUCache.prototype.addFirst = function(obj) { var newNode = new Node(obj, null); if (this.isEmpty()) { this.head = this.tail = newNode; } else { this.head.next = newNode; this.head = newNode; //链表是反着的,head是最后一个节点 } this.size++; newNode = null; }; //在尾部做删除 LRUCache.prototype.removeLast = function() { if (!this.isEmpty()) { var key = Object.keys(this.tail.value)[0]; delete this[key]; this.tail = this.tail.next; if (this.tail == null) { this.head = null; } this.size--; } }; //将节点向头部移动 LRUCache.prototype.moveForward = function(key) { var node = this.search(key); if (node && node.next) { var next = node.next; var temp = node.value; node.value = next.value; next.value = temp; //位置交换了一下 } }; //缓存元素 LRUCache.prototype.cache = function(key, value) { //先查找是否已存在 var result = this.search(key); //已存在采取覆盖value策略 if (result) { result.value[key] = value; this[key] = value; } else { var obj = {}; obj[key] = value; this.addFirst(obj); var that = this; Object.defineProperty(this, key, { set : function(x) { that.moveForward(key); value = x; }, get : function() { that.moveForward(key); return value; }, configurable : true, enumerable : true }); //超出容量的话,将最少使用的删除 if (this.size > this.capacity) { this.removeLast(); } } //可以链式调用 return this; }; //删除元素 LRUCache.prototype.del = function(key) { if (this.search(key)) { var previous = null; var cur = this.tail; for (; cur; cur = cur.next) { if (cur.value.hasOwnProperty(key)) { break; } previous = cur; } if (previous) { if (previous.next) { //待定,感觉有点问题,删除的是目标值的后一个节点 previous.next = previous.next.next; this.size--; } } else { this.tail = this.tail.next; this.size--; } } if (this.hasOwnProperty(key)) { return (delete this[key]); } else { return (delete LRUCache.prototype[key]); } }; //查找元素 LRUCache.prototype.search = function(key) { for (var e = this.tail; e; e = e.next) { if (key in e.value) { return e; } } return null; }; 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
参考:
http://flychao88.iteye.com/blog/1977653
https://blog.csdn.net/esir82/article/details/72674274#commentBox