一、 哈希表的介绍
1. 哈希表的优势
哈希表通常是基于数组实现的，但相对于数组，它有很多优势
- 快速的插入、删除、查找操作， 时间复杂度接近常量值，时间复杂度为 O(1)
- 哈希表的速度比树还要快，代码相对树来说简单很多
2. 哈希表的缺点
- 哈希表中的数据没有顺序，因此不能通过固定的方式遍历元素
- 哈希表是通过空间来换取时间是数据结构，通过占用更多的内存空间来提高操作效率
哈希表的实现是基于数组的下标值的一种变换，这种变换通过哈希函数实现
3. 哈希表的一些概念
- 哈希化： 将大数字转化为数组范围内下标的过程，我们称之为哈希化
- 哈希函数：大数字在进行哈希化的实现逻辑，封装在一个函数中，我们称这个函数为哈希函数
- 哈希表：通过哈希函数得到下标，并将数据插入到数组中，以及其它操作，对整个结构的封装，我们称之为哈希表
4. 解决冲突的方法
通过哈希函数得到的下标值，有可能会重复, 常见有两种解决方案
- 链地址法(也叫拉链法)
- 开放地址法
5. 链地址法
示意图：
hash_link.jpg
当哈希表产生冲突时，链地址法是常见的解决冲突的方法，数组中不再存储单一的值，也是存储一个链表(或数组)，将冲突的值依次追加到链表(或数组)中即可
6. 开发地址法
开发地址法的主要工作方式是寻找空白的位置来添加重复的数据
寻找空白位置，有三种不同的方法
- 线性探测:
- 插入元素产生冲突时，也就是位置上已经存在元素，以步长为 1，往后寻找空白位置，并插入数据
- 线性探测，在插入连续的数据时，会产生聚集，导致冲突数据位置之间的距离很远，影响哈希表的操作效率
- 二次探测
- 二次探测对步长做了优化，比如下标从 x 开始，那么步长可以是 x + 1, x + 2^2, x + 3^3 ......, 这样探测的距离比较远，可以避免连续数据产生的聚集问题
- 二次探测的问题是，不断的插入连续的数据，也会产生步长不一的聚集
- 效率比线性探测高
- 再哈希法
- 为了解决，线性探测和二次探测可能产生的聚集问题，我们可以使用再哈希法
- 再哈希法，是使用数据的关键字，用另一个哈希函数，再做一次哈希，用这次哈希化的结果作为步长
- 再哈希函数的算法
- stepSize = constant - (key % constant)
- constant 为小于数组长度的质数
- key 数据的关键字
开发地址法中查找元素时，也需要安装步长线性查找，但遇到空白位置时，就可以停止查找
开发地址法中删除元素时，不能直接把该元素的位置设为 null, 否则会影响查找操作，应该设置成一个特殊值，当查找时，遇到这个值，才能知道，后面可能还有查找的相关数据
7. 哈希化的效率
填充因子 = 总数据项 / 哈希表长度
开发地址法的填充因子，最大值为 1
链地址法的填充因子可以大于 1， 因为数组中存放的是链表，链表上又可以添加多个数据
探测次数与填充因子有关，随着填充因子的增长, 需要探测的次数会越来越多
开发地址法中， 线性探测的效率最低， 二次探测和再哈希法的效率差不多， 这三种算法的探测次数都随着填充因子的增大，呈现指数增长的趋势
链地址法，随填充因子的增大，探测次数与填充因子，呈现线性增长的趋势
因此，链地址法的效率比开放地址法的效率高很多
二、 哈希函数
1. 优秀的哈希函数
一个好的哈希函数，应该满足：
- 尽可能小的计算量(使用霍纳法则)
- 哈希化的结果，使得元素可以均匀分布在数组中
2. 霍纳法则
用于对多项式求值问题
表达式： Pn(x)= anx^n + a(n－1)x^(n-1) + … + a1x + a0 (时间复杂度为 O(n^2))
霍纳法则表示法： ((…(((anx + an － 1)x + an － 2)x + an －3)…)x + a1)x + a0 (时间复杂度为 O(n))
关于霍纳法则，需要去了解其相关介绍
3. 质数的使用
使用质数可以使数据尽可能均匀的分布
使用质数的地方有
- 数组的长度
- 幂的底数
4. 代码实现
function hashFunc(str, max) {
let hashCode = 0;
const primeNum = 37; // 质数
// 霍纳法则，计算 hashCode
for (let i = 0; i < str.length; i++) {
hashCode = primeNum * hashCode + str.charCodeAt(i);
}
return hashCode % max;
}
三、哈希表的实现
class HashTable {
constructor() {
this.storage = [];
this.count = 0;
this.limit = 7; // 默认数组长度
}
// 判断是否是质数
isPrime(num) {
const temp = Math.floor(Math.sqrt(num));
for (let i = 2; i <= temp; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
// 获取质数
getPrime(num) {
while (!this.isPrime(num)) {
num += 1;
}
return num;
}
// 哈希函数
hashFunc(str, max) {
let hashCode = 0;
// 霍纳算法
for (let i = 0; i < str.length; i++) {
hashCode = hashCode * 37 + str.charCodeAt(i);
}
return hashCode % max;
}
// 插入数据
put(key, value) {
// 通过哈希函数计算数组下标
const index = this.hashFunc(key, this.limit);
let bucket = this.storage[index];
if (!bucket) {
// 计算得到的下标还未存放数据
bucket = [];
this.storage[index] = bucket;
}
let isOverwrite = false; // 是否为修改操作
for (const tuple of bucket) {
// 循环判断是否为修改操作
if (tuple[0] === key) {
tuple[1] = value;
isOverwrite = true;
}
}
if (!isOverwrite) {
// 不是修改操作，执行插入操作
bucket.push([key, value]);
this.count++;
// 如果填充因子大于 0.75 需要对数组进行扩容
if (this.count / this.length > 0.75) {
const primeNum = this.getPrime(this.limit * 2);
this.resize(primeNum);
}
}
}
// 获取数据
get(key) {
const index = this.hashFunc(key, this.limit);
const bucket = this.storage[index];
if (!bucket) {
return null;
}
for (const tuple of bucket) {
if (tuple[0] === key) {
return tuple[1];
}
}
}
// 删除数据
remove(key) {
const index = this.hashFunc(key, this.limit);
const bucket = this.storage[index];
if (!bucket) {
return null;
}
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
if (tuple[0] === key) {
bucket.splice(i, 1);
this.count -= 1;
// 如果填充因子小于0.25，需要缩小数组容量
if (this.count / this.limit < 0.25 && this.limit > 7) {
const primeNum = this.getPrime(Math.floor(this.limit / 2));
this.resize(primeNum);
}
return tuple[1];
}
}
return null;
}
// 重新设置数组长度
resize(newLimit) {
const oldStorage = this.storage;
this.limit = newLimit;
this.count = 0;
this.storage = [];
// 将旧数据从新添加到哈希表中
oldStorage.forEach((bucket) => {
if (!bucket) {
return;
}
for (const tuple of bucket) {
this.put(...tuple);
}
});
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
}
网友评论