JavaScript中散列表是什么

小編給大家分享一下JavaScript中散列表是什么，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

散列表

我們從上圖開始分析

• 有一個集合U，里面分別是1000，10，152，9733，1555，997，1168

• 右側(cè)是一個10個插槽的列表（散列表），我們需要把集合U中的整數(shù)存放到這個列表中

• 怎么存放，分別存在哪個槽里？這個問題就是需要通過一個散列函數(shù)來解決了。我的存放方式是取10的余數(shù)，我們對應(yīng)這圖來看

• 1000%10=0，10%10=0 那么1000和10這兩個整數(shù)就會被存儲到編號為0的這個槽中

• 152%10=2那么就存放到2的槽中

• 9733%10=3 存放在編號為3的槽中

通過上面簡單的例子，應(yīng)該會有一下幾點一個大致的理解

• 集合U，就是可能會出現(xiàn)在散列表中的鍵

• 散列函數(shù)，就是你自己設(shè)計的一種如何將集合U中的鍵值通過某種計算存放到散列表中，如例子中的取余數(shù)

• 散列表，存放著通過計算后的鍵

那么我們在接著看一般我們會怎么去取值呢？

比如我們存儲一個key為1000，value為'張三' ---> {key:1000,value:'張三'}
從我們上述的解釋，它是不是應(yīng)該存放在1000%10的這個插槽里。
當我們通過key想要找到value張三，是不是到key%10這個插槽里找就可以了呢？到了這里你可以停下來思考一下。

散列的一些術(shù)語（可以簡單的看一下）

• 散列表中所有可能出現(xiàn)的鍵稱作全集U

• 用M表示槽的數(shù)量

• 給定一個鍵，由散列函數(shù)計算它應(yīng)該出現(xiàn)在哪個槽中，上面例子的散列函數(shù)h=k%M,散列函數(shù)h就是鍵k到槽的一個映射。

• 1000和10都被存到了編號0的這個槽中，這種情況稱之為碰撞。

看到這里不知道你是否大致理解了散列函數(shù)是什么了沒。通過例子，再通過你的思考，你可以回頭在讀一遍文章頭部關(guān)于散列表的定義。如果你能讀懂了，那么我估計你應(yīng)該是懂了。

常用的散列函數(shù)

處理整數(shù) h=>k%M （也就是我們上面所舉的例子）

處理字符串：

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

hash算法不是這里的重點，我也沒有很深入的去研究，這里主要還是去理解散列表是個怎樣的數(shù)據(jù)結(jié)構(gòu)，它有哪些優(yōu)點，它具體做了怎樣一件事。
而hash函數(shù)它只是通過某種算法把key映射到列表中。

構(gòu)建散列表

通過上面的解釋，我們這里做一個簡單的散列表

散列表的組成

• M個槽

• 有個hash函數(shù)

• 有一個add方法去把鍵值添加到散列表中

• 有一個delete方法去做刪除

• 有一個search方法，根據(jù)key去找到對應(yīng)的值

初始化

- 初始化散列表有多少個槽
- 用一個數(shù)組來創(chuàng)建M個槽

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

散列函數(shù)

處理字符串的散列函數(shù)，這里使用字符串是因為，數(shù)值也可以傳換成字符串比較通用一些

先將傳遞過來的key值轉(zhuǎn)為字符串，為了能夠嚴謹一些

將字符串轉(zhuǎn)換為數(shù)組, 例如'abc' => [...'abc'] => ['a','b','c']

分別對每個字符的charCodeAt進行計算，取M余數(shù)是為了剛好對應(yīng)插槽的數(shù)量，你總共就10個槽,你的數(shù)值%10 肯定會落到 0-9的槽里

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

添加

調(diào)用hash函數(shù)得到對應(yīng)的存儲地址(就是我們之間類比的槽)

因為一個槽中可能會存多個值，所以需要用一個二維數(shù)組去表示，比如我們計算得來的槽的編號是0，也就是slot[0]，那么我們應(yīng)該往slot[0] [0]里存，后面進來的同樣是編號為0的槽的話就接著往slot[0] [1]里存

    add(key,value) {
        const h = this.h(key);
        // 判斷這個槽是否是一個二維數(shù)組, 不是則創(chuàng)建二維數(shù)組
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 將值添加到對應(yīng)的槽中
        this.slots[h].push(value);
    }

刪除

通過hash算法,找到所在的槽

通過過濾來刪除

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }

查找

通過hash算法找到對應(yīng)的槽

用find函數(shù)去找同一個key的值

返回對應(yīng)的值

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

總結(jié)

講到這里，散列表的數(shù)據(jù)結(jié)構(gòu)已經(jīng)講完了，其實我們每學(xué)一種數(shù)據(jù)結(jié)構(gòu)或算法的時候，不是去照搬實現(xiàn)的代碼，我們要學(xué)到的是思想，比如說散列表它究竟做了什么，它是一種存儲方式，可以快速的通過鍵去查找到對應(yīng)的值。那么我們會思考，如果我們設(shè)計的槽少了，在同一個槽里存放了大量的數(shù)據(jù)，那么這個散列表它的搜索速度肯定是會大打折扣的，這種情況又應(yīng)該用什么方式去解決，又或者是否用其他的數(shù)據(jù)結(jié)構(gòu)的代替它。

補充一個小知識點

v8引擎中的數(shù)組 arr = [1,2,3,4,5] 或 new Array(100) 我們都知道它是開辟了一塊連續(xù)的空間去存儲，而arr = [] , arr[100000] = 10 這樣的操作它是使用的散列，因為這種操作如果連續(xù)開辟100萬個空間去存儲一個值，那么顯然是在浪費空間。

看完了這篇文章，相信你對JavaScript中散列表是什么有了一定的了解，想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！