数据结构篇——散列

发表于 | 分类于

散列后的数据可以快速插入或取用，散列使用的数据结构是散列表

适合插入、删除、取用数据；不适合查找

更现实的目标是：让散列函数尽量将键均匀地映射到数组中

两个键映射到同一个值的情况叫做碰撞

首先用一个HashTable的类来表示散列表，我们可以通过这个类来向散列插入新数据、从散列中读取数据、显示散列中数据分布、定义如何去计算散列值

1
2
3
4
5
6
7
function 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
28
function 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
9
function 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
14
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
    }
}

同理使用betterHash得到散列值，以避免发生碰撞

普遍采用betterHash，所以重写put方法

1
2
3
4
function put(key, data) {
    let pos = this.betterHash(key)
    this.table[pos] = dataa
}

定义get方法，用来读取存储在散列表中的数据

1
2
3
function get(key) {
    return this.table[this.betterHash(key)]
}

通过对键值进行散列，得到一个散列值，再通过这个散列值去散列表中读取对应的数据

接下来重点介绍如何解决碰撞

首先我们知道，当不同的输入通过散列函数后，得到相同的输出，这就是碰撞。解决碰撞一般有两种方式

  • 开链法
  • 线性探测法

开链法的重点是用来存储散列值的数组中每个元素，是一个新的数据结构，这样相同的输出也就能够共存了

相碰撞的两个散列值在第一数组的存储位置是相同的，不同的第二数组的位置，实现代码如下：

1
2
3
4
5
function 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
14
function 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
15
function 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
}