哈希表的特点：
1、哈希表也是一个数据结构 并且它是JS对象的原形， 不用想的太复杂。
2、哈希表的内部实现是基于数组的，一般是一key value 键值对的形式保存在数据结构中，且哈希表的性能比数组和链表都要更高，最大的优势是速度。
3、封装哈希表需要封装哈希函数，封装哈希函数需要了解哈希化的理论
一、设计哈希函数 把任意长度的输入转化为固定长度的输出
// 一、将字符串转为大数字 ：hashCode ，利用charCodeAt传入单个字符下标值 拿到unicode编码
// 二、将大数字进行压缩到数组范围之内
function hashFunc(str, size) {
// 1、定义hashCode
let hashCode = 0
//2、霍纳算法变化后乘法次数和加法次数都变成了循环次数
for (let i in str) {
hashCode = hashCode * 37 + str.charCodeAt(i) //需要大数字来减少冲突率 所以需要用到霍纳算法
}
//3、取模 获取压缩下标值
let index = hashCode % size
return index
}
console.log(hashFunc('abc', 7)) //4
console.log(hashFunc('cba', 7)) //3
console.log(hashFunc('asdasdsd', 7)) //5
console.log(hashFunc('cdasdasasba', 7)) //6
二、封装哈希表
// 封装哈希表类
function hashTable() {
// 定义默认属性
// 数组 哈希表的基础
this.storage = []
// 哈希表中元素个数
this.count = 0
// 哈希表中数组长度
this.limit = 7
// 封装哈希函数
this.hashFunc = function (str, size) {
// 1、定义hashCode
let hashCode = 0
//2、霍纳算法变化后乘法次数和加法次数都变成了循环次数
for (let i in str) {
hashCode = hashCode * 37 + str.charCodeAt(i) //需要大数字来减少冲突率 所以需要用到霍纳算法
}
//3、取模 获取压缩下标值
let index = hashCode % size
return index
}
// 插入&&删除操作
this.put = function (key, value) {
// 1、获取key下标
let index = this.hashFunc(key, this.limit)
// 2、桶不再创建桶 桶在进行后续操作
let bucket = this.storage[index]
if (!bucket) {
bucket = []
this.storage[index] = bucket
}
// 3、判断是否存在key值，存在进行修改，不存在进行添加
for (let i in bucket) {
let targetArr = bucket[i]
if (targetArr[0] === key) {
targetArr[1] = value
return true
}
}
bucket.push([key, value])
this.count += 1
if (this.count > 0.75 * this.limit) {
newLimit = this.limit * 2
newPrime = this.getPrime(newLimit)
this.resize(newPrime)
}
}
//根据key查询value操作
this.get = function (key) {
// 1、根据key获取桶的index
let index = this.hashFunc(key, this.limit)
let bucket = this.storage[index]
// 2、判断桶是否为空 为空终止 不为空继续
if (!bucket) return null
// 3、遍历桶 一一对比
for (let i in bucket) {
let targetArr = bucket[i]
if (targetArr[0] === key) {
return targetArr[1]
}
}
// 没找到
return null
}
//根据key删除元素操作
this.remove = function (key) {
let index = this.hashFunc(key, this.limit)
let bucket = this.storage[index]
if (!bucket) return null
for (let i in bucket) {
let targetArr = bucket[i]
if (targetArr[0] === key) {
bucket.splice(i, 1)
this.count -= 1
// 不能太小
if (this.count < 0.25 * this.limit && this.limit > 7) {
newLimit = Math.floor(this.limit / 2)
newPrime = this.getPrime(newLimit)
this.resize(newPrime)
}
return targetArr[i]
}
}
return null
}
//哈希表的扩容/缩容操作
// 思路：1、需要把原来的数据全部取出，并保存到新的数组中 防止扩容后哈希函数返回的值变化 影响所有的位置 导致错误
// 2、在数据增加的时候判断装填因子的大小调用扩容 在数据减少的时候减少缩容
this.resize = function (newLimit) {
let oldStorage = this.storage
let storage = []
let limit = newLimit
let count = 0
for (let i in oldStorage) {
let bucket = oldStorage[i]
// 有一个没值
if (!bucket[i]) {
continue
}
for (let j in bucket) {
let targetArr = bucket[j]
if (!targetArr) {
continue
}
// 这里的put方法里的storage是新的storage了，并且put方法会帮你升成bucket
this.put(targetArr[0], targetArr[1])
}
}
}
// 质数判断
this.isPrime = function (num) {
let temp = parseInt(Math.sqrt(num))
for (let i = 2; i <= temp; i++) {
if (num % i === 0) {
return false
}
}
return true
}
// 获取质数
this.getPrime = function (num) {
while (!this.isPrime(num)) {
num += 1
}
return num
}
//isEmpty方法 和count方法 返回长度 很简单
}
// 上述方法调试都成功
// const hashtable = new hashTable()
// hashtable.put('name', '王大锤')
// hashtable.put('age', 18)
// console.log(hashtable.get('name'))
// console.log(hashtable.get('age'))
总结：
1、哈希化把大数字转化的时间复杂度变成了O（N），哈希函数利用了哈希化和哈希表的长度输出了固定范围的index
2、哈希表的难点在于扩容，哈希表的扩容需要先把旧数据进行一个保存，再创建一个新的哈希表，并且属性需要重新定义/继承。一般在装载因子大于0.75和小于0.25时进行扩/缩容
3、哈希表的数组长度最好为质数
