JavaScript实现哈希表

文章目录

哈希表简介JS实现哈希表完整代码参考资料

---

哈希表简介

基于数组实现

优势：可以快速插入-查找-删除操作

不足：

1. 数据没有顺序，不能以固定顺序遍历 2. key不允许重复

哈希函数：将key转换为index的函数，该过程称为哈希化

哈希表：使用哈希函数转换索引值并进行结构封装的数组

哈希冲突：不同的key使用哈希函数转换后的index相同（不可避免）

解决方法 1. 链地址法：index中一链表或数组的形式存放多条数据（index相同的不同key） 2. 开放地址法：寻找空白的单元格来放置冲突的数据项 + 寻找空白单元格的方式 ++ 线性查找：由得到的index，逐个往后查找（既步长为1） ++ 二次查找：index每次增加pow(i++,2) ++ 再哈希化：有一个新的哈希函数计算步长

装填因子（loadFactor）：总数据项/哈希表长度

链地址法的loadFactor可能 > 1 开放地址法的loadFactor最大为1

---

JS实现哈希表

HashTable类的属性与方法

属性：容量-limit、数据条数-size、数据容器storege 方法：增(改)-put(key, value)、删-remove(key)、查-get(key)

哈希函数hashFunc(key)：使用霍纳算法计算出index

插入数据：包括修改数据的功能 key已经存在哈希表中则修改数据，否则插入数据

根据key计算的index 查看index是否存在数据 若不存在数据，则创建数组，并插入数据 若存在数据，则遍历该数组，是否存在相等的key，存在则替换，不存在则插入

查找数据： 根据key计算的index，查找到则返回对应的值，否则返回null

删除数据 根据key计算的index，查找到则使用slice删除数据，并返回删除的值，否则返回null

扩容问题

当装载因子过大，哈希表的效率会下降，故考虑扩容（loadFactor > 0.75） 当装载因子过小，会造成空间浪费，故考虑缩容（loadFactor < 0.25） 在put操作时，当 loadFactor > 0.75 时扩容 在remove操作时，当 loadFactor < 0.25 时缩容

扩（缩）容函数resize(newLimit)

1. 将原数据指向 oldStorage 2. this.storage 指向空数组 3. 设置 limit 值为 newLimit 4. 遍历 oldStorage 将数据，执行 put 操作 注：newLimit 应该是一个质数

---

完整代码

//封装哈希表类 function HashTable() { //属性 this.storage = [] this.count = 0 //计算已经存储的元素个数 //装填因子：loadFactor > 0.75时需要扩容；loadFactor < 0.25时需要减少容量 //哈希表容量应该为质数，这样取余后，数据在散列表中分布更均匀 this.limit = 7 //初始长度 } //方法 //哈希函数 HashTable.prototype.hashFunc = function(str, size) { //1.定义hashCode变量 let hashCode = 0 //2.霍纳法则，计算hashCode的值 //cats -> Unicode编码 for (let i = 0; i < str.length; i++) { // str.charCodeAt(i)//获取某个字符对应的unicode编码 hashCode = 37 * hashCode + str.charCodeAt(i) } //3.取余操作 let index = hashCode % size return index } //一.插入&修改操作 HashTable.prototype.put = function(key, value) { //1.根据key获取对应的index let index = this.hashFunc(key, this.limit) //2.根据index取出对应的bucket let bucket = this.storage[index] //3.判断该bucket是否为null if (bucket == null) { bucket = [] this.storage[index] = bucket } //4.判断是否是修改数据 for (let i = 0; i < bucket.length; i++) { let tuple = bucket[i]; if (tuple[0] == key) { tuple[1] = value return //不用返回值 } } //5.进行添加操作 bucket.push([key, value]) this.count += 1 //6.判断是否需要扩容操作 if (this.count > this.limit * 0.75) { let newSize = this.limit * 2 let newPrime = this.getPrime(newSize) this.resize(newPrime) } } //二.获取操作 HashTable.prototype.get = function(key) { //1.根据key获取对应的index let index = this.hashFunc(key, this.limit) //2.根据index获取对应的bucket let bucket = this.storage[index] //3.判断bucket是否等于null if (bucket == null) { return null } //4.有bucket，那么就进行线性查找 for (let i = 0; i < bucket.length; i++) { let tuple = bucket[i]; if (tuple[0] == key) { //tuple[0]存储key，tuple[1]存储value return tuple[1] } } //5.依然没有找到，那么返回null return null } //三.删除操作 HashTable.prototype.remove = function(key) { //1.根据key获取对应的index let index = this.hashFunc(key, this.limit) //2.根据index获取对应的bucket let bucket = this.storage[index] //3.判断bucket是否为null if (bucket == null) { return null } //4.有bucket,那么就进行线性查找并删除 for (let i = 0; i < bucket.length; i++) { let tuple = bucket[i] if (tuple[0] == key) { bucket.splice(i, 1) this.count -= 1 //6.缩小容量 if (this.limit > 7 && this.count < this.limit * 0.25) { let newSize = Math.floor(this.limit / 2) let newPrime = this.getPrime(newSize) this.resize(newPrime) } return tuple[1] } } //5.依然没有找到，返回null return null } /*------------------其他方法--------------------*/ //判断哈希表是否为null HashTable.prototype.isEmpty = function() { return this.count == 0 } //获取哈希表中元素的个数 HashTable.prototype.size = function() { return this.count } //哈希表扩容或缩容 HashTable.prototype.resize = function(newLimit) { //1.保存旧的storage数组内容 let oldStorage = this.storage //2.重置所有的属性 this.storage = [] this.count = 0 this.limit = newLimit //3.遍历oldStorage中所有的bucket for (let i = 0; i < oldStorage.length; i++) { //3.1.取出对应的bucket const bucket = oldStorage[i]; //3.2.判断bucket是否为null if (bucket != null) { //3.3.bucket中有数据，就取出数据重新插入 for (let j = 0; j < bucket.length; j++) { const tuple = bucket[j]; this.put(tuple[0], tuple[1]) //插入数据的key和value } } } } //判断传入的num是否质数 HashTable.prototype.isPrime = function(num) { if (num <= 1) { return false } //1.获取num的平方根:Math.sqrt(num) //2.循环判断 for (var i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) { return false; } } return true; } //获取质数的方法 HashTable.prototype.getPrime = function(num) { //7*2=14,+1=15,+1=16,+1=17(质数) while (!this.isPrime(num)) { num++ } return num } let ht = new HashTable() ht.put('class1','Tom') ht.put('class2','Mary') ht.put('class3','Gogo') ht.put('class4','Tony') console.log("Size: " + ht.size()); //10 console.log("Limit: " + ht.limit); //17 console.log(ht);

---

参考资料

JavaScript实现哈希表