10月03, 2013

用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出来的就是什么。

版权声明:本文为博主原创文章,未经博主允许不得转载。

本文链接:https://imjiaolong.cn/post/6.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。