哈希表是根据键可以访问到值的一种数据结构
在JavaScript中, 原生的 Object 就是哈希表的一种
这里用JavaScript实现一个哈希表, 完成存储和取值的两个方法
其中, 会用一个数组来存储哈希表的数据
最基本的功能
一. 数据存储在哪里?
哈希表需要一个数组, 用来存储所有的数据, 并且, 这个数组的长度应该是一个质数, 我们这里暂时取为137
二. 如何存储
当给一个哈希表提供一个 key 和 value 时, 有一个函数对这个key做一次运算, 根据他生成一个 0 - 137 的数字(这个过程就叫做哈希 hash),以这个数字为下标, 将数组的对应位置设置成 value
三. 如何取值
当给哈希表一个key, 希望取出对应的value时, 可以对这个key用第二步一样的哈希方法, 算出一个位置, 取出数组上对应位置的 value
知道了这些, 代码就比较好写了
class HashTable {
constructor() {
this.table = new Array(137)
}
hash(string) {
// 采用霍纳算法, 使得到的结果更分散
const H = 37
let total = 0
for (let i = 0; i < string.length; i++) {
total += H * total + string.charCodeAt(i)
}
total = total % this.table.length
return parseInt(total)
}
put(key, data) {
const index = this.hash(key)
this.table[index] = data
}
get(key) {
return this.table[this.hash(key)]
}
}
但是, 对不同的字符串进行哈希运算, 可能会得到一样的结果, 比如, 字符串 "aa_" 和 "_X" 哈希的结果都是 136
那么, 在设置或取值的时候, 就有可能会发生重复, 这个问题就是 哈希冲突
如何应对哈希冲突
开链法
开链法的过程
- 不变的是, 仍然要对 key 进行哈希运算, 找到这个位置
- 之前的这个位置应该存储的直接是 value, 开链法会在这个位置新建一个数组, 将 key 和 value 依次放到这个数组上(如果数组上的第一项已经有值了, 那么一直向后找, 直到没有值为止)
- 取值的时候, 需要先对key进行哈希, 然后找到这个位置上的数组, 再找到相同的key的位置, 下一个位置就是value了
代码如下
class HashTable {
constructor() {
this.table = new Array(137)
this.buildChains()
}
hash(string) {
const H = 37
let total = 0
for (let i = 0; i < string.length; i++) {
total += H * total + string.charCodeAt(i)
}
total = total % this.table.length
return parseInt(total)
}
put(key, data) {
const position = this.hash(key)
let index = 0
if (this.table[position][index] == undefined) {
this.table[position][index] = key
this.table[position][index + 1] = data
return
}
if (this.table[position][index] == 'key') {
this.table[position][index + 1] = data
return
}
while (this.table[position][index] != undefined) {
if (this.table[position][index] == key) {
break
}
index += 1
}
this.table[position][index] = key
this.table[position][index + 1] = data
}
buildChains() {
for (var i = 0; i < this.table.length; i++) {
this.table[i] = new Array()
}
}
get(key) {
var index = 0
var position = this.hash(key)
if (this.table[position][index] == key) {
return this.table[position][index + 1]
} else {
while (this.table[position][index] && this.table[position][index] != key) {
index += 2
}
return this.table[position][index + 1]
}
}
}
线性探测法
线性探测法的过程
- 内部有两个数组, 一个专门放key(这里简称为数组A), 另一个数组专门放value(这里简称为数组B)
- 存储时, 对key进行哈希, 如果数组A上的这个位置为空, 那么就把key放在这里, 把value放在数组B的相同位置; 如果不为空, 就去看看下一项, 直至找到为空的, 然后把key和value分别放进数组A和数组B
- 取值时, 对 key 进行哈希, 找到数组A上对应的位置, 如果key相等, 就取数组B上的这一项为value; 如果不相等, 则看下一位的key是否相等, 直至找到为止
class HashTable {
constructor() {
this.table = new Array(137)
this.values = []
}
hash(string) {
const H = 37
let total = 0
for (let i = 0; i < string.length; i++) {
total += H * total + string.charCodeAt(i)
}
total = total % this.table.length
return parseInt(total)
}
put(key, data) {
var position = this.hash(key)
if (this.table[position] == undefined) {
this.table[position] = key
this.values[position] = data
} else {
while (this.table[position] != undefined) {
if (this.table[position] == key) {
this.values[position] = data
return
}
// 防止超过数组的最后一位
if (position >= this.table.length - 1) {
position = 0
continue
} else {
position++
}
}
this.table[position] = key
this.values[position] = data
}
}
get(key) {
let hash = this.hash(key)
for (let i = 0; i < this.table.length; i ++) {
if (i == hash) {
if (key == this.table[hash]) {
return this.values[hash]
} else {
// 防止超过数组的最后一位
if (hash == this.table.length - 1) {
hash = 0
} else {
hash += 1
}
if (key == this.table[hash]) {
return this.values[hash]
}
}
}
}
}
}
