JavaScript Map實(shí)現(xiàn)原理與底層結(jié)構(gòu)詳解

更新時(shí)間：2022年09月26日 11:15:37 作者：十九（一拖再拖）

哈希表（也稱(chēng)為哈希表）是一種基于鍵直接訪(fǎng)問(wèn)內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)計(jì)算一個(gè)鍵值函數(shù)來(lái)加速查找，該函數(shù)將要查詢(xún)的數(shù)據(jù)映射到表中的某個(gè)位置。該映射函數(shù)稱(chēng)為散列函數(shù)，記錄數(shù)組稱(chēng)為散列表

前言

比如，有一天，我們?nèi)ベ?gòu)物店買(mǎi)了一件新的、不熟悉的商品。

張三：這個(gè)商品多少錢(qián)

收銀員：（在鍵盤(pán)上噼啪作響。。。）

收銀員：88元，給你湊個(gè)整。

（滴。。。付款成功）

成功支付90元。

hash表

收銀員如何在數(shù)千件商品中如此迅速地找到這件商品的價(jià)格。

有人說(shuō)可以遍歷暴力查詢(xún)，總能找到項(xiàng)目。

如果有一百萬(wàn)種產(chǎn)品，需要多少時(shí)間？雖然始終可以從頭到尾查詢(xún)，但我們追求更好的性能，這就是我們的哈希表存儲(chǔ)。

我們需要做的就是將商品轉(zhuǎn)化為下標(biāo)形式的數(shù)字，并對(duì)應(yīng)數(shù)組的下標(biāo)，這樣下次遇到這個(gè)商品，就可以直接根據(jù)下標(biāo)獲取我們需要的信息了。

就像我們有一根香蕉?? banana（香蕉）

我們想一個(gè)辦法把它變成一個(gè)數(shù)字：

        function getHash(str) {
            let _hash = 0;
            for (let i = 0; i < str.length; i++) {
                const charCode = str.charCodeAt(i);
                _hash += charCode;
            }
            return _hash;
        }
        console.log(getHash('banana')) //609

這里我們計(jì)算出它對(duì)應(yīng)的數(shù)字是609。

這里我們只是添加了字母對(duì)應(yīng)的ascii下標(biāo)。僅供參考和學(xué)習(xí)。一個(gè)好的哈希算法應(yīng)該盡量避免下標(biāo)過(guò)多和下標(biāo)分散過(guò)大，還要處理和解決哈希沖突。

所以我們可以將數(shù)組下標(biāo)到位置 609 并添加價(jià)格，arr[609] = 66，這里設(shè)置66元。

下次查詢(xún)香蕉的價(jià)格，還是可以通過(guò) getHash 算出609，直接取數(shù)組的下標(biāo)就可以得到我們的價(jià)格，只需要O(1)的時(shí)間。

實(shí)現(xiàn) get 功能

        function get(key){
            let _hash = getHash(key);
            //這里的 arr 代表我們存儲(chǔ)數(shù)據(jù)的數(shù)組
            if(!this.arr[_hash]){
                //如果沒(méi)查到數(shù)據(jù)，返回undefined
                return undefined;
            }
            return this.arr[_hash];
        }

實(shí)現(xiàn) set 功能

        function set(key,value){
            let _hash = getHash(key);
            //這里的 arr 代表我們存儲(chǔ)數(shù)據(jù)的數(shù)組
            this.arr[_hash] = value;
        }

做個(gè)測(cè)試

        class MyHash {
            constructor(){
                this.arr = [];
            }
            get(key) {
                let _hash = getHash(key);
                //這里的 arr 代表我們存儲(chǔ)數(shù)據(jù)的數(shù)組
                if (!this.arr[_hash]) {
                    //如果沒(méi)查到數(shù)據(jù)，返回undefined
                    return undefined;
                }
                return this.arr[_hash];
            }
            set(key, value) {
                let _hash = getHash(key);
                //這里的 arr 代表我們存儲(chǔ)數(shù)據(jù)的數(shù)組
                this.arr[_hash] = value;
            }
        }
        let myhash = new MyHash();
        myhash.set('banana', '88')
        console.log(myhash.get('banana'))

到此這篇關(guān)于JavaScript Map實(shí)現(xiàn)原理與底層結(jié)構(gòu)詳解的文章就介紹到這了,更多相關(guān)JS Map內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: