JavaScript 散列

[Checkson]

前言

我曾经以为，字典和散列表这两者是没什么区别的，在 JavaScript 中最具有代表的数据结构是 Object 类了。事实上，并不是这样的。在字典中，我们用 键-值 的形式来存储数据。在散列表中也是一样（也是以 键-值对的形式来存储数据）。但是两种数据结构的实现方式略有不同。

前一章，我们聊到字典在 JavaScript 可以笼统理解为 Object 类，这一章我们重点介绍散列表，及其与字典有什么本质的区别。

定义

散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据结构叫做散列表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却效率低下，比如查找一组数据中的最大值和最小值。这些操作得求助于其他数据结构，二叉查找树就是一个很好的选择。本章将介绍如何实现散列表，并且了解什么时候应该用散列表存取数据。

概览

我们的散列表是基于数组进行设计的。数组的长度是预先设定的，如有需要，可以随时增加。所有元素根据和该元素对应的键，保存在数组的特定位置，该键和我们前面讲到的字典中的键是类似的概念。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是 0 到散列表的长度。

理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限的，数组的长度是有限的（理论上，在 JavaScript 中是这样），一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。

即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为碰撞（collision），当碰撞发生时，我们需要有方案去解决。

要确定的最后一个问题是：散列表中的数组究竟应该有多大？这是编写散列函数时必须要考虑的。对数组大小常见的限制是：数组长度应该是一个质数。在实现各种散列函数时，我们将讨论为什么要求数组长度为质数。之后，会有多种确定数组大小的策略，所有的策略都基于处理碰撞的技术。因此，我们将在讨论如何处理碰撞时对它们进行讨论。如下图，以一些字符串散列为例，阐释了散列的概念。

散列表（HashTable）类实现

完整代码地址，我们使用一个类来表示散列表，该类包含计算散列值的方法、向散列中插入数据的方法、从散列表中读取数据的方法、显示散列表中数据分布的方法，以及其他一些可能会用到的工具方法。

1. 构造函数

function HashTable () {
    this.table = new Array(137);
}

2. simpleHash：简单散列函数

散列函数的选择依赖于键值的数据类型。如果键是整型，最简单的散列函数就是以数组的长度对键取余。在一些情况下，比如数组的长度是 10，而键值都是 10 的倍数时，就不推荐使用这种方式了。这也是数组的长度为什么要是质数的原因之一，就像我们在上个构造函数中，设定数组长度为 137 一样。如果键是随机的整数，则散列函数应该更均匀地分布这些键。这种散列方式称为除留余数法。

在很多应用中，键是字符串类型。事实证明，选择针对字符串类型的散列函数是很难的，散列选择时必须加倍小心。

回过头来看，将字符串中每个字符的 ASCII 码值相加似乎是一个不错的散列函数。这样散列值就是 ASCII 码值的和除以数组长度的余数。该散列函数的定义如下：

HashTable.prototype.simpleHash = function (data) {
    var total = 0;
    for (var i = 0, len = data.length; i < len; i++) {
        total += data.charCodeAt(i);
    }
    return total % this.table.length;
}

3. betterHash：更好的哈希函数

为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关键，这和计算散列值时使用的取余运算有关。数组的长度应该在 100 以上，这是为了让数据在散列表中分布得更加均匀。通过试验我们发现，比 100 大且不会让大部分数据产生碰撞的第一个质数是 137。使用其他更接近 100 的质数，在该数据集上依然会产生碰撞。

为了避免碰撞，在给散列表一个合适的大小后，接下来要有一个计算散列值的更好方法。霍纳算法很好地解决了这个问题。在此算法中，新的散列函数仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数。

大多数算法书建议使用一个较小的质数，比如 31，但是对于我们的数据集，31 不起作用，我们使用 37，这样刚好不会产生碰撞。

现在我们有了一个使用霍纳算法的更好的散列函数：

HashTable.prototype.betterHash = function (data) {
    const H = 37;
    var total = 0;
    for (var i = 0, len = data.length; i < len; i++) {
        total += H * total + data.charCodeAt(i);
    }
    total = total % this.table.length;
    return parseInt(total);
}

4. put：向哈希表中添加元素

HashTable.prototype.put = function (key, data) {
    var pos = this.betterHash(key);
    this.table[pos] = data;
}

5. get：根据key获取哈希表中的值

HashTable.prototype.get = function (key) {
    return this.table[this.betterHash(key)];
}

6. showDistro：显示散列表元素信息

HashTable.prototype.showDistro = function () {
    for (var i = 0, len = this.table.length; i < len; i++) {
        if (this.table[i] != undefined) {
            console.log(i + ": " + this.table[i]);
        }
    }
}

哈希表（HashTable）类测试

var hashTable = new HashTable();
hashTable.put('张三', '13910241024');
hashTable.put('李四', '13520482048');
hashTable.put('王五', '13440964096');
hashTable.showDistro();
console.log('----------------------------');
console.log('王五的电话号码：', hashTable.get('王五'));

运行结果：

31: 13440964096
53: 13910241024
94: 13520482048
----------------------------
王五的电话号码： 13440964096

碰撞问题

当散列函数对于多个输入产生同样的输出时，就产生了碰撞。这里将介绍如何解决碰撞，使所有的键都得以存储在散列表中。我们下面将讨论两种碰撞解决办法：开链法 和 线性探测法。

1. 开链法

开链法 就是改成 HashTable 中的数组改成二维数组，当发现两个值经过散列函数计算后相同，就将两个值，两两按 键-值 形式存入一维数组。例如现在HashTable中的数组每个元素都成了一维数组了，而这个一维数组第一个元素存键，第二个元素存对应的值，两两按顺序组合。

2. 线性探测法

线性探测法，故名思意，就是线性处理碰撞问题。在 HashTable 存入元素时，发现当前 key 值存在元素了，就寻找该元素后一个位置，直到找到空位置为止，然后存储起来。

参考链接

• Javascript数据结构算法之散列（霍纳算法，开链法，线性探测-寻址法）
• hash冲突处理的三种方法：线性探测，二次探测和开链法详细解释
• 散列碰撞问题的解决——开链法（拉链法）
  
• 散列碰撞的解决方法——线性探测法（开放寻址法的一种）