哈希表

  • 哈希表通常基于数组实现

  • 哈希表相对于数组的不足： 数据无序； 哈希表的key不允许重复

  • 数组：1.数字进行插入操作时，效率比较低

    ​ 2.数组进行查找操作的效率

    ​ 1),基于索引查找操作效率很高

    ​ 2).基于内容去查找(比如name=’hyp’)效率比较低

​ 3.数组进行删除操作，效率也不高

  • 哈希化：把大数字转化成数组范围内的下标的过程
  • 哈希函数：把单词转成大数字，将大数字实现哈希化的代码放到一个函数中 函数就是哈希函数
  • 哈希表：将数据插入到数组 对结构进行封装
  • 冲突 ： 解决
  • 链地址法 就是每个数组单元中存的不是单个数据 而是一个链条- 通常用数组或者链表实现
  • 开放地址法 寻找空的地方来添加重复的数据
    • 线性探测 index+1 查询到空就停止 注意：删除一个数据项 不可以设置成null 可以特殊处理成（比如-1） 线性探测存在问题：数据连续插入会聚集
    • 二次探测 优化了探测时的步长
    • 再哈希法 将关键字用另一个哈希函数哈希化 将这次哈希化的结果作为步长
      • stepSize=constant-(key%constant)
      • constant是质数，且小于数组的容量
  • 装填因子=总数据项/哈希表长度
  • 链地址法用的比较多
  • 优秀的哈希函数快速计算：霍纳法则 优化多项式 将时间复杂度从O(n^2)降到O(n)
    • 均匀分布： 质数的使用
      • 哈希表的长度
      • N次幂的底数
  • 哈希表的插入和修改操作;
    • 1.根据key获取索引值（通过hashFunc 传入key和limit得到的index能找到桶的位置 ）
    • 目 的：将数据插入到对应的位置
    • 2.根据索引值取出bucket如果桶不存在的话 那么创建一个桶，并且将桶放置在该索引值的位置
    • 3.判断新增还是修改原来的值如果已经有值了，那么就修改值如果没有值， 执行后续的添加操作
    • 4.新增操作
  • 获取方法：
    • 1.根据key获取index
    • 2.根据index获取对应的bucket
    • 3.判断bucket是否为null 如果为null 直接返回null
    • 4.线性查找bucket中每一个key是否等于传入的key如果等于那么直接返回对应的value
    • 5.遍历完以后，依然没有找到对应的key 就直接return null
  • 删除操作：
    • 1.根据key获取index
    • 2.根据index获取bucket
    • 3.判断bucket是否存在 ，不存在直接返回null
    • 4.线性查找bucket 寻找对应数据 删除
    • 5.依然没有找到 那么返回null
  • 哈希表扩容/缩容
    • 比较常见的情况是loadFactor>0.75的时候进行扩容.
    • 比如Java的哈希表就是在装填因子大于0.75的时候, 对哈希表进行扩容.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
//封装哈希表类
 function HashTable() {
   //属性
   this.storage=[]   //作为数组, 数组中存放相关的元素
   this.count=0      //表示当前已经存在了多少的数据
   this.limit=7      //用于标记数组中一共可以存放多少的元素
   //loadFactor=count/limit  loadFactor>0.75要进行扩容  <0.25要让数组变小一点   装载因子
   //方法
   //哈希函数
   HashTable.prototype.hashFunc=function(str,size) {
     //1.定义hashCode变量
     let hashCode=0

     //2.霍纳法则，计算hashCode的值
     //比如单词cats ->js中用的比较多Unicode编码
     for(let i=0;i<str.length;i++){
       hashCode=37 * hashCode + str.charCodeAt(i)  //用的比较多的质数是37
     }
     //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){       //[key,value]
         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){
         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是否为空
     if (bucket==null)return false
     //4.bucket不为空 进行遍历
     for (let i=0;i<bucket.length;i++){
       let tuple= bucket[i]
       if (tuple[0]===key){
         bucket.splice(i,1)
         this. count--
         return tuple[1]
         //缩小容量
         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  null
   }


   //其他方法
   //判断是否为空
   HashTable.prototype.isEmpty=function (){
     return this.count ===0
   }
   //获取元素个数
   HashTable.prototype.size=function (){
     return this.count
   }
   //哈希表扩容
   HashTable.prototype.resize=function (newLimt){
     //1.保存旧的数组的内容
     let oldstorage= this.storage

     //2.重置所有的属性
     this.storage=[]
     this.count=0
     this.limit=newLimt

     //3.遍历oldStorage中所有的bucket
     for(let i=0;i<oldstorage.length;i++){
       //取出对应bucket
       let bucket = oldstorage[i]
       //判断bucket是否为null
       if (bucket ==null){
         continue
       }
       //bucket中有数据，那么取出数据，重新插入
       for(let j=0;j<bucket.length;j++){
         let tuple=bucket[j]
         this.put(tuple[0],tuple[1])
       }
     }
   }
   //判断某个数字是否是质数
   HashTable.prototype.isPrime=function (num){
     //1获取num的平方根
     let temp=parseInt(Math.sqrt(num))

     //2.循环判断
     for(let i = 2;i<=temp;i++){
       if (num % i === 0){
         return false
       }
     }
     return true
   }

   //获取质数的方法
   HashTable.prototype.getPrime=function (num){
     //比如34->37
     while(!this.isPrime(num)){
       num++
     }
     return num
   }
 }

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//测试哈希表
  //1.创建哈希表
  let ht =new HashTable()
  //2.插入数据
  ht.put('abc','123')
  ht.put('cba','321')
  ht.put('nbc','521')
  ht.put('dbc','520')

  //3.获取数据
  console.log(ht.get('nbc'))
  //4.修改方法
  ht.put('nbc','111')
  console.log(ht.get('nbc'))
  ht.put('zzz','645')
  console.log(ht.get('zzz'))
  //5.删除方法
  ht.remove('nbc')
  console.log(ht.get('nbc'))