实现HashMap
前言
哈希表存储元素时将key进行hash计算，hash值转成索引后再存储元素
使用链地址法解决哈希冲突问题，如图所示哈希表每一项中再存储一个数组或链表用于存储hash值相同的元素
随着元素的插入和删除，需要对哈希表进行扩容或缩容操作
在这里插入图片描述
实现思路和代码
- 哈希表
function HashTable() {
//容器
this.storage = []
//大小
this.count = 0
//容量
this.limit = 7
}- 哈希函数计算hash值
hashFunc(str, size) {
let hashCode = 0
for(let i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i)
}
let index = hashCode % size
return index
}- 插入、修改元素
put(key, value) {
//获取key对应的索引
let index = hashFunc(key, this.limit)
//获取对应的bucket
let bucket = this.storage[index]
//bucket不存在
if(bucket === undefined) {
//创建空数组放到对应的索引中
bucket = []
this.storage[index] = bucket
}
//修改数据
for(let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if(tuple[0] === key) {
tuple[1] = value
return
}
}
//添加数据
bucket.push([key, value])
this.count += 1
//判断是否需要扩容
if(this.count > this.limit * 0.75) {
//获取新的容量 当前容量的2倍
let newSize = this.limit * 2
//保持当前容量是素数
let newLimit = this.getPrime(newSize)
this.resize(newLimit)
}
}- 获取元素
get(key) {
//获取索引
let index = hashFunc(key, this.limit)
//获取索引对应的元素或数组或链表
let bucket = this.storage[index]
if(bucket === undefined) {
return null
}
//遍历
for(let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if(tuple[0] === key) {
return tuple[1]
}
}
//没找到
return null
}- 删除元素
remove(key) {
//获取索引
let index = hashFunc(key, this.limit)
//获取索引对应的元素或数组或链表
let bucket = this.storage[index]
if(bucket === undefined) {
return null
}
//遍历
for(let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if(tuple[0] === key) {
bucket.splice(i, 1)
this.count -= 1
//判断是否需要缩容
if(this.limit > 7 && this.count < this.limit * 0.25) {
//获取新的容量 是当前容量的一半向下取整
let newSize = Math.floor(this.limit / 2)
//保持新的容量是素数
let newLimit = this.getPrime(newSize)
this.resize(newLimit)
}
return tuple[1]
}
}
return null
}- 是否为空
- 哈希表长度
isEmpty() {
return this.count === 0
}
size() {
return this.count
}- 扩容、缩容
resize(newLimit) {
//指向老容器的引用
let oldStorage = this.storage
//清空当前容器 准备扩容
this.storage = []
this.count = 0
//新容量
this.limit = newLimit
//遍历老容器
for(let i = 0; i < oldStorage.length; i++) {
//获取容器每一项
let bucket = oldStorage[i]
if(bucket === undefined) {
//为空终止本次循环 执行下一次
continue
}
//遍历 老元素添加到新容器中
for(let j = 0; j < bucket.length; j++) {
let tuple = bucket[j]
this.put(tuple[0], tuple[1])
}
}
}- 判断是否是质数
isPrime(num) {
let temp = parseInt(Math.sqrt(num))
for(let i = 0; i < temp; i++) {
if(num % i === 0) {
return false
}
}
return true
}- 获取质数
getPrime(num) {
while(!this.isPrime(num)) {
num++
}
return num
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-04-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
