JavaScript数据结构 --- 散列

散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用，但查找操作却效率低下，这是可以依靠其他数据结构（例如二叉查找树）。

散列使用的数据结构叫散列表，这里的散列表是基于数组进行设计的。所有元素根据该元素对应的键（类型字典中的键），保存在数组的特定位置。使用散列表存储数据时，通过一个散列函数 将键映射为一个长度为 0 到散列表长度的数字。

一般来说，数组的长度是有限的，所以我们让散列函数尽量将键均匀地映射到数组中。

1. HashTable 类
使用一个类来表示散列表。


function HashTable() {
   this.table = new Array(137); // 构建一个新数组用来存储 散列表
   this.simpleHash = simpleHash; // 一个简单的散列函数
   this.showDistro = showDistro; // 显示散列表中的数据
   this.put = put; // 将数据插入散列表
}

1.1 选择散列函数
散列函数的选择依赖键值的数据类型。如果键是整形，最简单的散列函数就是以数组的长度对键取余。当很多键值是数组的长度的倍数时，这种方式会导致大规模碰撞（散列值一样）。所以一般将数组的长度设为质数。

针对字符串类型的散列函数比较困难，要更加小心选择。

我们定义的 smpleHash 函数是将每个字符的 ASCII 码相加。如此散列值就是 ASCII 码值之和除以数组长度得到的余数。

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

再定义用来将数据存入散列表的方法 put() 和用来显示散列表中的数据的方法 showDistro() 。

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

测试用例
HashTable1
程序结果：

 35: Cynthia
 45: Clayton
 57: Donnie
 77: David
 95: Danny
 116: Mike
 132: Jennifer
 134: Jonathan

根据结果来看，数据没有均匀分布，有时候还会出现碰撞（散列值一样）的情况，我们需要改善散列函数。

1.2 更好的散列函数

使用霍纳德算法得到更好的散列函数。

function betterHash(string, arr) {
   const H = 37; // 通过一个常数值声明一个块范围变量
   var total = 0;
   for (var i = 0; i < string.length; ++i) {
      total += H * total + string.charCodeAt(i);
   }    
   total = total % arr.length;
   return parseInt(total);
}

测试用例：
betterHash

结果为：

12: Jennifer
22: Raymond
55: Donnie
58: Clayton
80: Jonathan
82: Mike
103: Cynthia
110: Danny

1.3 散列化整型键

这里使用的数据集是学生的成绩，随机产生一个9位数的键，用来识别学生身份和一门成绩。

function getRandomInt (min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function genStuData(arr) {
   for (var i = 0; i < arr.length; ++i) {
      var num = "";
      for (var j = 1; j <= 9; ++j) {
         num += Math.floor(Math.random() * 10);
      }
      num += getRandomInt(50,100); //可以指定随机数的最大值和最小值
      arr[i] = num;
   }
}

genStuDate() 函数生成学生的数据。里层的循环生成 ID，后面的循环代码生成一个随机的成绩，并把成绩添加在ID后面。主程序会分离ID和成绩，散列函数将学生ID里的数字相加，使用 simpleHash() 函数计算出散列值。
示例程序：
HashTable2

运行结果为：

 Student data:

 04437992 89
 35054068 96
 34780034 52
 34103157 91
 29752520 74
 96057108 80
 55413450 57
 33664847 61
 33179680 71
 91022430 51


 Data distribution:

 9: 91022430251
 16: 34103157291
 18: 34780034252
 26: 29752520374
 27: 55413450857
 28: 33664847061
 30: 96057108680
 32: 33179680771
 35: 35054068996
 44: 04437992989

使用更好的散列函数 betterHash()，得到的输出。
示例程序：
betterTable2.sj

 Student data:

 90605894 100
 41483254 96
 42802463 86
 25395996 90
 39102248 97
 52528869 68
 53083791 94
 01904985 63
 51172821 61
 84746600 82


 Data distribution:

 19: 84746600382
 40: 39102248697
 45: 01904985263
 61: 53083791894
 64: 42802463486
 70: 25395996790
 93: 52528869068
 105: 41483254496
 112: 906058948100
 127: 51172821561

通过对比，可以发现无论是字符串还是整型， betterHash() 的散列效果都更胜一筹。