散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数
理解:举例子,有一学校有几万人,存放每个人的档案,将每个人的名字(key)用哈希函数转换成下标index,根据下标index,把学校的信息(value)存放在storage里,为了避免不同学生的key转换成数字后重叠,storage内的每一个元素,可以使用数组或者链表.就是将index相同的学生,存放在一个数组或者链表内,再存放在下标为index的storage内,
哈希函数设计思路
// 哈希表最终数据;最外层数组-storage;第二层数组bucket(桶);第三层数组用于存放信息,k(key)用来使用哈希函数转换成下标;v(value)存放具体信息
//[[[k,v],[k,v],[k,v]],[[k,v],[k,v]],[[k,v]],[[k,v]]]
//备注
//1)使用数组实现hash表;数组跟链表存放元素效果差不多(都是线性查找).(开发地址没学精)
//2)为什么需要扩容,数据增多,扩宽limit长度,可以增加效率;如果
//limit用质数,目的是为了啥来着,有点忘了
class HsahTable {
constructor(size) {
this.storage = [];//作为我们的数组,用来存放相关的元素
this.count = 0;//表示当前存放了多少数据
//用于标记数组中一共可以存放的元素数量,这个数是用来对数组容量进行限制的。在哈希函数中起到缩小哈希化后的数字的作用，以保证哈希化后的数字能够压缩到合理的在 storage 范围内。
this.limit = size;
};
// 哈希函数
hashFunc(str) {
// 1:定义hashCode变量
let hashCode = 0
//2:霍纳算法,来计算hashCode的值
//cats-->UniCode编码
for (let i = 0; i < str.length; i++) {
//37是取的常用的质数,26个字母加空格为27;往后的质数有31,34,37;这里取37
hashCode = 37 * hashCode + str.charCodeAt(i)//霍斯算法;虽然超简单,但是原理还挺多的
}
let index = hashCode % this.limit;//根据数组的最大长度,压缩hashCode到数组范围(大小)之内
return index
};
//哈希表的插入&修改操作
put(key, value) {
// 1:根据key获取索引值
// 2:根据索引值取出bucket
// 2.1)如果桶不存在,创建桶,并且放置在索引值的位置
//3判断新增还是修改原来的值
//3.1)如果已经有值了,修改值
// 3.2)如果没有值,执行后续的添加操作
// 4:添加操作
// 1:
let index = this.hashFunc(key)
//2
let bucket = this.storage[index]
// 3
if (bucket == null) {
bucket = []
this.storage[index] = bucket
}
// 3.1
for (let i = 0; i < bucket.length; i++) {
if (key == bucket[i][0]) {
bucket[i][1] = value
return
}
}
// 4
bucket.push([key, value])
this.count += 1
//判断是否需要扩容
if(this.count>this.limit*0.75){
this.resize(this.limit*2)
}
};
//获取操作
get(key) {
// 1:根据key获取索引值
//2:根据索引值找到bucket
//3:如果bucket为null;返回null
// 4:判断key是否在bucket内,如果在返回value
// 返回null
let index = this.hashFunc(key)
let bucket = this.storage[index]
if (bucket == null) return null
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] == key) {
return bucket[i][1]//4:返回value
}
}
return null
};
// 删除操作
remove(key) {
// 1:根据key找到索引值
// 2:根据索引值找到bucket
// 3:判断bucket是否存在;没有返回null
// 4:线性查找bucket判断有没有key;有则返回value
// 返回null
let index = this.hashFunc(key)
let bucket = this.storage[index]
if (bucket == null) return null
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] == key) {
bucket.splice(i, 1)
this.count--
// 缩小容量
if(this.count<this.limit*0.25){
this.resize(Math.floor(this.limit/2))
}
return tuple[1]
}
}
// 5:
return null
};
// 其它方法
isEmpty() {
return this.count == 0
};
size() {
return this.count
};
// 哈希表扩容
resize(newSize){
//思路,获取新的limit,然后取出旧的storage内的所有元素,存放在新的storage中
//1:保存旧数组
let oldStorage = this.storage
//2:重置所有的属性
this.storage = []
this.count = 0
this.limit = newSize
//取质数
while(!this.isPrime(this.limit))this.limit++
//3:遍历旧数组中的所有bucket;
for (let i = 0; i < oldStorage.length; i++) {
//取出bucket
let bucket = oldStorage[i]
//判断bucket是否为null
if(bucket == null){
continue
}
//循环bucket,将所有元素从新放置在新的storage中
for (let j = 0; j < bucket.length; j++) {
this.put(bucket[0],bucket[1])
}
}
};
////判断一个数是不是质数
isPrime(num){
//对这个数进行二分,得到一个较小的数
let temp = parseInt(Math.sqrt(num))
for (let i = 2; i <= temp; i++) {
if(num%i == 0)return false
}
return true
}
}
let hashTable = new HsahTable(7)
hashTable.put('abc', "我是abc")
hashTable.put('cba', "我是cba")
hashTable.put('nba', "我是nba")
hashTable.put('mba', "我是mba")
console.log(hashTable)
console.log(hashTable.get('abc'))
console.log(hashTable.get('cba'))
console.log(hashTable.get('nba'))
console.log(hashTable.get('mba'))
console.log(hashTable.get('ddd'))
console.log(hashTable.remove('mba'))
console.log(hashTable)
hashTable.put('mba', "我是mba")
console.log(hashTable)
