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

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

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

前言

比如，有一天，我們?nèi)ベ徫锏曩I了一件新的、不熟悉的商品。

張三：這個商品多少錢

收銀員：（在鍵盤上噼啪作響。。。）

收銀員：88元，給你湊個整。

（滴。。。付款成功）

成功支付90元。

hash表

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

有人說可以遍歷暴力查詢，總能找到項目。

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

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

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

我們想一個辦法把它變成一個數(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

這里我們計算出它對應的數(shù)字是609。

這里我們只是添加了字母對應的ascii下標。僅供參考和學習。一個好的哈希算法應該盡量避免下標過多和下標分散過大，還要處理和解決哈希沖突。

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

下次查詢香蕉的價格，還是可以通過 getHash 算出609，直接取數(shù)組的下標就可以得到我們的價格，只需要O(1)的時間。

實現(xiàn) get 功能

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

實現(xiàn) set 功能

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

做個測試

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

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

您可能感興趣的文章: