JS实现字典与散列表

  集合、字典和散列表可以存储不重复的值。在集合中，我们感兴趣的是每个值本身，并把它当作主要元素。在字典中，我们用[键，值]的形式来存储数据。在散列表中也是一样(也是以[键， 值]对的形式来存储数据)。但是两种数据结构的实现方式略有不同。

字典
  集合表示一组互不相同的元素(不重复的元素)。在字典中，存储的是[键，值] 对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字 典则是以[键，值]的形式来存储元素，字典也称作映射。
  我们用JS来实现字典：

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' ]

散列表
  散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中，我们已经知道如果要在数据结构中获得一个值(使用get方法)，需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。
  最常见的散列函数——“lose lose”散列函数，方法是简单地将每个键值中的每个字母的ASCII值相加。

  接下来我们用JS来实现散列表：

function HashMap() {
    let items = []
    let loseloseHashCode = function (key) {
        let hash = 0
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        // 为了得到比较小的数值，我们会使用hash值和一个任意 数做除法的余数(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数组中将位置也移除。
        // 由于元素分布于整个数组范围内，一些位置会没有任何元素占据，并默认为undefined值。
        // 我们也不能将位置本身从数组中移除(这会改变其他元素的位置)，否则，当下次需要获得或移除一个 元素的时候，这个元素会不在我们用散列函数求出的位置上。
        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

处理散列表中的冲突
  有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。例如，我们看看下面的代码会得到怎样的输出结果:

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

  在当前的数据结构中，对于发生冲突的元素来说，后者会覆盖前者。使用一个数据结构来保存数据的目的显然不是去丢失这些数据，而是通过某种方法将它们全部保存起来。因此，当这种情况发生的时候就要去解决它。

分离链接
  分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面，它是解决冲突最简单的方法。

  我们来实现一个使用了分离链接的HashMap实例，LinkedList类上篇文章已经详细解释过了，这里直接引用。

function LinkedList() {

    // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针
    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) { // 列表中第一个节点
            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
        }
    }

    // 把链表内的值转换成一个字符串
    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)
        }
        // 为了得到比较小的数值，我们会使用hash值和一个任意 数做除法的余数(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) { // 检查元素在链表第一个或最后一个节点的情况
                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')

线性查找
  另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引 为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试 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)
        }
        // 为了得到比较小的数值，我们会使用hash值和一个任意 数做除法的余数(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

创建更好的散列函数
  我们实现的“lose lose”散列函数并不是一个表现良好的散列函数，因为它会产生太多的冲突。如果我们使用这个函数的话，会产生各种各样的冲突。一个表现良好的散列函数是由几个方面构成的:插入和检索元素的时间(即性能)，当然也包括较低的冲突可能性。我们可以在网上找到一些不同的实现方法，或者也可以实现自己的散列函数。

 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变量并赋值为一个质数，大多数实现都使用5381，然后迭代参数key，将hash与33相乘(用来当作一个魔力数)，并和当前迭代到的字符的ASCII 码值相加。最后，我们将使用相加的和与另一个随机质数(比我们认为的散列表的大小要大——在本例 中，我们认为散列表的大小为1000)相除的余数。
  这并不是最好的散列函数，但这是最受社区推崇的散列函数之一。