哈希表
Chao 工程师
  2019-11-26 14:45:00 2019-11-26 14:45   2023-07-19 21:40:40      4.3k Words  16 Mins  

一、哈希表 vs 数组

哈希表：

基于数组进行实现的，相对于数组，有很多优势。

  1. 提供 非常==快速的插入-删除-查找==操作。
  2. 无论多少数据，插入和删除值需要接近常量的时间：即O(1)的时间级。实际上只需要几个机器指令即可完成。
  3. 哈希表的 ==速度 比 树== 还要快，基本可以瞬间查找到想要的元素。
  4. 哈希表相对于 树 来说==编码要容易==的很多。
  5. 哈希表的结构就是==数组，对下标值的一种变换==，这种变换称之为==哈希函数==，通过哈希函数可以获得HashCode;

相对于数组的不足：

  1. 数据没有顺序，不能以一种固定的方式（比如从小大）来遍历其中的元素
  2. 通常情况下，哈希表中的key是不允许充重复的，不能放置相同的key，用于保存不同的元素

数组查找效率：

  1. 如果是基于索引进行查找，效率非常高
  2. 如果是基于内容查找(name=’why’)，效率比较低
  3. 进行删除操作，效率也不高

二、哈希表

自定义编码：

  1. 规则：用1表示a，用26表示z，用0表示空格

  2. 字母转数组：

    2.1 数组相加。

  • 方法：cats = 3 + 1 + 20 + 19 = 43;
  • 问题：很多单词的数字之和都相同，会造成数据覆盖。
  • 结果：数组下标太少

​ 2.2 ==幂的连乘==。

  • 方法：7654 = 710^3 + 610^2 + 5*10 + 4;（基本保证唯一性）

  • 问题：

    • 单词太长，得到的结果非常大，数组能否表示这么大的下标值吗？
    • 就算能够创建这么大的数组，实时上有很多是无效的单词
    • 创建这么大的数组时没有意义的、

  • 结果：数组下标太多

  • 改进：压缩范围，将巨大的整数范围压缩到可以接受的数组范围中。

  • 压缩实现：取余操作。

    ​

哈希化：将大数字转化成数组范围内下标的过程。

哈希函数：通常会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数被称为哈希函数。

哈希表：最终将数据插入到的这个数组，对整个结构的封装，称之为一个哈希表

冲突

下标值仍然可能相同，冲突不可避免，只能解决冲突。

解决冲突：

  • 链地址法（拉链法）。
  • 开放地址法。

链地址法

image
  • 每个数组单元中存储的不再是单个数据，而是一个==链条==。
  • 链条的数据结构通常是 数组或==链表==。
  • 比如是链表，也就是每个数组单元中存储着一个链表。一旦发现重复，将重复的元素插入到链表的首端或者未端即可。
  • 当查询时，先根据哈希化后的下标值找到对应的位置，再取出链表，依次查询找寻找的数据。

开放地址法

image

寻找空白的单元格来添加重复的数据

探索这个位置的方式：

  1. 线性探测：
  2. 二次探测
  3. 再哈希法

1.线性探测（82和32）

  1. 插入：

​ 经过哈希化得到index = 2，在插入的时候，发现该位置已经有了82；

​ 从 index+1 的位置开始一点点查找合适位置（空白位置）来放置32

  1. 查找：

​ 经过哈希化得到index = 2，比如2的位置结果和查询的数据是否相同，相同则直接返回；

​ 不相同，则从 index+1 位置开始查找和32一样的

​ 如果32的位置 我们之前 没有插入，则查询到空位置就停止，因为查询到这里有空位置，32之前不可能跳过空位置去其他的位置。

  1. 删除：

​ 删除一个数据项时，不可以将这个下标的内容设置为null；

​ 如果设置为null可能会影响之后的查询操作，通常删除一个位置的数据项时，可以进行特殊处理（比如设置为-1）；

​ 当看到-1位置的数据项时，就知道要继续查询，但是插入时这个位置可以放置数据。

  1. 问题：聚集

​ 比如在没有任何数据的时候，插入的是22-23-24-25-26，那么意味着下标值2-3-4-5的位置都有元素；

​ 这种一连串填充单元就叫做聚集；

​ 聚集会影响哈希表的性能，无论是插入/查询/删除 都有影响

​ 比如插入一个32，会发现连续的单元都不允许放置数据，并且在这个过程中需要探测多次；

​ 二次探测可以解决一部分这个问题。

2.二次探测

  • 二次探测主要优化的是==探测时的步长==；
  • ==线性探测==，可以看成是==步长为1==的探测，比如从下标值x开始,那么线性测试就是x+1，X+2，X+3依次探测；
  • 二次探测，对步长做了优化，比如从下标值x开始，x+1^2，x+2^2，x+3^2；
  • 这样就可以==一次性探测比较长的距离==，比避免那些聚集带来的影响；

问题：

​ 二次探测依然存在问题，比如我们连续插入的是32-112-82-2-192,那么它们依次累加的时候步长的相同的；

​ 也就是这种情况下会造成==步长不一的一种聚集==，还是会影响效率、(当然这种可能性相对于连续的数字会小一些)

3.再哈希法

  • 二次探测的算法产生的探测序列步长是固定的：1，4，9，16，依次类推；
  • 现在需要一种方法：产生一种 ==依赖关键字的探测序列==，而不是每个关键字都一样；
  • 那么，==不同的关键字== 即使映射到 ==相同的数组下标==，也可以使用 ==不同的探测序列==；
  • 再哈希法的做法就是：把关键字用另外一个哈希函数，再做一次哈希化，用这次哈希化的结果作为步长；
  • 对于==指定的关键字，步长==在整个探测中是==不变==的，不过==不同的关键字==使用==不同的步长==

第二次哈希化需要具备如下特点：

  • 和==第一个哈希函数不同== (不要再使用上一次的哈希函数了，不然结果还是原来的位置)；
  • ==不能输岀为0== (否则，将没有步长每次探测都是原地踏步，算法就进入了死循环)

其实，我们不用费脑细胞来设计了，计算机专家已经设计出一种工作很好的哈希函数:

  • stepsize = constant - (key % constant);
  • 其中 constant是质数，且小于数组的容量;
  • 例如: stepsize = 5 - (key % 5)，满足需求，并且结果不可能为0

哈希表中执行插入和搜索操作效率是非常高的：

  • 如果没有产生冲突，那么效率就会更高；
  • 如果发生冲突，存取时间就依赖后来的探测长度；
  • 平均探测长度以及平均存取时间，取决于墳装因子，随着填装因子变大，探测长度也越来越长；
  • 随着填裝因子变大，效率下降的情况，在不同开放地址法方案中比链地址法更严重；
  • 所以我们来对比-下他们的效率，再决定我们选取的方案

在分析效率之前，我们先了解一个概念：裝填因子

  • 装填因子表示当前哈希表中 已经包含的数据项 和 整个哈希表长度的 比值；
  • 装填因子 = 总数据项 / 哈希表长度；
  • 开放地址法 的 装填因子 最大 是多少呢?1，因为它必须寻找到空白的单元才能将元素放入
  • 链地址法 的 装填因子 呢?可以大于1，因为拉链法可以无限的延伸下去，只要你愿意(当然后面效率就变低了)。

三、哈希函数

好的哈希函数应该尽可能让计算的过程变得简单提高计算的效率。

  • 哈希表的主要==优点是它的速度==，所以在速度上不能满足，那么就达不到设计的目的了；
  • 提高速度的一个办法就是让哈希函数中==尽量少的有乘法和除法==。因为它们的==性能是比较低==的；

+ 设计好的哈希函数应该具备哪些优点呢?

  1. 快速的计算
  • 哈希表的优势就在于效率，所以快速获取到对应的 hash Code非常重要；
  • 我们需要通过快速的计算来获取到元素对应的 hash Code；
  1. 均匀的分布
  • 哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置的时候都会影响效率；
  • 所以优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀的分布；

​ 在设计哈希表时，我们已经有办法处理 映射到相同下标值 的情况：链地址法或者开放地址法.

​ 但是无论哪种方案，为了提供效率，最好的情况还是让数据在哈希表中均匀分布.

​ 因此，我们需要在使用常量的地方，尽量使用质数.

哪些地方我们会使用到常量呢?

+ 质数的使用

  • 哈希表的长度.
  • N次幂的底数(我们之前使用的是27)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/***************  哈希函数 ***********/

// 1.将字符串转成比较大的数字：hashCode
// 2.将大的数字hashCode压缩到数组范围（大小）之内
function hashFunc(str, size) {
  // 1.定义hashCode边浪
  let hashCode = 0;


  // 2.霍纳算法，来计算hashCode的值
  // cats -> Unicode编码
  for (let i = 0; i < str.length; i++) {
    hashCode = 37 * hashCode + str.charCodeAt(i);
  }

  // 3.取余操作
  return hashCode % size;
}

console.log(hashFunc('abc', 7)) // 4
console.log(hashFunc('cba', 7)) // 3
console.log(hashFunc('nba', 7)) // 5
console.log(hashFunc('mba', 7)) // 1

四、哈希表的实现

结构：

1
2
3
[
  [], [['name','Alice']], [['age', 20]]
]
image

代码实现：

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
/***************  哈希表 ***********/

function HashTable() {
  // 数组中存放相关的元素
  this.storage = [];
  // 当前哈希表已经存放的元素个数
  this.count = 0;
  // 哈希表 数组当前的总长度
  this.limit = 7;
  // 加载因子/装载因子 loadFactor > 0.75 || loadFactor < 0.25 ; loadFactor = count / limit

  // 哈希函数
  HashTable.prototype.hashFunc = function (str, size) {
    // 1.定义hashCode边浪
    let hashCode = 0;


    // 2.霍纳算法，来计算hashCode的值
    for (let i = 0; i < str.length; i++) {
      hashCode = 37 * hashCode + str.charCodeAt(i);
    }

    // 3.取余操作
    return hashCode % size;
  }

  // 插入和修改操作
  HashTable.prototype.put = function (key, value) {

    // 1.根据key获取索引值（目的：将数据插入到对应的位置）
    let index = this.hashFunc(key, this.limit);

    // 2.根据索引值取出bucket
    let bucket = this.storage[index];

    // 3.判断该bucket是否为null
    if (!bucket) {
      bucket = [];
      this.storage[index] = bucket;
    }

    // 4.判断是否是修改数据
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if(tuple[0] === key) {
        tuple[1] = value;
        return;
      }
    }

    // 5.进行添加操作
    bucket.push([key, value])
    this.count += 1;
  }


  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，是，直接返回null
    if(bucket === null) return null;

    // 4.线性查找bucket中每一个key是否等于传入的key
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      if (tuple[0] === key) {
        return tuple[1]
      }
    }

    // 5.依然没有知道
    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是否为null，是，直接返回null
    if(bucket === null) return null;

    // 4.线性查找bucket中每一个key是否等于传入的key
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      if (tuple[0] === key) {
        bucket.splice(i, 1);
        this.count--;
        return tuple[1];
      }
    }

    // 5.依然没有找到
    return null;
  }

  // 判断哈希表是否为空
  HashTable.prototype.isEmpty = function () {
    return this.count === 0;
  }

  // 判断哈希表元素的个数
  HashTable.prototype.size = function () {
    return this.count;
  }

}

五、哈希表扩容

+ 为什么需要扩容

  • 目前，我们是将所有的数据项放在长度为7的数组中的。
  • 因为我们使用的是链地址法， load Factor可以大于1，所以这个哈希表可以无限制的插入新数据。
  • 但是，随着数据量的增多，每—个 index对应的 bucket会越来越长，也就造成效率的降低。
  • 所以在合适的情况对数组进行扩容。比如扩容两倍。

+ 如何进行扩容

  • 扩容可以简单的将容量增大两倍(不是质数吗?质数的问题后面再讨论)。
  • 但是这种情况下，所有的数据项一定要同时进行修改(重新调用哈希函数来获取到不同的位置)。
  • 比如 hash Code=12的数据项在 length=8的时候 index=5。在长度为16的时候呢? index=12。
  • 这是一个耗时的过程，但是如果数组需要扩容，那么这个过程是必要的。

+ 什么情况下需要扩容

  • 比较常见的情况是 Lload Factor>0.75的时候进行扩容。
  • 比如Java的哈希表就是在==装填因子大于0.75==的时候，对哈希表进行扩容。

容量质数

+ 我们前面提到过，容量最好是质数

  • 虽然在链地址法中将容量设置为质数，没有在开放地址法中重要。
  • 但是其实链地址法中质数作为容量也更利于数据的均匀分布。

+ 质数的特点

  • 质数也称为素数
  • 质数表示大于1的自然数中，只能被1和自己整除的数。
    • 在 2到n-1 中间有可以被整除的数

+ 判定质数

  • 对于每个数n，其实并不需要从2判断到n-1
  • 一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n).
  • 比如16可以被分解。那么是2*8, 2小于sqrt(16)，也就是4，8大于4。而4*4都是等于sqrt(n)
  • 所以其实我们遍历到等于sqrt(n)即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 // 判断是否是质数
HashTable.prototype.isPrime = function (number) {
  if(number <= 1) return false;

  // 获取number的平方根
  const sqrt = parseInt(Math.sqrt(number));

  for (let i = 2; i <= sqrt; i++) {
    if (number % i === 0) {
      return false;
    }
  }
  return true;
}

// 获取质数：实现恒为质数
HashTable.prototype.getPrime = function(number) {
  while(!this.isPrime(number)) {
    number++;
  }
  return number;
}
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
// 哈希表扩容/缩容
HashTable.prototype.resize = function (newLimit) {
  // 1.保存旧数组内容
  let oldStorage = this.storage;

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

  // 3.遍历oldStorage 中所有的bucket
  for (let i = 0; i < oldStorage.length; i++) {
    // 3.1 取出对应的bucket
    const bucket = oldStorage[i];

    // 3.2 判断bucket是否为null
    if(!bucket) {
      continue;
    }

    // 3.3 bucekt中有数据，那么取出数据，重新插入
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      this.put(tuple[0], tuple[0])
    }

  }
}

// 插入时，扩容
HashTable.prototype.put = function (key, value) {

  // 1.根据key获取索引值（目的：将数据插入到对应的位置）
  let index = this.hashFunc(key, this.limit);

  // 2.根据索引值取出bucket
  let bucket = this.storage[index];

  // 3.判断该bucket是否为null
  if (!bucket) {
    bucket = [];
    this.storage[index] = bucket;
  }

  // 4.判断是否是修改数据
  for (let i = 0; i < bucket.length; i++) {
    let tuple = bucket[i];
    if(tuple[0] === key) {
      tuple[1] = value;
      return;
    }
  }

  // 5.进行添加操作
  bucket.push([key, value])
  this.count += 1;

  // 6.判断是否需要扩容
  if(this.count > this.limit * 0.75) {
    let newPrime = this.getPrime(this.limit * 2);
    this.resize(newPrime);
  }
}


// 删除时，减小容量
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是否为null，是，直接返回null
  if(bucket === null) return null;

  // 4.线性查找bucket中每一个key是否等于传入的key
  for (let i = 0; i < bucket.length; i++) {
    const tuple = bucket[i];
    if (tuple[0] === key) {
      bucket.splice(i, 1);
      this.count--;

      // 缩小容量
      if(this.limit > 7 && this.count < this.limit * 0.25) {
        let newPrime = this.getPrime(Math.floor(this.limit / 2));
        this.resize(newPrime)
      }

      return tuple[1];
    }
  }

  // 5.依然没有找到
  return null;
}
  • Post title: 哈希表
  • Post author: Chao
  • Create time: 2019-11-26 14:45:00
  • Post link: 2019/11/26/哈希表/
  • Copyright notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments
  1. 1. 一、哈希表 vs 数组
    1. 1.1. 哈希表：
    2. 1.2. 相对于数组的不足：
    3. 1.3. 数组查找效率：
  2. 2. 二、哈希表
    1. 2.1. 冲突
    2. 2.2. 链地址法
    3. 2.3. 开放地址法
  3. 3. 三、哈希函数
  4. 4. 四、哈希表的实现
  5. 5. 五、哈希表扩容
    1. 5.1. 容量质数