更快的取值方式之散列表

散列算法的作用是尽可能快的在数据结构中找到一个值。如果使用数组，或是链表的方式存取数据，要想查找一个特定的值，必须要遍历整个数据结构。但是，如果使用散列的方式，就相当于知道了这个值的位置，因此就可以轻松快速地获取该值。

在创建散列表之前，需要创建一个散列函数。散列函数的作用是给定一个键值，然后返回值在表中的地址。

const getHashCode = function (key) {
    let hash = 5381
    for (let i = 0, l = key.length; i < l; i++) {
        hash = hash * 33 + key.charCodeAt(i)
    }
    return hash % 1013
}

一个表现良好的散列函数由几个方面构成：插入和检索元素的时间，当然也要包括较低的散列冲突（也叫做散列碰撞）可能性，因为key值经过散列函数处理之后与散列的值并不是一一对应的，这就会出现多个key对应同一个地址，然后就出现了散列冲突。

为了解决散列冲突问题，常见的有：分离链接法、线性探查法等。

所谓分离链接法，就是在散列表的每一个位置创建一个链表，并将元素存储在里面。第一次存储时，计算的位置还没有值，那么就新创建一个链表，将值保存于链表中，再将链表存储到该位置。如果下次散列地址计算到了相同的位置，就在当前位置的链表中追加元素即可。

再一个是线性探查。当计算的位置已经有值时，则探查当前位置+1的位置是否有值，如果仍然有值，再探查+2的位置，以此往复，直到探查的位置无值，将值保存到探查到的位置。

以下代码基于线性探查实现：

let HashTable = (function () {
    const getHashCode = function (key) {
        let hash = 5381
        for (let i = 0, l = key.length; i < l; i++) {
            hash = hash * 33 + key.charCodeAt(i)
        }
        return hash % 1013
    }
    let items = []

    const ValuePair = class {
        constructor(key, value) {
            this.key = key
            this.value = value
        }

        toString() {
            return `[key:${this.key} value:${this.value}]`
        }
    }

    class HashTable {

        put(key, value) {
            let position = getHashCode(key);
            if (items[position] === undefined) {
                items[position] = new ValuePair(key, value)
            } else {
                let index = position
                while (++index) {
                    if (items[position] === undefined) {
                        items[position] = new ValuePair(key, value)
                        break;
                    }
                }
            }
        }

        remove(key) {
            let position = getHashCode(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[index] = undefined
                    }
                }
            }
        }

        get(key) {
            let position = getHashCode(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
                    }
                }
            } else {
                return undefined
            }
        }

        toString() {
            let str = ''
            for (let i = 0; i < items.length; i++) {
                if (items[i] !== undefined) {
                    str += items[i].toString() + "\r\n"
                }
            }
            return str
        }
    }

    return HashTable
}())

const hashTable = new HashTable()
hashTable.put('a', 'hello Jason')
hashTable.put('b', 'hello Mick')
console.log(hashTable.toString());
console.log(hashTable.get('a'));
hashTable.remove('a')
console.log(hashTable.toString());

// 输出：
// [key:a value:hello Jason]
// [key:b value:hello Mick]
//
// hello Jason
// [key:b value:hello Mick]