??集合、字典和散列表可以存儲不重復(fù)的值。在集合中，我們感興趣的是每個值本身，并把它當(dāng)作主要元素。在字典中，我們用[鍵，值]的形式來存儲數(shù)據(jù)。在散列表中也是一樣(也是以[鍵， 值]對的形式來存儲數(shù)據(jù))。但是兩種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方式略有不同。

字典
??集合表示一組互不相同的元素(不重復(fù)的元素)。在字典中，存儲的是[鍵，值] 對，其中鍵名是用來查詢特定元素的。字典和集合很相似，集合以[值，值]的形式存儲元素，字 典則是以[鍵，值]的形式來存儲元素，字典也稱作映射。
??我們用JS來實現(xiàn)字典：

function Dictionary() {
    let items = {}
    this.set = function (key, value) {
        items[key] = value
    }
    this.has = function (key) {
        return key in items
    }
    this.remove = function (key) {
        if (this.has(key)) {
            delete items[key]
            return true
        }
        return false
    }
    this.get = function (key) {
        return this.has(key) ? items[key] : undefined
    }
    this.values = function () {
        let values = []
        for (let k in items) {
            if (this.has(k)) {
                values.push(items[k])
            }
        }
        return values
    }
    this.clear = function () {
        items = []
    }
    this.size = function () {
        return Object.keys(items).length
    }
    this.keys = function () {
        return Object.keys(items)
    }
    this.getItems = function () {
        return items
    }
}
let dic = new Dictionary()
dic.set('name', 'hello')
dic.set('age', 22)
console.log(dic.has('name')) // true
dic.remove('age')
console.log(dic.values()) // [ 'hello' ]

散列表
??散列算法的作用是盡可能快地在數(shù)據(jù)結(jié)構(gòu)中找到一個值。在之前的章節(jié)中，我們已經(jīng)知道如果要在數(shù)據(jù)結(jié)構(gòu)中獲得一個值(使用get方法)，需要遍歷整個數(shù)據(jù)結(jié)構(gòu)來找到它。如果使用散列函數(shù)，就知道值的具體位置，因此能夠快速檢索到該值。散列函數(shù)的作用是給定一個鍵值，然后返回值在表中的地址。
??最常見的散列函數(shù)——“l(fā)ose lose”散列函數(shù)，方法是簡單地將每個鍵值中的每個字母的ASCII值相加。

??接下來我們用JS來實現(xiàn)散列表：

function HashMap() {
    let items = []
    let loseloseHashCode = function (key) {
        let hash = 0
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        // 為了得到比較小的數(shù)值，我們會使用hash值和一個任意 數(shù)做除法的余數(shù)(mod)。
        return hash % 37
    }
    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        console.log(position + '-' + key)
        items[position] = value
    }
    this.get = function (key) {
        return items[loseloseHashCode(key)]
    }
    this.remove = function (key) {
        // 對于HashMap類來說，我們不需要像ArrayList類一樣從items數(shù)組中將位置也移除。
        // 由于元素分布于整個數(shù)組范圍內(nèi)，一些位置會沒有任何元素占據(jù)，并默認(rèn)為undefined值。
        // 我們也不能將位置本身從數(shù)組中移除(這會改變其他元素的位置)，否則，當(dāng)下次需要獲得或移除一個 元素的時候，這個元素會不在我們用散列函數(shù)求出的位置上。
        items[loseloseHashCode(key)] = undefined
    }
}
let map = new HashMap()
map.put('name', 'hello') // 10-name
map.put('age', 22) // 5-age
console.log(map.get('name')) // hello
map.remove('name')
console.log(map.get('name')) // undefined
console.log(map.get('age')) // 22

處理散列表中的沖突
??有時候，一些鍵會有相同的散列值。不同的值在散列表中對應(yīng)相同位置的時候，我們稱其為沖突。例如，我們看看下面的代碼會得到怎樣的輸出結(jié)果:

var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com'); 10 hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jonathan', 'jonathan@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com');

19-Gandalf
29-John
16-Tyrion
16-Aaron
13-Donnie
13-Ana
5-Jonathan
5-Jamie
5-Sue
32-Mindy
32-Paul
10-Nathan

??在當(dāng)前的數(shù)據(jù)結(jié)構(gòu)中，對于發(fā)生沖突的元素來說，后者會覆蓋前者。使用一個數(shù)據(jù)結(jié)構(gòu)來保存數(shù)據(jù)的目的顯然不是去丟失這些數(shù)據(jù)，而是通過某種方法將它們?nèi)勘４嫫饋?。因此，?dāng)這種情況發(fā)生的時候就要去解決它。

分離鏈接
??分離鏈接法包括為散列表的每一個位置創(chuàng)建一個鏈表并將元素存儲在里面，它是解決沖突最簡單的方法。

??我們來實現(xiàn)一個使用了分離鏈接的HashMap實例，LinkedList類上篇文章已經(jīng)詳細(xì)解釋過了，這里直接引用。

function LinkedList() {

    // Node輔助類，表示要加入列表的項，element是即將添加到列表的值，next是指向列表中下一個節(jié)點項的指針
    let Node = function (element) {
        this.element = element
        this.next = null
    }

    let length = 0
    let head = null

    // 向鏈表尾部追加元素
    this.append = function (element) {
        let node = new Node(element)
        let current
        if (head === null) { // 列表中第一個節(jié)點
            head = node
        } else {
            current = head
            while (current.next) {
                current = current.next // 找到最后一項，是null
            }
            current.next = node // 給最后一項賦值
        }
        length++ // 更新列表的長度
    }

    // 從鏈表中移除指定位置元素
    this.removeAt = function (position) {
        if (position > -1 && position < length) { // 值沒有越界
            let current = head
            let previous, index = 0
            if (position === 0) { //  移除第一項
                head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next // 將previous與current的下一項連接起來，跳過current，從而移除
            }
            length-- // 更新列表的長度
            return current.element
        } else {
            return null
        }
    }

    // 在鏈表任意位置插入一個元素
    this.insert = function (position, element) {
        if (position >= 0 && position <= length) { // 檢查越界值
            let node = new Node(element),
                current = head,
                previous,
                index = 0
            if (position === 0) { // 在第一個位置添加
                node.next = current
                head = node
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                node.next = current // 在previous與current的下一項之間插入node
                previous.next = node
            }
            length++
            return true
        } else {
            return false
        }
    }

    // 把鏈表內(nèi)的值轉(zhuǎn)換成一個字符串
    this.toString = function () {
        let current = head,
            string = ''
        while (current) {
            string += current.element + ' '
            current = current.next
        }
        return string
    }

    // 在鏈表中查找元素并返回索引值
    this.indexOf = function (element) {
        let current = head,
            index = 0
        while (current) {
            if (element === current.element) {
                return index
            }
            index++
            current = current.next
        }
        return -1
    }

    // 從鏈表中移除指定元素
    this.remove = function (element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }

    this.isEmpty = function () {
        return length === 0
    }

    this.size = function () {
        return length
    }

    this.getHead = function () {
        return head
    }
}

function HashMap() {
    let items = []
    let ValuePair = function (key, value) { // 輔助類，表示將要加入LinkedList實例的元素。
        this.key = key
        this.value = value
        this.toString = function () {
            return '[' + this.key + '-' + this.value + ']'
        }
    }
    let loseloseHashCode = function (key) {
        let hash = 0
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        // 為了得到比較小的數(shù)值，我們會使用hash值和一個任意 數(shù)做除法的余數(shù)(mod)。
        return hash % 37
    }
    
    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        if (items[position] == undefined) {
            items[position] = new LinkedList() // 初始化一個LinkedList類的實例
        }
        items[position].append(new ValuePair(key, value)) // 在單鏈表中添加element
    }
    
    this.get = function (key) {
        let position = loseloseHashCode(key)
        if (items[position] !== undefined) {
            let current = items[position].getHead()
            while(current.next) { // 遍歷鏈表來尋找鍵/值
                if (current.element.key === key) {
                    return current.element.value
                }
                current = current.next
            }
            if (current.element.key === key) { // 檢查元素在鏈表第一個或最后一個節(jié)點的情況
                return current.element.value
            }
        }
        return undefined
    }
    
    this.remove = function (key) {
        let position = loseloseHashCode(key)
        if (items[position] !== undefined) {
            let current = items[position].getHead()
            while (current.next) {
                if (current.element.key === key) {
                    items[position].remove(current.element)
                    if (items[position].isEmpty()) {
                        items[position] = undefined
                    }
                    return true
                }
                current = current.next
            }
            if (current.element.key === key) {
                items[position].remove(current.element)
                if (items[position].isEmpty()) {
                    items[position] = undefined
                }
                return true
            }
        }
        return false
    },
        
    this.getItems = function () {
        return items
    }
}

let hash = new HashMap()
hash.put('Gandalf', 'gandalf@email.com')
hash.put('John', 'johnsnow@email.com')
hash.put('Tyrion', 'tyrion@email.com')
hash.put('Aaron', 'aaron@email.com')
hash.put('Donnie', 'donnie@email.com')
hash.put('Ana', 'ana@email.com')
hash.put('Jonathan', 'jonathan@email.com')
hash.put('Jamie', 'jamie@email.com')
hash.put('Sue', 'sue@email.com')
hash.put('Mindy', 'mindy@email.com')
hash.put('Paul', 'paul@email.com')
hash.put('Nathan', 'nathan@email.com')

線性查找
??另一種解決沖突的方法是線性探查。當(dāng)想向表中某個位置加入一個新元素的時候，如果索引 為index的位置已經(jīng)被占據(jù)了，就嘗試index+1的位置。如果index+1的位置也被占據(jù)了，就嘗試 index+2的位置，以此類推。

function HashMap() {

    let items = []
    let ValuePair = function (key, value) { // 輔助類，表示將要加入LinkedList實例的元素。
        this.key = key
        this.value = value
        this.toString = function () {
            return '[' + this.key + '-' + this.value + ']'
        }
    }

    let loseloseHashCode = function (key) {
        let hash = 0
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        // 為了得到比較小的數(shù)值，我們會使用hash值和一個任意 數(shù)做除法的余數(shù)(mod)。
        return hash % 37
    }

    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        if (items[position] == undefined) {
            items[position] = new ValuePair(key, value)
        } else {
            let index = ++position
            while (items[index] != undefined) {
                index++
            }
            items[index] = new ValuePair(key, value)
        }
    }

    this.get = function (key) {
        let position = loseloseHashCode(key)
        if (items[position] !== undefined) {
            if (items[position].key === key) {
                return items[position].value
            } else {
                let index = ++position
                while (items[index] === undefined || items[index].key !== key) {
                    index++
                }
                if(items[index].key === key) {
                    return items[index].value
                }
            }
        }
        return undefined
    }

    this.remove = function (key) {
        let position = loseloseHashCode(key)
        if (items[position] !== undefined) {
            if (items[position].key === key) {
                items[position] = undefined
            } else {
                let index = ++position
                while (items[index] === undefined || items[index].key !== key) {
                    index++
                }
                if(items[index].key === key) {
                    items[position] = undefined
                }
            }
        }
        return undefined
    }
}
let map = new HashMap()
map.put('name', 'hello') // 10-name
map.put('age', 22) // 5-age
console.log(map.get('name')) // hello
map.remove('name')
console.log(map.get('name')) // undefined
console.log(map.get('age')) // 22

創(chuàng)建更好的散列函數(shù)
??我們實現(xiàn)的“l(fā)ose lose”散列函數(shù)并不是一個表現(xiàn)良好的散列函數(shù)，因為它會產(chǎn)生太多的沖突。如果我們使用這個函數(shù)的話，會產(chǎn)生各種各樣的沖突。一個表現(xiàn)良好的散列函數(shù)是由幾個方面構(gòu)成的:插入和檢索元素的時間(即性能)，當(dāng)然也包括較低的沖突可能性。我們可以在網(wǎng)上找到一些不同的實現(xiàn)方法，或者也可以實現(xiàn)自己的散列函數(shù)。

 let djb2HashCode = function (key) {
        let hash = 5381; //{1}
        for (let i = 0; i < key.length; i++) { //{2}
            hash = hash * 33 + key.charCodeAt(i); //{3}
        }
        return hash % 1013; //{4}
    }

??它包括初始化一個hash變量并賦值為一個質(zhì)數(shù)，大多數(shù)實現(xiàn)都使用5381，然后迭代參數(shù)key，將hash與33相乘(用來當(dāng)作一個魔力數(shù))，并和當(dāng)前迭代到的字符的ASCII 碼值相加。最后，我們將使用相加的和與另一個隨機(jī)質(zhì)數(shù)(比我們認(rèn)為的散列表的大小要大——在本例 中，我們認(rèn)為散列表的大小為1000)相除的余數(shù)。
??這并不是最好的散列函數(shù)，但這是最受社區(qū)推崇的散列函數(shù)之一。