学习JavaScript数据结构与算法 — 散列表

摘要：定义散列表是字典键值对的一种实现方式。根据键值从散列表中移除值。分离链接分离链接法在散列表的每一个位置创建一个链表并将元素存储在里面。一个表现良好的散列函数应该有较好的插入和查找性能且有较低的冲突可能性。

散列表是字典（键、值对）的一种实现方式。每次在字典中获取一个值，都需要重复遍历字典，如果用散列表，字典中的每个key都对应一个确定的位置，从而不再需要遍历。
以电子邮件地址簿为例，每个名字（key）对应一个邮件地址，用散列函数计算每个key在散列表中的位置（这里使用key的所有字符的ASCII码值相加），如图：

put(key,value)：向散列表增加一个新的项（也能更新散列表）。

remove(key)：根据键值从散列表中移除值。

get(key)：返回根据键值检索到的特定的值。

function HashTable() {
    // 私有变量table，作为散列表的载体
    var table = [];
    // 散列函数，计算key对应的hash值
    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i); // 所有字符的ASCII码值相加
        }
        // 为了将hash值变为更小的值，除以一个数并取余数
        // 这里除以素数37是为了降低计算出重复hash的概率（后续会处理hash重复的问题）
        return hash % 37;
    };
    // put方法，向散列表增加一个新的项（也能更新散列表）
    this.put = function(key, value) {
        var position = loseloseHashCode(key); // 计算key的hash值作为当前数据在散列表中的位置
        table[position] = value; // 将当前数据插入散列表
    };
    // get方法，返回根据键值检索到的特定的值
    this.get = function (key) {
        return table[loseloseHashCode(key)]; //根据key计算出的hash取对应位置中的值
    };
    // remove方法，根据键值从散列表中移除值
    this.remove = function(key) {
        table[loseloseHashCode(key)] = undefined;
    };
}

到这里，一个基本的的散列表已经实现了，但没有考虑散列函数计算出重复hash值的问题，这会导致后添加的数据覆盖先添加的数据，比如：

var table = new HashTable();
// Jamie和Sue的hash值都为5，因此Sue的数据会覆盖Jamie的数据
table.put("Jamie", "Jamie@qq.com");
table.put("Sue", "Sue@gmail.com");

处理上述冲突的方式主要有：分离链接、线性探查，双散列法，这里使用前两种。

分离链接法在散列表的每一个位置创建一个链表并将元素存储在里面。它的缺点是在HashTable实例之外还需要额外的存储空间。如图，散列表的每一个位置都是一个链表，链表里可以存储多个数据。

下面，重写put、get、remove方法，实现散列表的分离链接（其中链表类的实现参照链表）。

    // 首先要添加一个新的辅助类来实例化添加到链表的元素
    var ValuePair = function(key, value){
        this.key = key;
        this.value = value;
    };
    // 改写put方法
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        if (table[position] == undefined) {
            // 在当前位置示例化一个链表
            table[position] = new LinkedList();
        }
        // 在链表中添加元素
        table[position].append(new ValuePair(key, value));
    };
    // 改写get方法
    this.get = function(key) {
        var position = loseloseHashCode(key);
        if (table[position] !== undefined){
            // 获取链表的第一个元素
            var current = table[position].getHead();
            // 遍历链表（这里不能遍历到最后一个元素，后续特殊处理）
            while(current.next){
                // 如果链表中存在当前key对应的元素，返回其值
                if (current.element.key === key){
                    return current.element.value;
                }
                // 处理下一个元素
                current = current.next;
            }
            // 处理链表只有一个元素的情况或处理链表的最后一元素
            if (current.element.key === key){
                return current.element.value;
            }
        }
        // 不存在值，返回undefined
        return undefined;
    };
    // 改写remove方法
    this.remove = function (key) {
        var position = loseloseHashCode(key);
        if (table[position] !== undefined) {
            // 获取当前位置链表的第一个元素
            var current = table[position].getHead();
            // 遍历链表（这里不能遍历到最后一个元素，后续特殊处理）
            while (current.next) {
                if (current.element.key === key) {
                    // 遍历到对应元素，从链表中删除
                    table[position].remove(current.element);
                    if (table[position].isEmpty()) {
                        // 如果链表已经空了，将散列表的当前位置置为undefined
                        table[position] = undefined;
                    }
                    // 返回true表示删除成功
                    return true;
                }
                // 处理下一个元素
                current = current.next;
            }
            // 处理链表只有一个元素的情况或处理链表的最后一元素
            if (current.element.key === key) {
                table[position].remove(current.element);
                if (table[position].isEmpty()) {
                    table[position] = undefined;
                }
                return true;
            }
        }
        // 要删除的元素不存在，返回false
        return false;
    };

线性探查法在向散列表中插入元素时，如果插入位置position已经被占据，就尝试插入position+1的位置，以此类推，直到找到空的位置。下面用线性探查的方式重写put、get、remove方法

    // 重写put方法
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        // 依次查找，如果当前位置不为空，position + 1，直到找到为空的位置为止
        while (table[position] != undefined){
            position++;
        }
        table[position] = new ValuePair(key, value);
    };
    // 重写get方法
    this.get = function(key) {
        var position = loseloseHashCode(key);
        var len = table.length;
        // 只要当前位置小于散列表长度就要查找
        if (position < len){
            // 由于查找的值可能是以 position + 1 的形式类推，找到空位后插入的
            // 因此需要从当前位置（position）开始查找，直到找到key相同的位置，或者找完整个散列表
            while (position < len && (table[position] === undefined || table[position].key !== key)){
                position++;
            }
            // 如果最终position >= len，说明没找到
            if (position >= len) {
                return undefined
            } else {
                // 否则说明找到了，返回对应值
                return table[position].value;
            }
        }
        // 如果当前位置为空，说明添加时没有累加position，直接返回undefined
        return undefined;
    };
    // 改写remove方法
    this.remove = function(key) {
        var position = loseloseHashCode(key);
        var len = table.length;
        if (position < len){
            // 从当前位置（position）开始查找，直到找到key相同的位置，或者找完整个散列表
            while (position < len && (table[position] === undefined || table[position].key !== key)){
                position++;
            }
            // 如果最终position < len，说明找到了,将对应位置数据删除
            if (position < len) {
                table[position] = undefined;
            }
        }
    };

上述散列函数表现并不好，它极易计算出相同的hash值，从而导致冲突。一个表现良好的散列函数应该有较好的插入和查找性能且有较低的冲突可能性。下面的散列函数，被证明是比较合适的。

var djb2HashCode = function (key) {
    var hash = 5381; // 一个较大的素数基准值
    for (var i = 0; i < key.length; i++) {
        hash = hash * 33 + key.charCodeAt(i); // 基准值乘以33再加ASCII码值
    }
    return hash % 1013; //除以1013取余
};