数据结构-散列
散列概览
我们的散列表示基于数组进行设计的. 数组的长度是预先设定的, 如有需要, 可以随时增加. 所有元素根据和该元素对应的键, 保存在数组的特定位置, 该键和我们前面讲到的字典中的键是类似的概念. 使用散列表存储数据时, 通过一个散列函数将键映射为一个数字, 这个数字的范围是0到散列表的长度.
理想情况下, 散列函数会将每个键映射为一个唯一的函数索引. 然鹅, 键的数量是无限的, 数组的长度是有限的(理论上, 在js中是这样的). 一个更现实的目标是让散列函数尽量将键均匀地映射到数组中.
即使使用一个搞笑的散列函数, 仍然存在将两个键映射成同一个值的可能, 这样现象称为 碰撞(collision) , 当 碰撞 发生时, 我们需要有方法去解决. 本章稍后将详细讨论如何解决 _碰撞_.
要确定的最后一个问题是: 散列表中的数组究竟应该有多大? 这是编写散列函数时必须要考虑的. 对数组大小常见的限制是: 数组长度应该是一个质数. 在实现各种散列函数时, 我们将讨论为什么要求数组长度为质数. 之后, 会有多种确定数组大小的策略, 所有的策略都基于处理碰撞的技术, 因此, 我们将讨论如何处理碰撞时对它们进行讨论.
HashTable类
我们使用一个类来表示散列表, 该类包含计算散列值的方法、向散列中插入数据的方法、从散列表中读取数据的方法、显示散列表中数据分布的方法, 以及其它一些可能会用到的工具方法.
class HashTable {
constructor() {
this._table = new Array(137);
}
_simpleHash() {
}
showDistro() {
}
put() {
}
}选择一个散列函数
散列函数的选择依赖于键值的数据类型. 如何键是整型, 最简单的散列函数就是以数组的长度对键取余. 在一些情况下, 比如数组的长度是10, 而键值都是10的倍数时, 就不推荐使用这种方式了. 这也是数据长度为什么要是质数的原因之一, 就像我们在上个构造函数中, 设定数组长度为137一样. 如何键是随机的整数, 则散列函数应该更均匀地分布这些键. 这种散列方式称为: 除留余数法 .
在很多应用中, 键是字符串类型. 事实证明, 选择针对字符串类型的散列函数是很难的, 选择时必须加倍小心.
乍一看, 将字符串中的每个字符的ASCII码值相加似乎是一个不错的散列函数. 这样散列值就是ASCII码值的和 除以数组长度的余数. 该散列的方法_simpleHash():
...
_simpleHash(data) {
let total = 0;
for(let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
};
return total % this._table.length;
}
...再给HashTable加两个方法: put()和_showDistro(), 一个用来将数据存入散列表, 一个用来显示散列表中的数据, 这样就初步实现了HashTable类.
...
showDistro() {
this._table.forEach((i, index) => {
if(i != undefined) {
log(`${index}: ${i}`)
}
})
}
put(data) {
const pos = this._simpleHash(data);
this._table[pos] = data;
}
...做一个简单散列:
window.log = console.log.bind(console)
class HashTable {
constructor() {
this._table = new Array(137);
}
_simpleHash(data) {
let total = 0;
for(let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
};
return total % this._table.length;
}
showDistro() {
this._table.forEach((i, index) => {
if(i != undefined) {
log(`${index}: ${i}`)
}
})
}
put(data) {
const pos = this._simpleHash(data);
this._table[pos] = data;
}
};
const someNames = [ 'David', 'Jennifer', 'Donnie', 'Raymond', 'Cynthia', 'Mike', 'Clayton', 'Danny', 'Jonathan' ];
const h = new HashTable();
someNames.forEach(i => {
h.put(i);
});
h.showDistro();输出如下:
35: Cynthia 45: Clayton 57: Donnie 77: David 95: Danny 116: Mike 132: Jennifer 134: Jonathan
_simpleHash()函数通过使用js的charCodeAt()函数, 返回每个字符的ASCII码值, 然后再将它们相加得到散列值. put()方法通过调用_simpleHash()函数得到数组的索引, 然后将数据存储到该索引对应的位置上. 你会发现, 数据并不是均匀分布的, 人名想数组的两端集中.
比起这种不均匀的分布, 还有一个更严重的问题. 如果你仔细观察输出, 会发现初始的数组中的人名并没有全部显示. 给_simpleHash()函数加入一条console.log()输出, log('Hash value:' + data + '->' + total);
运行程序你就会发现有两个字符串'Clayton'和'Raymond'的散列值是一样的. 一样的散列值引发了碰撞, 因为碰撞, 只有'Clayton'存入了散列表. 可以通过改善散列函数来避免碰撞.
一个更好的散列函数
为了避免碰撞, 首先要确保散列表中用来存储数据的数组其大小是个 质数. 这一点很关键, 这和计算散列值时使用的取余运算有关. 数组的长度应该在100以上, 这是为了让数据在散列表中分布得更加均匀. 通过试验我们发现, 比100大且不会让数据产生碰撞的第一个质数是137. 使用其它更接近100的质数, 在该数据集上依然会产生碰撞.
为了避免碰撞, 在给散列表一个合适的大小后, 接下来要有一个计算散列值的更好方法.
霍纳算法 很好的解决了这个问题. 本书不会过深入该算法的数学细节, 在此算法中, 新的散列函数仍然先计算字符串中各字符的ASCII码值, 不过求和时每次要乘以一个质数. 大多数算法书建议使用一个较小的质数, 比如31, 但是对于我们的数据集, 31不起作用, 我们使用37, 这样刚好不会产生碰撞.
_betterHash(data) {
const H = 37;
let total = 0;
for(let i = 0; i < data.length; i++) {
total += H * total + data.charCodeAt(i);
};
total = total % this._table.length;
if(total < 0) {
total += this._table.length - 1;
};
return parseInt(total);
}window.log = console.log.bind(console)
class HashTable {
constructor() {
this._table = new Array(137);
}
_simpleHash(data) {
let total = 0;
for(let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
};
return total % this._table.length;
}
_betterHash(data) {
const H = 37;
let total = 0;
for(let i = 0; i < data.length; i++) {
total += H * total + data.charCodeAt(i);
};
total = total % this._table.length;
if(total < 0) {
total += this._table.length - 1;
};
return parseInt(total);
}
showDistro() {
this._table.forEach((i, index) => {
if(i != undefined) {
log(`${index}: ${i}`)
}
})
}
put(data) {
const pos = this._betterHash(data);
this._table[pos] = data;
}
};
const someNames = [ 'David', 'Jennifer', 'Donnie', 'Raymond', 'Cynthia', 'Mike', 'Clayton', 'Danny', 'Jonathan' ];
const h = new HashTable();
someNames.forEach(i => {
h.put(i);
});
h.showDistro();程序输出:
12: Jennifer 22: Raymond 55: Donnie 58: Clayton 80: Jonathan 82: Mike 103: Cynthia 110: Danny
这次所有的人名都显示出来了, 而且没有碰撞.
散裂化整型键
上面展示了如何散列化字符串类型的键, 接下来介绍如何使用散列化整型键, 使用的数据集是学生的成绩. 我们将随机产生一个9位数的键, 用以识别学生身份和一门成绩. 下面是产生学生数据(包含ID和成绩)的函数:
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
};
function genStuData(arr) {
for(let i = 0; i < arr.length; i++) {
let num = '';
for(let j = 1; j <= 9; j++) {
num += Math.floor(Math.random() * 10)
};
num += getRandomInt(50, 100);
arr[i] = num;
};
};使用getRandomInt()函数时, 可以指定随机数的最大值和最小值. 拿学生成绩来说, 最低分50, 最高分100.
genStuData()函数生成学生的数据. 里层的循环用来生成学生的ID, 紧跟在循环后面的代码生成一个随机的成绩, 并把成绩缀在ID的后面. 主程序会把ID和成绩分离. 散列函数将学生ID里的数字相加, 使用_simpleHash()函数计算出散列值.
执行程序:
const students = new Array(10);
genStuData(students);
students.forEach(i => {
log(i.substring(0, 8) + ' ' + i.substring(9))
});
const h = new HashTable();
students.forEach(i => {
h.put(i)
});
h.showDistro();程序输出:
83700897 87 25732026 56 60875817 85 49919842 77 09796486 57 67922868 58 57820350 58 70903358 54 46307166 100 09033369 99 23: 57820350058 25: 70903358154 27: 25732026956 38: 09033369799 41: 49919842177 46: 09796486557 49: 67922868858 62: 463071660100
散列函数再一次发生碰撞, 数组中没有包含所有的数据. 事实上, 如果将程序多跑几次, 有时会出现正常的情况, 但是结果太不一致了. 可以通过修改数组的大小, 或者在调用put()方法时使用更好的_betterHash()函数, 来试试能不能解决碰撞.
使用_betterHash()散列函数得到的输出:
88200007 99 22314764 82 25636690 64 88623060 53 17940629 70 59142776 58 14774034 70 90261540 66 02406002 75 95463920 65 8: 59142776758 27: 22314764782 46: 95463920165 57: 25636690564 78: 90261540066 80: 88623060453 98: 17940629670 108: 14774034770 112: 02406002475 114: 88200007799
很明显: 无论是字符串还是整型, _betterHash()的散列效果都更胜一筹.
对散列表排序、从散列表中取值
前面讲的是散列函数, 现在学以致用, 看看如何使用散列表来存储数据. 为此, 需要修改put()方法, 使得该方法同时接受键和数据作为参数, 对键值散列后, 将数据存储到散列表中.
然后定义get()方法, 用以读取存储在散列表中的数据. 该方法同样需要对键值进行散列化, 然后才能知道数据到底存储在数组的什么位置.
window.log = console.log.bind(console)
class HashTable {
constructor() {
this._table = new Array(137);
}
_simpleHash(data) {
let total = 0;
for(let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
};
return total % this._table.length;
}
_betterHash(data) {
const H = 37;
let total = 0;
for(let i = 0; i < data.length; i++) {
total += H * total + data.charCodeAt(i);
};
total = total % this._table.length;
if(total < 0) {
total += this._table.length - 1;
};
return parseInt(total);
}
showDistro() {
this._table.forEach((i, index) => {
if(i != undefined) {
log(`${index}: ${i}`)
}
})
}
put(key, data) {
const pos = this._betterHash(key);
this._table[pos] = data;
}
get(key) {
return this._table[this._betterHash(key)];
}
};
const h = new HashTable();
h.put('张三', 110);
h.put('李四', 112);
h.put('王五', 119);
log(h.get('王五')); // 输出 119碰撞处理
当散列函数对于多个输入产生同样的输出时, 就产生了碰撞. 散列算法的第二部分就是介绍如何解决碰撞, 是所有键都得以存储在散列表中. 下面介绍两种解决办法: 开链法 和 线性探测法 .
开链法
当碰撞发生时, 我们仍希望将键存储到通过散列算法产生的索引位置上, 但实际上, 不可能将多份数据存储到一个数组单元中. 开链法是指实现散列列表的底层数组中, 每个数组元素又是一个新的数据结构, 比如另一个数组, 这样就能存储多个键了.
使用这种技术. 即使两个键散列后的值相同, 依然被保存在同样的位置, 只不过它们在第二个数组中的位置不一样罢了.
实现开链法的方法时: 在创建存储散列过的键值的数组时, 通过调用一个函数创建一个新的空数组, 然后将该数组赋给散列表里的每个数组元素. 这样就创建了一个二维数组. 我们定义了一个函数buildChains()函数用来创建第二组数组, 我们也称这个数组为 链 .
完整代码:
window.log = console.log.bind(console)
class HashTable {
constructor() {
this._table = new Array(137);
}
_simpleHash(data) {
let total = 0;
for(let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
};
return total % this._table.length;
}
_betterHash(data) {
const H = 37;
let total = 0;
for(let i = 0; i < data.length; i++) {
total += H * total + data.charCodeAt(i);
};
total = total % this._table.length;
if(total < 0) {
total += this._table.length - 1;
};
return parseInt(total);
}
showDistro() {
this._table.forEach((i, index) => {
if(i[0] != undefined) {
log(`${index}: ${i}`)
}
});
}
buildChains() {
for(let i = 0; i < this._table.length; i++) {
this._table[i] = new Array();
};
}
put(key, data) {
const pos = this._betterHash(key);
let index = 0;
if(this._table[pos][index] == undefined) {
this._table[pos][index] = data;
} else {
while(this._table[pos][index] != undefined) {
++index
};
this._table[pos][index] = data;
}
}
get(key) {
let index = 0;
const pos = this._betterHash(key);
while ((this._table[pos][index] != undefined) && (this._table[pos][index] != key)) {
index += 1;
};
if(this._table[pos][index] == key) {
return this._table[pos][index];
} else {
return undefined;
}
}
};
const someNames = [ 'David', 'Jennifer', 'Donnie', 'Raymond', 'Cynthia', 'Mike', 'Clayton', 'Danny', 'Jonathan' ];
const h = new HashTable();
h.buildChains();
someNames.forEach(i => {
h.put(i, i);
});
h.showDistro();
log(h.get('David'))
log(h.get('Jonathan'))考虑到散列表现在使用多维数组存储数据, 为了更好地显示使用了开链法后键值的分布, 修改了showDistor()方法.
重新定义了put(), 将键值散列, 散列后的的值对应数组中的一个位置, 先尝试将数据放在该位置上的数组中的第一个单元格, 如果该单元格已经有数据了, put()方法会搜索下一个位置, 知道找到能放置数据的单元格, 并把数据存储进去. 这里实际上可以用this._table[pos].push(data)来代替, 因为通过buildChains()方法已经将散列表中的元素修改为二维数组(链).
get()方法先对键值散列, 根据散列后的值找到散列表中相应的位置, 然后搜索该位置上的链, 知道找到键值. 如果找到, 就将紧跟在键值后面的数据返回; 如果没有, 就返回undefined.
线性探测法
第二种处理碰撞的方法是 线性探测法 . 线性探测法隶属于一种更一般化的散列技术: _开放寻址散列_. 当发生碰撞时, 线性探测法检查散列表中的下一个位置是否为空. 如果为空, 就将数据存入该位置; 如果不为空, 则继续查找下一个位置, 知道找到一个空的为止. 该技术是基于这样一个事实: 每个散列表都会有很多空的单元格, 可以使用他们来存储数据.
当存储数据使用的数组特别大时, 选择线性探测法要比开链法好. 这里有个公式, 常常可以帮助我们选择使用哪种碰撞解决办法: 如果数组的大小事带存储数据个数的1.5倍, 那么使用开链法; 如果数组的大小是待存储数据的两倍及两倍以上时, 那么使用线性探测法.
为了说明线性探测法的工作原理, 可以重写put()和get()方法. 为了实现一个真实的数据存取系统, 需要为HashTable类增加一个新的数组, 用来存储数据. 数组_table和_values并行工作, 当将一个键值保存到数组_table中同时将数据存入数组_values中相应的位置上.
在HashTable的构造函数中加入下面一行代码:
this._values = [];
在put()方法中使用线性探测技术:
...
put(key, data) {
let pos = this._betterHash(key);
if(this._table[pos] == undefined) {
this._table[pos] = key;
this._values[pos] = data;
} else {
while(this._table[pos] != undefined) {
pos++
};
this._table[pos] = key;
this._values[pos] = data;
}
}
...get()方法先搜索键在散列表中的位置, 如果找到, 则返回数组_values中对应位置上的数据; 如果没有找到, 则循环搜索, 知道找到对应的键或者数组中的单元为undefined时, 后者表示该键没有被存入散列表中.
...
get(key) {
let hash = -1;
hash = this._betterHash(key);
if(hash > -1) {
for(let i = hash; this._table[hash] != undefined; i++) {
if(this._table[i] === key) {
return this._values[i];
};
}
};
return undefined;
}
...