JavaScript(ES6)数据结构与算法之哈希表

5. 哈希表（散列表/字典）

5.1 概念

• 基于数组实现，存放键值对：结构是数组，对输入的键进行变换（哈希函数）得到HashCode
• 解决冲突（不同下标值HashCode相同）
  • 链地址法（常用）：每个数组单元存储数组或链表，出现相同映射就链式延伸添加
  • 开放地址法（少）：寻找空白单元格（线性探测、二次探测、再哈希法）来添加重复的数据，可能会扩容
• 优势：
  • 非常快速的插入删除查找操作
  • 速度比树快，编码比树容易
• 劣势：
  • 数据没有顺序，不能按大小等遍历
  • key不允许重复
• 装填因子：
  • 装填因子=总数据项/哈希表长度
  • 装填因子越大，探测长度越长，哈希表插入和搜索效率降低，链地址法随装填因子改变，效率改变更小，因此更常被采用
  • 链地址法装填因子可以大于1，开放地址法装填因子最大为1
• 设计哈希函数
  • 快速计算，多项式的优化：霍纳法则（秦九韶算法），降低时间复杂度从O(N^2)到O(N)
  • 均匀分布：使用常量的地方，尽量使用质数

5.2 哈希表的实现

• 常见方法：

  • 存放元素
  • 获取元素
  • 删除元素
  • 哈希表扩容

• 封装

  export class HashTable{
      constructor(){
          this.storage=[]//数组存储元素
          this.count=0;//当前存放了多少个元素
          this.limit=8;//容量
      }
      
      //哈希函数
      hashFunc(str,max){
          //1.定义hashCode
          let hashCode = 0;
          //2.霍纳算法
          for(let i=0;i<str.length;i++){
              hashCode = 31*hashCode + str.charCodeAt(i);
          }
          hashCode = hashCode%max;
          
          return hashCode;
      }
      
      //存放元素方法
      put(key,value){
          //1.根据key映射到index
          const index = this.hashFunc(key,this.limit);
          
          //2.取出数组
          //storage的每个index都可以有一个bucket
          let bucket = this.storage[index];
          if(bucket === undefined){
              bucket = [];
              this.storage[index] = bucket;
          }
          //3.判断是插入还是修改操作
          let overwride = false;
          for(let i = 0;i<bucket.length;i++){
              let tuple = bucket[i];
              //bucket是二维数组，一个放key，一个放value
              if(tuple[0] === key){
                  tuple[1]=value;
                  overwride = true;
              }
          }
          //4.如果没有覆盖（没有该key），则新增
          if(!overwride){
              bucket.push([key,value]);
              this.count++;
          }
          
          
      }
      
      //获取元素方法
      get(key){
          //1.根据key获得Index
          const index = this.hashFunc(key,this.limit);
          
          //2.获得bucket
          const bucket = this.storage[index];
          if(bucket === undefined){
              return null;
          }
          
          //3.遍历bucket,一个个查找
          for(let i = 0;i<bucket.length;i++){
              let tuple = bucket[i];
              if(tuple[0] === key){
                  return tuple[1];
              }
          }
          //4.遍历完，没有找到则返回null
          return null；
      }
      
      //删除元素方法
      remove(key){
          //1.根据key获得index
          const index = rhis.hashFunc(key,this.limit);
          
          //2.获得bucket
          const bucket = this.storage[index];
          if(bucket === undefined){
              return null;
          }
          
          //3.遍历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]
              }
          }
      }
      
      isEmpty(){
          return this.count===0;
      }
      
      size(){
          return this.count;
      }
      
  }
  

5.3 扩容

装填因子过大会降低操作效率，这时可以考虑扩容，扩容后所有数据项都需要修改，因为扩容后哈希函数计算的index会改变

常见情况是loadFactor>0.75（如java）时进行扩容

• 哈希表的扩容(也可能缩小容量)

  resize(newLimit){
      //1.保留原数组中的内容
      let oldStorage = this.storage;
      
      //2.重置属性
      this.limit = newLimit;
      this.storage = [];
      this.count = 0;
      
      //3.取出oldStorage所有的元素，重新放入到storage
      oldStorage.forEach((bucket)=>{
          if(bucket === null){
              return
          }
          for(let i = 0;i<bucket.length;i++){
              let tuple = bucket[i];
              //直接调用put方法，limit已经更新了
              this.put(tuple[0],tuple[1])
          }
      })
      
  }
  

  在put方法和remove方法中调用

  const MAX_LOAD_FACTOR = 0.75;
  const MIN_LOAD_FACTOR = 0.75;
  
  put(key,value){
      //略
      if(!overwride){
          bucket.push([key,value]);
          this.count++;
          
          if(this.count>this.limit*MAX_LOAD_FACTOR){
              this.resize(this.limit*2);
          }
      }
      
  }
  
  remove(key){
      //略
      for(let i = 0;i<bucket.length;i++){
          let tuple = bucket[i];
          if(tuple[0] === key){
              bucket.splice(i,1);
              this.count--;
              
              
   //设置容量不小于8
              if(this.limit>8&&this.count<this.limit*MIN_LOAD_FACTOR){
                  this.resize(Math.floor(this.limit/2))
              }
          }
          return tuple[1];
      }
  }
  

• 判断数字是否为质数（素数）

  容量最好是质数，大于1的自然数中，只能被1和自己整除的数

  //如果一个数可以被大于其平方根的整数整除，那么一定也可以被小于其平方根的整数整除
  //添加方法判断
  isPrime(num){
      //1.获取平方根，向上取整
      var temp = Math.ceil(Math.sqrt(num))
      for(let i=2;i<=temp;i++){
          if(num%i===0){
              return true;
          }    
      }
      return false;
  }
  

• 扩容为质数

  //添加方法获得质数
  getPrime(num){
      while(!isPrime(num)){
          num++;
      }
      return num;
  }
  
  //修改put 
  let newLimit = this.getPrime(this.limit*2);
  this.resize(newLimit)
  //修改remove
  let newLimit = this.getPrime(Math.floor(this.limit/2));
  this.resize(newLimit)