本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2021-05-03
散列是一种常用的数据存储技术，散列后的数据可以快速地插入和取用。散列使用的数据结构叫做 散列表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来却效率低下。
这一章，我们的散列表是基于数组进行设计的，数组的长度是预先设定的，如有需要，可以随时地增加。所有元素根据和该元素对应的键，保存在数组的特定位置。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是0到散列表的长度。
理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而， 键的数量是无限的，数组的长度是有限的（理论上，在JavaScript中数组长度是 2^32），一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。
即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象被称为 碰撞 (collision)，当碰撞发生时，我们需要有方案去解决，会在稍后提到。
要确定的最后一个问题是：散列表中的数组究竟应该有多大？这是编写散列函数时必须要考虑的，对数组大小常见的限制是：数组长度应该是一个质数。稍后，我们会讨论为什么数组的长度为质数。
下面将使用一个类来表示散列表，该类包含计算散列值的方法，向散列中插入数据、读取数据、显示数据的方法。
function HashTable() {
this.table = new Array(137); // 写死限制数组的长度
this.simpleHash = simpleHash;
this.showDistro = showDistro;
this.put = put;
}
// 一个简单的散列函数
function simpleHash(data) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i)
// 则 total 为每个字母的ASCII码之和
}
return total % this.table.length; // 使用每个字母的ASCII码之和对数组的长度求模，以限制数组不会超出长度。
// 关于碰撞的处理，之后会介绍
}
function put(data) {
var pos = this.simpleHash(data); // 通过散列函数对data映射生成一个key值
this.table[pos] = data;
}
// 显示数据
function showDistro() {
for (var i = 0; i < this.table.length; ++i) {
const item = this.table[i];
if (item != undefined) {
console.log(`${i}: ${item}`);
}
}
}
测试代码：
var someNames = ['David', 'Jennifer', 'Clayton','Donnie', 'Raymond', 'Cynthia']
var h = new HashTable();
for (var i = 0; i < someNames.length; i++) {
h.put(someNames[i])
}
h.showDistro()
// 35: Cynthia
// 45: Raymond
// 57: Donnie
// 77: David
// 132: Jennifer
上面的测试代码可以发现，Clayton 并没有被打印出来，因为根据我们的 simpleHash 函数的逻辑， Clayton 和 Raymond 计算出来的键值是一样的，所以后面的 Raymond 覆盖了 Clayton，这就是发生了碰撞，可以通过改善散列函数来避免碰撞。
为了避免碰撞，采用一个更好的计算散列值的方法，即霍纳算法，在此算法中，新的散列函数仍然先计算字符串中各字符的 ASCII 码，不过求和时每次乘以一个质数，大多数算法法建议使用一个较小的质数，我们这里使用 37。
function betterHash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; i++) {
total += H * total + string.charCodeAt(i)
}
total = total % this.table.length;
return parseInt(total);
}
修改 HashTable 类：
function HashTable() {
this.table = new Array(137);
this.showDistro = showDistro;
this.betterHash = betterHash;
this.put = put;
}
function put(data) {
var pos = this.betterHash(data);
this.table[pos] = data;
}
// 测试代码不变，结果变为
// 12: Jennifer
// 22: Raymond
// 55: Donnie
// 58: Clayton
// 80: David
// 103: Cynthia
// 有效的避免了碰撞
当然，这不能完美的解决碰撞，这只是一个更好的散列算法而已。后面我们将讨论碰撞处理。
现在我们看看怎么使用散列表来存储数据，为此，需要修改 put 方法，使得该方法同时接受键和数据作为参数，对键值散列后，将数据存储到散列表中。
function put(key, data) {
// 对键值进行散列
var pos = this.betterHash(key)
this.table[pos] = data;
}
function get(key) {
return this.table[this.betterHash(key)]
}
当散列函数对于多个输入产生同样的输出时，就产生了碰撞。下面就介绍如何解决碰撞，使所有的键都得以存储在散列表中。
当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组元素又是新的数据结构，比如另一个数组，这样就能存储多个键了。
实现开链法的方法是：在创建存储散列过的键值的数组时，通过调用一个函数创建一个新的空数组，然后将数组赋给散列表里的每个数组元素，这样就创造了一个二维数组。
function buildChains() {
for (var i = 0; i < this.table.length; i++) {
this.table[i] = new Array()
}
}
同时需要修改对应的 put 方法，该方法将键值散列，散列后的值对应数组中的一个位置，该位置是一个数组，使用数组中两个连续的单元格，第一个用来保存键值，第二个用来保存键值。
get 方法则先对键值散列，根据散列后的值找到散列表中对应的位置，然后搜索该位置的数组，直到找到键值，如果找到，就将紧跟着键值后面的数据返回，如果没有找到，就返回 undefined。
最终代码为：
function HashTable() {
this.table = new Array(137);
this.showDistro = showDistro;
this.simpleHash = simpleHash;
this.put = put;
this.get = get;
this.buildChains = buildChains;
}
function simpleHash(data) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i)
}
return total % this.table.length;
}
// modify
function put(key, data) {
var pos = this.simpleHash(key)
var index = 0;
while (this.table[pos][index] != undefined) {
++index;
}
this.table[pos][index] = key;
this.table[pos][index+1] = data;
}
// modify
function get(key) {
var pos = this.simpleHash(key)
for (var i = 0 ; i < this.table[pos].length; i+=2) {
if (this.table[pos][i] === key) {
return this.table[pos][i+1]
}
}
return undefined;
}
function showDistro() {
for (var i = 0; i < this.table.length; ++i) {
if (this.table[i][0] != undefined) {
console.log(`${i}: ${JSON.stringify(this.table[i])}`);
}
}
}
function buildChains() {
for (var i = 0; i < this.table.length; i++) {
this.table[i] = new Array()
}
}
var someNames = ['David', 'Jennifer', 'Clayton','Donnie', 'Raymond', 'Cynthia']
var h = new HashTable();
h.buildChains();
for (var i = 0; i < someNames.length; i++) {
// 以名字做key 以 { name: 名字 } 作为数据
h.put(someNames[i], {
name: someNames[i]
})
}
h.showDistro()
// 35: ["Cynthia",{"name":"Cynthia"}]
// 45: ["Clayton",{"name":"Clayton"},"Raymond",{"name":"Raymond"}]
// 57: ["Donnie",{"name":"Donnie"}]
// 77: ["David",{"name":"David"}]
const a = h.get('Raymond')
console.log(a); // { name: 'Raymond' }
const b = h.get('Raymond2')
console.log(b); // undefined
const c = h.get('Clayton')
console.log(c); // { name: 'Clayton' }
线性探测法隶属于一种更一般化的散列技术：开放寻址散列。当发生碰撞时，线性探测法检测散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置。该技术基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存储数据。
当存储数据使用的数组特别大时，选择线性探测法要比开链法好，这里有一个公式，常常可以帮助我们使用哪种碰撞解决办法：如果数组的大小是待存储数据的1.5倍，那么使用开链法；如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探测法。
针对线性探测法，要重写 put 和 get 方法，重写 此处HashTable 的 put 以及增加一个 get 方法即可，相同的测试代码，可以发现 45 位置上变成了 Clayton，与它散列键值一样的 Raymond 则依次后移为 46 号位置了，不会出现之前后面的 Raymond 覆盖 Clayton 的情况了。
function put(key, data) {
var pos = this.simpleHash(key);
if (this.table[pos] == undefined) { // 为空 则存入
this.table[pos] = key;
this.values[pos] = data; // HashTable加一个values用来方便存取数据
} else { // 为空，则往下寻找为空的位置
while (this.table[pos] != undefined) {
pos++;
pos = pos >= this.table.length ? 0 : pos;
}
this.table[pos] = key;
this.values[pos] = data;
}
}
function get(key) {
var hash = this.simpleHash(key)
while (this.table[hash] != undefined) {
if (this.table[hash] == key) {
return this.values[hash]
}
hash++;
hash = hash >= this.table.length ? 0 : hash;
}
return undefined;
}
var someNames = ['David', 'Jennifer', 'Clayton','Donnie', 'Raymond', 'Cynthia']
var h = new HashTable();
for (var i = 0; i < someNames.length; i++) {
h.put(someNames[i], {
name: someNames[i]
})
}
h.showDistro()
// 35: Cynthia
// 45: Clayton
// 46: Raymond
// 57: Donnie
// 77: David
// 132: Jennifer
console.log(h.get('Clayton')); // { name: 'Clayton' }
console.log(h.get('Raymond')); // { name: 'Raymond' }