关于哈希表的原理详见我的上一篇文章简单易懂数据结构之哈希表
前言
JavaScript中是有哈希类型的数据结构的，比如说最简单的对象{ },就有key: value这种结构。ES6新出的数据结构Map是对对象这种类型的扩展，同样也是哈希表。即使如此，重复造轮子还是有意义的，对于我们对底层原理的实现和编程能力的提高都是有帮助的。接下来让我们用JavaScript中的数组模拟哈希表这种数据结构。
代码链接：
简单哈希表：HashTable
仿Map哈希表: HashMap
结构设计
class HashTable {
// 初始化哈希表
constructor(size) {
}
// 从哈希表中取值
get() {}
// 向哈希表中填值
set() {}
// 从哈希表中删除数据
delete() {}
// 判断哈希表中存不存在该值
has() {}
// 展示哈希表中所有数据
showAllData() {}
}
代码实现
class HashMap {
constructor(size) {
this.table = new Array(size)
this.size = 0
}
//哈希函数，将value转化，计算出存储的key
hashConversion(value) {
let keyCode = 0
for(let item of value) {
keyCode += item.charCodeAt(0)
}
let key = keyCode % this.table.length
return key
}
set(value) {
let key = this.hashConversion(value)
this.size++
this.table[key] = value
}
get(value) {
let key = this.hashConversion(value)
return this.table[key]
}
delete(value) {
let key = this.hashConversion(value)
if(this.table[key] !== undefined) {
this.table[key] = undefined
this.size--
return true
} else {
return false
}
}
has(value) {
let key = this.hashConversion(value)
if(this.table[key] !== undefined) {
return true
} else {
return false
}
}
showAllData() {
let result = []
for (let item of this.table) {
if(item !== undefined) {
result.push(item)
}
}
return result
}
}
调用展示
let hashTable = new HashMap(10)
hashTable.set('1')
hashTable.set('aa')
hashTable.set('6a')
hashTable.set('75')
console.log('size:' + hashTable.size)
console.log(hashTable.showAllData())
结果展示1.png
冲突解决
仔细看上方的代码，很明显没有做冲突的处理，当输入的值发生冲突时，我们就没有办法得到想要的结果，在这里扩展上方代码，用线性探测法进行冲突处理。
/*
*使用数组模拟的JavaScript哈希表
*使用最简单的线性探测法解决冲突
*/
class HashTable {
constructor(size) {
this.table = new Array(size)
this.size = 0
}
//哈希函数
hashConversion(value) {
let keyCode = 0
for(let item of value) {
keyCode += item.charCodeAt(0)
}
let key = keyCode % this.table.length
return key
}
//set方法，用来向哈希表中填入数据
set(value) {
let key = this.hashConversion(value)
while(this.table[key] !== undefined && this.table[key] !== value) {
key++
if(key >= this.table.length) {
throw new Error('已经没有可用空间')
}
}
if (this.table[key] !== value) {
this.size++
this.table[key] = value
}
}
//get方法，用来从哈希表中取值
get(value) {
let key = this.hashConversion(value)
while(this.table[key] !== undefined && this.table[key] !== value) {
key++
if(key >= this.table.length) {
return undefined
}
}
return this.table[key]
}
//delete方法，用来删除哈希表的数据
delete(value) {
let key = this.hashConversion(value)
while(this.table[key] !== undefined && this.table[key] !== value) {
key ++
if(key >= this.table.length) {
return false
}
}
this.table[key] = undefined
this.size--
return true
}
//has方法，判断哈希表中有没有该值
has(value) {
let key = this.hashConversion(value)
while(this.table[key] !== undefined && this.table[key] !== value) {
key ++
if(key >= this.table.length) {
return false
}
}
if(this.table[key] !== undefined) {
return true
} else {
return false
}
}
//展示存储到哈希表中的所有数据
showAllData() {
let result = []
for (let item of this.table) {
if(item !== undefined) {
result.push(item)
}
}
return result
}
}
扩展
上文的HashTable有一个缺点，不能自己定义key值，我们想要类似JavaScript中对象或者说Map的功能，可以做到set(key,value), get(key) -->value这种功能。这就要对上文对数据结构进行更进一步的扩展。
/*
*使用数组模拟的JavaScript仿Map哈希表
*使用最简单的线性探测法解决冲突
*/
class HashMap {
constructor(size) {
this.table = []
for(let i = 0; i < size; i++) {
this.table.push([undefined, 0])
}
this.size = 0
}
//哈希函数
hashConversion(index) {
let keyCode = 0
for(let item of index) {
keyCode += item.charCodeAt(0)
}
let key = keyCode % this.table.length
return key
}
//set方法，用来向哈希表中填入数据
set(index, value) {
let key = this.hashConversion(index)
while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
key++
if(key >= this.table.length) {
throw new Error('已经没有可用空间')
}
}
if ((this.table[key])[0] !== index) {
this.size++
this.table[key][0] = index
this.table[key][1] = value
}
}
//get方法，用来从哈希表中取值
get(index) {
let key = this.hashConversion(index)
while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
key++
if(key >= this.table.length) {
return undefined
}
}
return (this.table[key])[1]
}
//delete方法，用来删除哈希表的数据
delete(index) {
let key = this.hashConversion(index)
while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
key ++
if(key >= this.table.length) {
return false
}
}
this.table[key] = new Array(2)
this.size--
return true
}
//has方法，判断哈希表中有没有该值
has(index) {
let key = this.hashConversion(index)
while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
key ++
if(key >= this.table.length) {
return false
}
}
if((this.table[key])[0] !== undefined) {
return true
} else {
return false
}
}
//展示存储到哈希表中的所有数据
showAllData() {
let result = []
for (let item of this.table) {
if(item[0] !== undefined) {
result.push(item)
}
}
return result
}
}
总结
虽然自己封装的哈希表远不如JavaScript中的Map，但是从自己实现该数据结构的过程中也收获了很多。
网友评论