用javascript对象模拟LRUcache缓存池（百度2014校招前端笔试题）

LUR指的是内存管理中，淘汰页面时选择最近最久未使用的那个。

/* 利用数组模拟缓存池
 * 每个数组元素是一个对象，{k:v},k->key,v->value
 * key可看为是块号，value可看为是块中的内容
 * 块号可相同，但块中的内容则不一定相同
 */
		function LRUcache(size)
		{
			this.size = typeof size === "number" ? size : 0;
			if(this.size)
			{
				this.elements = new Array();
			}
		}
/*flag标记在缓存池中是否已存在与key值相同的块或页
 *flag = 0,不存在，flag = 1 存在
 */
		LRUcache.prototype.add = function(key,value){
			var i,
				flag = 0,
				len = this.elements.length,
				key = typeof key === "number" ? key : -1;
			if(key != -1)
			{
				for(i = 0;i < len; i++)
				{
					if(this.elements[i].k == key)
					{
						// 找到已存在的key值块或页，就从缓存池中去除
						// 简单的做法就是用后面的块覆盖它
						// 最后再将较新的块放在缓存池的顶部，即数组中的最后一个位置
						for(j = i ;j < len - 1; j++)
							this.elements[j] = this.elements[j + 1];
						this.elements[j] = {k:key,v:value};
						flag = 1;
					}
				}
				if(!flag)
				{
					// 如果此时缓存池已满且即将放入的块是新的，则队头出一项
					// 将新的块压入缓存池中
					if(len == this.size)
					{
						this.elements.shift();		
					}
					this.elements.push({k:key,v:value});	
				}
				return true;
			}
			return false;
		};
		LRUcache.prototype.get = function(key){
			var i,
				len = this.elements.length,
				key = typeof key == "number" ? key : -1;
			if(key != -1)
			{
				for(i = 0; i < len; i++)
				{
					if(this.elements[i].k == key)
					{
						var tmp = this.elements[i].v;
						
						for(j = i ;j < len - 1; j++)
						this.elements[j] = this.elements[j + 1];
					
						// 找到key块，并移动过元素后，将数组中多余的队尾元素弹出
						this.elements.pop();
						return tmp;
					}
				}
			}
			return -1;
		};
测试用例：
var l = new LRUcache(3);
		l.add(3,1);
		l.add(5,2);
		l.add(1,3);
		l.add(2,4);
		l.add(3,5);
		l.add(1,6);
		l.add(5,7);
		l.add("5",8);
		for(var i = 0, len = l.elements.length; i < len; i++)
			console.log(l.elements[i]);
		console.log(l.get(1));
		console.log(l.get("a"));
		console.log(l);

结果：

值得注意的点：

1. var test = [{“a”:1,”b”:”jack”}];，表示的是test为一个数组，数组中有一个元素，这个元素的类型为一个对象是{“a”:1,”b”:”jack”}.

2. var pp = {“element” : [1,2,3,4]},表示的是pp是一个对象，对象中有一个属性element,这个属性是一个数组，为[1,2,3,4],可以通过pp.element[0]…来访问数组其中的元素。

3. 读取对象属性时，如果对象内部的键值为字符串类型，比如”name”,那么可以test1.name,或者test1[“name”];

如果内部的键值为number类型，则只能是test1[1];

4. typeof 对象.属性，（属性就是那个键值），键值对应的值的类型是什么，typeof出来的就是什么。