首頁 >web前端 >js教程 >JavaScript中散列表(哈希表)的詳細介紹(程式碼範例)

JavaScript中散列表(哈希表)的詳細介紹(程式碼範例)

不言
不言轉載
2019-01-02 09:37:534484瀏覽

這篇文章帶給大家的內容是關於JavaScript中散列表(哈希表)的詳細介紹(程式碼範例),有一定的參考價值,有需要的朋友可以參考一下,希望對你有所幫助。

散列表

散列表(Hash table,也叫雜湊表),是根據鍵(Key)而直接存取在記憶體儲存位置的資料結構。也就是說,它透過計算一個關於鍵值的函數,將所需查詢的資料映射到表中一個位置來存取記錄,這加快了查找速度。這個映射函數稱做雜湊函數,存放記錄的數組稱為做散列表。

JavaScript中散列表(哈希表)的詳細介紹(程式碼範例)

我們從上圖開始分析

  • #有一個集合U,裡面分別是1000,10,152, 9733,1555,997,1168

  • #右邊是一個10個插槽的列表(散列表),我們需要把集合U中的整數存放到這個列表中

  • 怎麼存放,分別存在哪個槽裡?這個問題就是需要透過一個雜湊函數來解決了。我的存放方式是取10的餘數,我們對應這張圖來看

    • #1000 =0,10 =0 那麼1000和10這兩個整數就會被儲存到編號為0的這個槽中

    • #152 =2那麼就存放到2的槽中

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

透過上面簡單的例子,應該會有幾個大致的理解

  • #集合U,就是可能會出現在散列表中的鍵

  • #散列函數,就是你自己設計的一種如何將集合U中的鍵值透過某種計算存放到散列表中,如例子中的取餘數

  • 散列表,存放著通過計算後的鍵

那我們在接著看一般我們會怎麼去取值呢?

例如我們儲存一個key為1000,value為'張三' ---> {key:1000,value:'張三'}
從我們上述的解釋,它是不是應該存放在1000 的這個插槽。
當我們透過key想要找到value張三,是不是到key 這個插槽裡找就可以了呢?你到了這裡可以停下來思考一下。

散列的一些術語(可以簡單的看一下)

  • 散列列表中所有可能出現的鍵稱作全集U

  • #用M表示槽的數量

  • 給定一個鍵,由雜湊函數計算它應該出現在哪個槽中,上面例子的雜湊函數h=k% M,散列函數h就是鍵k到槽的一個映射。

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

看到這裡不知道你是否大致理解了雜湊函數是什麼了沒。透過例子,再透過你的思考,你可以回頭在讀一遍文章頭部關於散列表的定義。如果你能讀懂了,那我估計你應該是懂了。

常用的雜湊函數

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

處理字串:

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

hash演算法不是這裡的重點,我也沒有很深入的去研究,這裡主要還是去理解散列表是個怎樣的資料結構,它有哪些優點,它具體做了怎樣一件事。
而hash函數它只是透過某種演算法把key映射到列表中。

建構散列表

透過上面的解釋,我們在這裡做一個簡單的散列表

散列表的組成

  • M個槽

  • 有個hash函數

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

  • #有一個delete方法去做刪除

  • 有一個search方法,根據key去找到對應的值

初始化

- 初始化散列表有多少個槽
- 用一個陣列來建立M個槽

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

雜湊函數

處理字串的雜湊函數,這裡使用字串是因為,數值也可以傳換成字串比較通用一些

先將傳遞過來的key值轉為字串,為了能夠嚴謹一些

將字串轉換為數組, 例如'abc' => [...'abc'] => ['a','b','c']

分別對每個字元的charCodeAt進行計算,取M餘數是為了剛好對應插槽的數量,你總共就10個槽,你的數值 肯定會落到0-9的槽裡

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

加上

呼叫hash函數得到對應的儲存位址(就是我們之間類比的槽)

因為一個槽中可能會存多個值,所以需要用一個二維數組去表示,例如我們計算得來的槽的編號是0,也就是slot[0],那麼我們應該往slot[0] [0]裡存,後面進來的同樣是編號為0的槽的話就接著往slot[0] [1]裡存

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        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演算法找到對應的槽

用find函數去找同一個key的值

傳回對應的值

    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;    
    }

总结

讲到这里,散列表的数据结构已经讲完了,其实我们每学一种数据结构或算法的时候,不是去照搬实现的代码,我们要学到的是思想,比如说散列表它究竟做了什么,它是一种存储方式,可以快速的通过键去查找到对应的值。那么我们会思考,如果我们设计的槽少了,在同一个槽里存放了大量的数据,那么这个散列表它的搜索速度肯定是会大打折扣的,这种情况又应该用什么方式去解决,又或者是否用其他的数据结构的代替它。

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储,而arr = [] , arr[100000] = 10 这样的操作它是使用的散列,因为这种操作如果连续开辟100万个空间去存储一个值,那么显然是在浪费空间。


以上是JavaScript中散列表(哈希表)的詳細介紹(程式碼範例)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:segmentfault.com。如有侵權,請聯絡admin@php.cn刪除