美文网首页
js如何实现Map对象?

js如何实现Map对象?

作者: _静夜听雨_ | 来源:发表于2021-12-05 10:16 被阅读0次

    简单写一下Map对象的底层实现原来,包括常用的几个方法:

    size,set(),get(),delete(),clear()

    Map底层数据结构是,hashMap,即哈希表或者散列表
    哈希表冲突解决方案采用拉链法

    function MyMap(){
        this.init();
    }
    MyMap.prototype.init = function(){
        this.size = 0;
        this.bucket = new Array(8);
        for(let i = 0; i < 8; i++){
            this.bucket[i] = {};
            this.bucket[i].next = null;
        }
    }
    MyMap.prototype.hash = function(key){
        let index = 0;
        // 根据key的不同的数据类型,返回不同的index,其实就是决定放到bucket的那个链表上
        if(typeof key === 'object'){
            index = 0;
        }else if(typeof key === 'number'){
            index = key % this.bucket.length;
        }else if(typeof key === 'undefined'){
            index = 1;
        }else if(typeof key === 'null'){
            index = 2;
        }else if(typeof key === 'string'){
            for(let i = 0; i < 10; i++){
                index += isNaN(key.charCodeAt(i)) ?  0 : key.charCodeAt(i);
            }
        }
        index = index % this.bucket.length;
        return index;
    }
    MyMap.prototype.get = function(key){
        const i = this.hash(key);
        let target = this.bucket[i];
        // 找到在链表上哪个位置
        while(target.next){
            if(target.next.key === key){
                return target.next.value;
            }
            target = target.next;
        }
        return undefined;
    }
    MyMap.prototype.set = function(key, value){
        // 1、决定key,value放到哪个链表上
        const i = this.hash(key);
        // 2、获取当前要存放的链表
        let target = this.bucket[i];
        // 放到链表上哪个位置
        while(target.next){
            // key已经存在,直接修改
            if(target.next.key === key){
                target.next.value = value;
                return this;
            }
            target = target.next;
        }
        target.next = {key, value, next : null}
        this.size++;
        return this;
    }
    MyMap.prototype.has = function(key){
        const i = this.hash(key);
        let target = this.bucket[i];
        while(target.next){
            if(target.next.key === key){
                return true;
            }
            target = target.next;
        }
        return false;
    }
    MyMap.prototype.clear = function(){
        this.init();
    }
    MyMap.prototype.delete = function(key){
        const i = this.hash(key);
        let target = this.bucket[i];
        // 防止删除第一个,设置虚拟头
        let front = {
            next: target
        };
        let cur = front;
        while(cur.next){
            if(cur.next.key === key){
                cur.next = cur.next.next;
                return true;
            }
            cur = cur.next;
        }
        return false
    }
    

    相关文章

      网友评论

          本文标题:js如何实现Map对象?

          本文链接:https://www.haomeiwen.com/subject/pvegxrtx.html