参考文章https://blog.csdn.net/weixin_46862327/article/details/134176813哈希表哈希表的结构就是数组但它神奇之处在于对下标值的一种变换下标不是直接对应内容值的。实现这种变换的过程我们称之为哈希函数哈希函数是传入需要存储的数据的key(一般是字符串)转变成幂大数使用秦久韶算法可以以37作为幂最后再将幂大数哈希化为下标。哈希表存储的数据一般是key,value组成的数据key是唯一的标识把key带入到哈希函数可以获取到应该存储到的数组下标然后将[key, value]以数组的格式存储到该下标对应的空间中。所以哈希表一般是3维数组eg[[[class2,Mary]],[[class3,Gogo]],[[class4,Vibi]],3empty items,[[class1,TomTom]]]哈希表的结构哈希表的实现1哈希函数//设计哈希函数//1.将字符串转成比较大的数字hashCede//2.将大的数字hasCode压缩到数组范围(大小)之内functionhashFunc(str,size){//1.定义hashCode变量lethashCode0//2.霍纳法则计算hashCode的值//cats - Unicode编码for(leti0;istr.length;i){// str.charCodeAt(i)//获取某个字符对应的unicode编码hashCode37*hashCodestr.charCodeAt(i)}//3.取余操作letindexhashCode%sizereturnindex}2创建哈希表//封装哈希表类functionHashTable(){//属性this.storage[]this.count0//计算已经存储的元素个数//装填因子loadFactor 0.75时需要扩容loadFactor 0.25时需要减少容量this.limit7//初始长度//方法//哈希函数HashTable.prototype.hashFuncfunction(str,size){//1.定义hashCode变量lethashCode0//2.霍纳法则计算hashCode的值//cats - Unicode编码for(leti0;istr.length;i){// str.charCodeAt(i)//获取某个字符对应的unicode编码hashCode37*hashCodestr.charCodeAt(i)}//3.取余操作letindexhashCode%sizereturnindex}}3添加修改获取删除操作//封装哈希表类functionHashTable(){//属性this.storage[]this.count0//计算已经存储的元素个数//装填因子loadFactor 0.75时需要扩容loadFactor 0.25时需要减少容量this.limit7//初始长度//方法//哈希函数HashTable.prototype.hashFuncfunction(str,size){//1.定义hashCode变量lethashCode0//2.霍纳法则计算hashCode的值//cats - Unicode编码for(leti0;istr.length;i){// str.charCodeAt(i)//获取某个字符对应的unicode编码hashCode37*hashCodestr.charCodeAt(i)}//3.取余操作letindexhashCode%sizereturnindex}//插入修改操作HashTable.prototype.putfunction(key,value){//1.根据key获取对应的indexletindexthis.hashFunc(key,this.limit)//2.根据index取出对应的bucketletbucketthis.storage[index]//3.判断该bucket是否为nullif(bucketnull){bucket[]this.storage[index]bucket}//4.判断是否是修改数据for(leti0;ibucket.length;i){lettuplebucket[i];if(tuple[0]key){tuple[1]valuereturn//不用返回值}}//5.进行添加操作bucket.push([key,value])this.count1}//获取操作HashTable.prototype.getfunction(key){//1.根据key获取对应的indexletindexthis.hashFunc(key,this.limit)//2.根据index获取对应的bucketletbucketthis.storage[index]//3.判断bucket是否等于nullif(bucketnull){returnnull}//4.有bucket那么就进行线性查找for(leti0;ibucket.length;i){lettuplebucket[i];if(tuple[0]key){//tuple[0]存储keytuple[1]存储valuereturntuple[1]}}//5.依然没有找到那么返回nullreturnnull}//删除操作HashTable.prototype.removefunction(key){//1.根据key获取对应的indexletindexthis.hashFunc(key,this.limit)//2.根据index获取对应的bucketletbucketthis.storage[index]//3.判断bucket是否为nullif(bucketnull){returnnull}//4.有bucket,那么就进行线性查找并删除for(leti0;ibucket.length;i){lettuplebucket[i]if(tuple[0]key){bucket.splice(i,1)this.count-1returntuple[1]}}//5.依然没有找到返回nullreturnnull}//判断哈希表是否为nullHashTable.prototype.isEmptyfunction(){returnthis.count0}//获取哈希表中元素的个数HashTable.prototype.sizefunction(){returnthis.count}}//测试哈希表//1.创建哈希表lethtnewHashTable()//2.插入数据ht.put(class1,Tom)ht.put(class2,Mary)ht.put(class3,Gogo)ht.put(class4,Tony)ht.put(class4,Vibi)console.log(ht.storage);// 获取数据ht.get(class2)console.log(ht.storage);// 删除数据ht.remove(class2)console.log(ht.storage);哈希表的扩容随着数据量的增多storage中每一个index对应的bucket数组链表就会越来越长这就会造成哈希表效率的降低这个时候就需要进行扩容。1扩容方法//哈希表扩容HashTable.prototype.resizefunction(newLimit){//1.保存旧的storage数组内容letoldStoragethis.storage//2.重置所有的属性this.storage[]this.count0this.limitnewLimit//3.遍历oldStorage中所有的bucketfor(leti0;ioldStorage.length;i){//3.1.取出对应的bucketconstbucketoldStorage[i];//3.2.判断bucket是否为nullif(bucketnull){continue}//3.3.bucket中有数据就取出数据重新插入for(letj0;jbucket.length;j){consttuplebucket[j];this.put(tuple[0],tuple[1])//插入数据的key和value}}}2装填因子(loadFactor)装填因子 哈希表中数据 / 哈希表长度通常情况下当装填因子laodFactor 0.75时对哈希表进行扩容。在哈希表中的添加方法push方法中添加如下代码判断是否需要调用扩容函数进行扩容//判断是否需要扩容操作if(this.countthis.limit*0.75){this.resize(this.limit*2)}当装填因子laodFactor 0.25时对哈希表容量进行压缩。在哈希表中的删除方法remove方法中添加如下代码判断是否需要调用扩容函数进行压缩//缩小容量if(this.limit7this.countthis.limit*0.25){this.resize(Math.floor(this.limit/2))}哈希表的常量一般采用质数为HashTable类添加判断质数的isPrime方法和获取质数的getPrime方法//判断传入的num是否质数HashTable.prototype.isPrimefunction(num){if(num1){returnfalse}//1.获取num的平方根:Math.sqrt(num)//2.循环判断for(vari2;iMath.sqrt(num);i){if(num%i0){returnfalse;}}returntrue;}//获取质数的方法HashTable.prototype.getPrimefunction(num){//7*214,115,116,117(质数)while(!this.isPrime(num)){num}returnnum}使用在put方法中添加如下代码//判断是否需要扩容操作if(this.countthis.limit*0.75){let newSizethis.limit*2let newPrimethis.getPrime(newSize)this.resize(newPrime)}在remove方法中添加如下代码//缩小容量if(this.limit7this.countthis.limit*0.25){let newSizeMath.floor(this.limit/2)let newPrimethis.getPrime(newSize)this.resize(newPrime)}哈希表的全部实现//封装哈希表类functionHashTable(){//属性this.storage[]this.count0//计算已经存储的元素个数//装填因子loadFactor 0.75时需要扩容loadFactor 0.25时需要减少容量this.limit7//初始长度//方法//哈希函数HashTable.prototype.hashFuncfunction(str,size){//1.定义hashCode变量lethashCode0//2.霍纳法则计算hashCode的值//cats - Unicode编码for(leti0;istr.length;i){// str.charCodeAt(i)//获取某个字符对应的unicode编码hashCode37*hashCodestr.charCodeAt(i)}//3.取余操作letindexhashCode%sizereturnindex}//一.插入修改操作HashTable.prototype.putfunction(key,value){//1.根据key获取对应的indexletindexthis.hashFunc(key,this.limit)//2.根据index取出对应的bucketletbucketthis.storage[index]//3.判断该bucket是否为nullif(bucketnull){bucket[]this.storage[index]bucket}//4.判断是否是修改数据for(leti0;ibucket.length;i){lettuplebucket[i];if(tuple[0]key){tuple[1]valuereturn//不用返回值}}//5.进行添加操作bucket.push([key,value])this.count1//6.判断是否需要扩容操作if(this.countthis.limit*0.75){letnewSizethis.limit*2letnewPrimethis.getPrime(newSize)this.resize(newPrime)}}//二.获取操作HashTable.prototype.getfunction(key){//1.根据key获取对应的indexletindexthis.hashFunc(key,this.limit)//2.根据index获取对应的bucketletbucketthis.storage[index]//3.判断bucket是否等于nullif(bucketnull){returnnull}//4.有bucket那么就进行线性查找for(leti0;ibucket.length;i){lettuplebucket[i];if(tuple[0]key){//tuple[0]存储keytuple[1]存储valuereturntuple[1]}}//5.依然没有找到那么返回nullreturnnull}//三.删除操作HashTable.prototype.removefunction(key){//1.根据key获取对应的indexletindexthis.hashFunc(key,this.limit)//2.根据index获取对应的bucketletbucketthis.storage[index]//3.判断bucket是否为nullif(bucketnull){returnnull}//4.有bucket,那么就进行线性查找并删除for(leti0;ibucket.length;i){lettuplebucket[i]if(tuple[0]key){bucket.splice(i,1)this.count-1returntuple[1]//6.缩小容量if(this.limit7this.countthis.limit*0.25){letnewSizeMath.floor(this.limit/2)letnewPrimethis.getPrime(newSize)this.resize(newPrime)}}}//5.依然没有找到返回nullreturnnull}/*------------------其他方法--------------------*///判断哈希表是否为nullHashTable.prototype.isEmptyfunction(){returnthis.count0}//获取哈希表中元素的个数HashTable.prototype.sizefunction(){returnthis.count}//哈希表扩容HashTable.prototype.resizefunction(newLimit){//1.保存旧的storage数组内容letoldStoragethis.storage//2.重置所有的属性this.storage[]this.count0this.limitnewLimit//3.遍历oldStorage中所有的bucketfor(leti0;ioldStorage.length;i){//3.1.取出对应的bucketconstbucketoldStorage[i];//3.2.判断bucket是否为nullif(bucketnull){continue}//3.3.bucket中有数据就取出数据重新插入for(letj0;jbucket.length;j){consttuplebucket[j];this.put(tuple[0],tuple[1])//插入数据的key和value}}}//判断传入的num是否质数HashTable.prototype.isPrimefunction(num){if(num1){returnfalse}//1.获取num的平方根:Math.sqrt(num)//2.循环判断for(vari2;iMath.sqrt(num);i){if(num%i0){returnfalse;}}returntrue;}//获取质数的方法HashTable.prototype.getPrimefunction(num){//7*214,115,116,117(质数)while(!this.isPrime(num)){num}returnnum}}