js如何實(shí)現(xiàn)Map對象?

簡單寫一下Map對象的底層實(shí)現(xiàn)原來庵朝,包括常用的幾個(gè)方法:

size吗冤,set(),get()九府,delete()椎瘟,clear()

Map底層數(shù)據(jù)結(jié)構(gòu)是,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;
    // 根據(jù)key的不同的數(shù)據(jù)類型肺蔚,返回不同的index,其實(shí)就是決定放到bucket的那個(gè)鏈表上
    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];
    // 找到在鏈表上哪個(gè)位置
    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放到哪個(gè)鏈表上
    const i = this.hash(key);
    // 2儡羔、獲取當(dāng)前要存放的鏈表
    let target = this.bucket[i];
    // 放到鏈表上哪個(gè)位置
    while(target.next){
        // key已經(jīng)存在宣羊,直接修改
        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];
    // 防止刪除第一個(gè),設(shè)置虛擬頭
    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
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末汰蜘,一起剝皮案震驚了整個(gè)濱河市仇冯,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌鉴扫,老刑警劉巖赞枕,帶你破解...
    沈念sama閱讀 218,607評(píng)論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異坪创,居然都是意外死亡炕婶,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,239評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門莱预,熙熙樓的掌柜王于貴愁眉苦臉地迎上來柠掂,“玉大人,你說我怎么就攤上這事依沮⊙恼辏” “怎么了枪狂?”我有些...
    開封第一講書人閱讀 164,960評(píng)論 0 355
  • 文/不壞的土叔 我叫張陵,是天一觀的道長宋渔。 經(jīng)常有香客問我州疾,道長,這世上最難降的妖魔是什么皇拣? 我笑而不...
    開封第一講書人閱讀 58,750評(píng)論 1 294
  • 正文 為了忘掉前任严蓖,我火速辦了婚禮,結(jié)果婚禮上氧急,老公的妹妹穿的比我還像新娘颗胡。我一直安慰自己,他們只是感情好吩坝,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,764評(píng)論 6 392
  • 文/花漫 我一把揭開白布毒姨。 她就那樣靜靜地躺著,像睡著了一般钉寝。 火紅的嫁衣襯著肌膚如雪弧呐。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,604評(píng)論 1 305
  • 那天瘩蚪,我揣著相機(jī)與錄音泉懦,去河邊找鬼。 笑死疹瘦,一個(gè)胖子當(dāng)著我的面吹牛崩哩,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播言沐,決...
    沈念sama閱讀 40,347評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼邓嘹,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了险胰?” 一聲冷哼從身側(cè)響起汹押,我...
    開封第一講書人閱讀 39,253評(píng)論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎起便,沒想到半個(gè)月后棚贾,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,702評(píng)論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡榆综,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,893評(píng)論 3 336
  • 正文 我和宋清朗相戀三年妙痹,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片鼻疮。...
    茶點(diǎn)故事閱讀 40,015評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡怯伊,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出判沟,到底是詐尸還是另有隱情耿芹,我是刑警寧澤崭篡,帶...
    沈念sama閱讀 35,734評(píng)論 5 346
  • 正文 年R本政府宣布,位于F島的核電站吧秕,受9級(jí)特大地震影響琉闪,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜砸彬,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,352評(píng)論 3 330
  • 文/蒙蒙 一塘偎、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧拿霉,春花似錦、人聲如沸咱扣。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,934評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽闹伪。三九已至沪铭,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間偏瓤,已是汗流浹背杀怠。 一陣腳步聲響...
    開封第一講書人閱讀 33,052評(píng)論 1 270
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留厅克,地道東北人赔退。 一個(gè)月前我還...
    沈念sama閱讀 48,216評(píng)論 3 371
  • 正文 我出身青樓,卻偏偏與公主長得像证舟,于是被迫代替她去往敵國和親硕旗。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,969評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容