摘要：我經(jīng)常在業(yè)務(wù)代碼中把數(shù)據(jù)處理成這種字典的數(shù)據(jù)結(jié)構(gòu)獲取的方法哈希表在學(xué)習(xí)了類之后，我們會(huì)學(xué)習(xí)散列表，也就是哈希表。

集合、字典、散列表存儲(chǔ)的都是「不重復(fù)」的數(shù)據(jù)結(jié)構(gòu)

集合：我們更關(guān)注每一個(gè)元素的值，并把其作為主要元素

字典：我們用[鍵,值]的形式來存儲(chǔ)數(shù)據(jù)

散列表： 跟字典類似，也會(huì)是用[鍵,值]的形式來存儲(chǔ)數(shù)據(jù)

但是「字典」和「散列表」的實(shí)現(xiàn)方式略有不同。

字典也稱作映射。我覺得這種數(shù)據(jù)結(jié)構(gòu)，其實(shí)在業(yè)務(wù)代碼中的應(yīng)用很常見。

與Set類似，ES6同樣實(shí)現(xiàn)了一個(gè)Map類，即我們所說的字典

字典的大致骨架

    function Dictionary(){
        var items = {}
    }

    this.set = function(key,value){}
    this.get = function(key){}
    this.delete = function(key){}
    this.has = function(key){}
    this.clear = function(){}
    this.size = function(){}
    this.keys = function(){}  // 將字典所包含的所有鍵，以一個(gè)數(shù)組返回
    this.values = function(){}  // 將字典所包含的所有值，以一個(gè)數(shù)組返回

字典類的實(shí)現(xiàn)，十分簡(jiǎn)單就直接粘貼全部代碼了。

我覺得在JS中，對(duì)象本身就可以作為字典來使用。我經(jīng)常在業(yè)務(wù)代碼中把數(shù)據(jù)處理成這種字典的數(shù)據(jù)結(jié)構(gòu)

        function Dictionary() {
            var items = {}

            this.has = function ( key ) {
                return items.hasOwnProperty( key )
            }

            this.set = function ( key, value ) {
                items[ key ] = value
            }

            this.delete = function ( key ) {
                if ( this.has( key ) ) {
                    delete items[ key ]
                    return true
                }
                return false
            }

            this.get = function ( key ) {
                if ( this.has( key ) ) {
                    return items[ key ]
                } else {
                    return undefined
                }
            }

            this.values = function(){
                return Object.values(items)
            }

            this.keys = function(){
                return Object.keys(items)
            }

            this.clear = function(){
                this.items = {}
            }

            this.size = function(){
                return this.keys().length
            }

            this.getItems = function(){   // 獲取items的方法
                return items
            }
        }

        var dictionary = new Dictionary()

        dictionary.set("Gandalf","[email protected]")
        dictionary.set("John","[email protected]")
        dictionary.set("Tyrion","[email protected]")

        console.log(dictionary.has("Gandalf"))
        console.log(dictionary.size())
        console.log(dictionary.keys())
        console.log(dictionary.values())
        console.log(dictionary.get("Tyrion"))
        dictionary.delete("John")
        console.log(dictionary.keys())
        console.log(dictionary.values())
        console.log(dictionary.getItems())

在學(xué)習(xí)了Dictionary類之后，我們會(huì)學(xué)習(xí)散列表，也就是哈希表。它是Dictionary類的另外一種實(shí)現(xiàn)方式

我在讀到這里時(shí)，對(duì)于「字典」和「哈希表」2個(gè)慨念之間的區(qū)別還沒弄清，當(dāng)然書中也沒有太多解釋。

所以這里，我寫記錄一下自己查閱資料后的個(gè)人理解

「字典」指的是Key-Value這種存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)

那么哈希表也是字典，但是它是用另外的一種實(shí)現(xiàn)方式來做的。

那么我們我為什么要使用這種方式來實(shí)現(xiàn)「字典」呢，是不是字典存在某種缺點(diǎn)呢？

是的，比如說這樣的一組字典數(shù)據(jù)

k1, k2, k3, k4, k4 ....
v1, v2, v3, v4, v5 ....

當(dāng)你輸入key，命令電腦查詢key對(duì)應(yīng)的value時(shí)，電腦其實(shí)是沒法立刻找到key所對(duì)應(yīng)的value呢

看上去是直接根據(jù)key得到value，但實(shí)際上電腦還是需要遍歷k1、k2、k3去比較kn是否等于key。如果是的話就取出對(duì)應(yīng)的值

那么為了省去這個(gè)遍歷的過程，才想到用哈希表來實(shí)現(xiàn)「字典」

哈希表利用數(shù)組實(shí)現(xiàn)「字典」這種數(shù)據(jù)結(jié)構(gòu)，那么用數(shù)組來實(shí)現(xiàn)字典的話，用戶傳入的key對(duì)應(yīng)哪個(gè)索引呢？所以我們需要一個(gè)「散列算法」

「散列算法」，可以求出這個(gè)key在數(shù)組里對(duì)應(yīng)的位置，用哈希表實(shí)現(xiàn)的目的就是盡可能快地在字典中找到一個(gè)值。

function HashTable(){
    let table = []

    // 散列算法
    var loseloseHashCode = function(key){
        var hash = 0;
        for(var i = 0 ; i
哈希表的key值沖突
我們哈希表的散列算法，是為求出用戶傳入的key所對(duì)應(yīng)的一個(gè)索引
那么這個(gè)索引是有可能重復(fù)的，一旦重復(fù)就會(huì)導(dǎo)致后面的值覆蓋前面的值。
這種情況，叫做哈希表的沖突。所以我們了解2種處理沖突的方法原理

分離鏈接: 把數(shù)組的每一個(gè)元素都實(shí)例成鏈表結(jié)構(gòu)。這樣key相同的值，也可以用單鏈表的形式不斷存儲(chǔ)。不會(huì)覆蓋
線性探查: 當(dāng)用散列算法求出的這個(gè)索引index重復(fù)時(shí)，就index++，直到index不重復(fù)為止。

實(shí)現(xiàn)更好的散列函數(shù)
之前實(shí)現(xiàn)的"lose lose"散列函數(shù)，用來求值其實(shí)是非常容易產(chǎn)生key沖突的。
如果經(jīng)常沖突的話，那么插入和查詢一個(gè)元素的時(shí)間就會(huì)變慢(性能變差)
所以一個(gè)優(yōu)秀的散列算法，應(yīng)該是可以盡可能少出現(xiàn)沖突的
這里給出一個(gè)比較好的社區(qū)的實(shí)現(xiàn)。至于為什么這種算法,可以減少?zèng)_突我也不太理解，
可能是hash是質(zhì)數(shù)，然后質(zhì)數(shù)*33,最后在跟1013取模的話，不太會(huì)產(chǎn)生一樣的余數(shù)，這個(gè)感覺是數(shù)學(xué)問題。
var djb2HashCode = function(key){
    var hash = 5381

    for(var i = 0 ; i < key.length ; i++){
        hash = hash*33 + key.charCodeAt(i)
    }

    return hash % 1013
}

簡(jiǎn)單回顧一下，集合、字典、哈希表吧
首先他們的元素都是不重復(fù)的

集合： 是無序的，[value value]的形式的一組數(shù)據(jù)結(jié)構(gòu)
字典： 是由一對(duì)對(duì) [key-value] 組成的數(shù)據(jù)結(jié)構(gòu)
哈希表： 是字典的另外一種實(shí)現(xiàn)方式，優(yōu)點(diǎn)在于可能更快的根據(jù)key取到value

記錄一下書中沒搞清楚的小疑問：
《javascript數(shù)據(jù)結(jié)構(gòu)和算法》中多次提到「順序數(shù)據(jù)結(jié)構(gòu)」和「非順序數(shù)據(jù)結(jié)構(gòu)」的慨念，并表示

- 「順序數(shù)據(jù)結(jié)構(gòu)」：棧、隊(duì)列、數(shù)組、鏈表、集合
- 「非順序數(shù)據(jù)結(jié)構(gòu)」: 散列表 、 樹

可是我覺得鏈表、集合是無序的，數(shù)組是有序的呀

這個(gè)「順序數(shù)據(jù)結(jié)構(gòu)」似乎并不是指的在內(nèi)存中存儲(chǔ)形式。問題先記下，回頭再查把