散列后的数据可以快速插入或取用，散列使用的数据结构是散列表
适合插入、删除、取用数据；不适合查找
更现实的目标是：让散列函数尽量将键均匀地映射到数组中
两个键映射到同一个值的情况叫做碰撞
首先用一个HashTable的类来表示散列表，我们可以通过这个类来向散列插入新数据、从散列中读取数据、显示散列中数据分布、定义如何去计算散列值1
2
3
4
5
6
7function HashTable() {
this.table = new Array(137) // 这里数组的长度推荐是质数
this.simpleHash = simpleHash
this.showDistro = showDistro
this.put = put
this.get = get
}
散列函数是这个过程的重点，它相当于一个信息压缩函数，将键（通常是字符串的形式）压缩成一个值（通常为数值形式）
散列函数定义如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28function simpleHash(data){
let total = 0
for(let i = 0; i < data.length; ++i){
total += data.charCodeAt(i);
}
return total % this.table.length
}
function put(data){
let pos = this.simpleHash(data)
this.table[pos] = data
}
function showDistro(){
for(let i = 0; i < this.table.length; ++i){
if(this.table[i] != undefined){
console.log(i + ":" + this.table[i])
}
}
}
// 测试代码
let cities = ['shenzhen', 'beijing', 'guangzhou', 'shanghai']
let hTable = new HashTable()
for(let i = 0; i < cities.length; ++i){
hTable.put(cities[i])
}
hTable.showDistro()
以上这种散列函数，会使得如果两个键所产生的散列值是相同的，那么只有一个能存入散列表，也就是发生了碰撞
我们可以通过改善散列函数来避免碰撞
需要从以下几个方面入手改善
- 数组的长度应该是质数
- 霍纳算法
使用霍纳算法来改善之前的散列函数1
2
3
4
5
6
7
8
9function betterHash(string, arr){
const H = 37
let total = 0
for(let i = 0; i< string.length; ++i){
total += H * total + string.charCodeAt(i) // 区别是每次求和时都要乘以一个质数
}
total = total % arr.length
return parseInt(total)
}
上面我们所散列化的键都是字符串类型，接下来要继续修改这个程序，使之可以散列化整型键1
2
3
4
5
6
7
8
9
10
11
12
13
14function 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
}
}
同理使用betterHash得到散列值，以避免发生碰撞
普遍采用betterHash，所以重写put方法1
2
3
4function put(key, data) {
let pos = this.betterHash(key)
this.table[pos] = dataa
}
定义get方法，用来读取存储在散列表中的数据1
2
3function get(key) {
return this.table[this.betterHash(key)]
}
通过对键值进行散列，得到一个散列值，再通过这个散列值去散列表中读取对应的数据
接下来重点介绍如何解决碰撞
首先我们知道，当不同的输入通过散列函数后，得到相同的输出，这就是碰撞。解决碰撞一般有两种方式
- 开链法
- 线性探测法
开链法的重点是用来存储散列值的数组中每个元素，是一个新的数据结构，这样相同的输出也就能够共存了
相碰撞的两个散列值在第一数组的存储位置是相同的，不同的第二数组的位置，实现代码如下：1
2
3
4
5function buildChains() {
for(let i = 0; i < this.table.length; ++i) {
this.table[i] = new Array()
}
}
重新定义put方法1
2
3
4
5
6
7
8
9
10
11
12
13
14function put(key, data){
let pos = this.betterHash(key)
let index = 0
if(this.table[pos][index] == undefined) {
this.table[pos][index + 1] = data
}
++index
else {
while (this.table[pos][index] != undefined){
++index
}
this.table[pos][index+1] = data
}
}
重新定义get方法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function get(key){
let index = 0
let hash = this.betterHash(key)
if(this.table[hash][index] == key){
return this.table[hash][index+1]
}
index += 2
else {
while(this.table[pos][index] != key){
index += 2
}
return this.table[hash][index+1]
}
return undefined
}