关于数据结构和算法:数据结构与算法学习哈希表下

30次阅读

共计 2886 个字符，预计需要花费 8 分钟才能阅读完成。

下面的一篇文章曾经为这篇文章做了很好的铺垫，让咱们意识了哈希表。那么咱们来认识一下什么是扩容。扩容顾名思义就是扩充容量的意思。咱们上面会封装 3 个办法包含，put(新增 / 批改数据)，get(获取数据)，remove(删除数据)。下面咱们曾经提到了先定义一个固定长度的数组。既然是固定长度那么当咱们在不晓得减少多少的状况下这时候就用到了扩容。本篇文章是基于链地址法来实现的哈希表。

什么状况下扩容呢？
比方常见的状况是 loadFactor（填充因子）>0.75 的时候，对哈希表进行扩容

为什么须要扩容？
目前，咱们是将所有的数据项放在长度为 7 的数组中
因为咱们应用的是链地址法，loadFactor(填充因子)能够大于 1，所以这个哈希表能够无限度的插入新数据
然而，随着数据量的增多，每一个 index 对应的 bucket 会越来越长，也就造成效率的升高
所以在适合的状况对数组进行扩容，比方扩容两倍

如何扩容？
扩容能够将简略的将容量增大两倍（不是质数吗？质数问题前面在探讨）
然而这种状况下，所有的数据项肯定要同时进行批改（从新调用哈希函数，来获取到不同的地位）
比方 hashCode=12 的数据项，在 length= 8 的时候，index=4 在长度为 16 的时候呢？index=12
这是一个耗时的过程，然而如果数组须要扩容，那么这个过程是必要的

在写办法之前咱们须要用到检测质数的办法，这样能够用于数组扩容之后的长度为质数从而解决元素的汇集问题；
那么咱们先来看一看一般检测

function isPrimeHigh(num) {for (let i = 2; i < num; i++) {if (num % i === 0) {return false}
  }
  return true
}

下面这种办法是能够失常检测的，然而他的效率很慢，如果是一个比拟小的数还是很好的，然而如果传进去的是一个大的数字那么就很慢了。

高效的检测质数办法

// 利用开方的办法 例如以下的 12
//  2 * 6 = 12
//  3 * 4 = 12
//  Math.sqrt(num)*Math.sqrt(num)=12
//  4 * 3 = 12
//  6 * 2 = 12
// 循环时只需循环到 Math.sqrt(num)(这里通过 parseInt 函数获得的是 3), 因为 Math.sqrt(num)前面的乘法就相当于 Math.sqrt(num)后面反过来一样, 所以如果后面的不能被整除前面的肯定不能被整除
/* 拿 13 举例：parseInt(Math.sqrt(13)) = 3；i= 2 时 13 % 2 = 1；i= 3 时 13 % 3 = 1; 下面的流程没有进到办法，所以返回 true*/
function isPrime(num) {let temp = parseInt(Math.sqrt(num));
  for (let i = 2; i <= temp; i++) {
    // i=2   12 % 2 = 0 那么间接返回 false
 if (num % i == 0) {return false}
  }
  return true
}

删除办法和上图逻辑大体一致

class HashTable {constructor() {this.storage = [];
    this.count = 0;
    this.limit = 7;
  }
  // 获取关键字对应的索引
 hashCode(str, size) {
    let hashCode = 0;
    // 秦九韶算法依据传递进来的 key 值的每个字符当做关键字传进来这样缩小抵触
 for (let i = 0; i < str.length; i++) {
      //37 是一个罕用的质数
 hashCode = hashCode * 37 + str[i].charCodeAt()}
    // 将一个比拟大的数压缩为比拟小的数字作为索引
 return hashCode % size
  }
  // 新增 / 批改办法
 put(key, val) {let index = this.hashCode(key, this.limit);
    let bucket = this.storage[index];
    if (bucket && bucket.length > 0) {for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];
        if (tuple[0] === key) {tuple[1] = val;
          return
 }
      }
    } else {bucket = [];
      this.storage[index] = bucket;
    }
    bucket.push([key, val]);
    this.count += 1;
    if (this.count / this.limit > 0.75) {this.expansion(Math.floor(this.limit * 2))
    }
  }
  // 获取元素
 get(key) {let index = this.hashCode(key, this.limit);
    let bucket = this.storage[index];
    if (bucket && bucket.length > 0) {for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];
        if (tuple[0] === key) {return tuple[1]
        }
      }
    } else {return null;}
  }
  // 删除元素
 remove(key) {let index = this.hashCode(key, this.limit);
    let bucket = this.storage[index];
    if (bucket && bucket.length > 0) {for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];
        if (tuple[0] === key) {let currentVal = tuple[1];
          bucket.splice(i, 1);
          this.count -= 1;
          if (this.count / this.limit < 0.75 && this.limit > 7) {this.expansion(Math.floor(this.limit / 2))
          }
          return currentVal;
        }
      }
    } else {return null;}
  }
  // 扩容以及将定义的数组长度转成质数
 expansion(newSize) {
    let oldStorage = this.storage;
    this.storage = [];
    this.count = 0;
    this.limit = newSize;
    while (!this.isPrime(this.limit)) {this.limit += 1;}
    for (let i = 0; i < oldStorage.length; i++) {let bucket = oldStorage[i];
      if (!bucket || bucket.length < 1) continue;
      for (let j = 0; j < bucket.length; j++) {let tuple = bucket[j];
        this.put(tuple[0], tuple[1])
      }
    }
  }
  // 判断是否是一个质数
 isPrime(num) {let power = Math.sqrt(num);
    for (let i = 2; i <= power; i++) {if (num % i === 0) {return false}
    }
    return true
 }
}

正文完