【数据结构】哈希表

博主： PCsky
发布时间：2022 年 06 月 15 日
853次浏览
暂无评论
4302字数
分类：算法笔记数据结构

前言

数组是一种常见的数据结构，在我们知道数组中某个元素的下标值时，我们可以通过下标值的方式以 O(1) 复杂度获取到数组中对应的元素。但如果我们不知道某个元素的下标值，而只是知道该元素在数组中，这时我们想要获取该元素就只能对数组进行线性查找，如果一个长度为10000的数组，我们需要的元素正好在第10000个，那么我们就要对数组遍历10000次，复杂度退化为 O(n) 。为了解决上述数组的不足之处，我们引入了哈希表的概念。

哈希表思维导图

一、什么是哈希表

我们回想一下，若要在字典查找一个单词，肯定不会从头翻到尾，而是会通过单词首字母，找到对应的那一页，然后快速的跳转到那个单词所在的页，这里面用到了哈希表的思维。

哈希表，又称散列表，是一种以 key-value 形式存储数据的数据结构。所谓以 key-value 形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以通过某种映射函数快速地找到其对应的 value（如下图）。

HashTable

通常，我们会把给定的键值叫做 key ，把对应的记录称为 value ，可以快速求出该关键字对应的的数据的哈希地址函数则称之为 哈希函数 。在OI中，最常见的情况应该是 key 为整数的情况，另一种比较常见的情况是 key 为字符串的情况，但我们一般不直接把字符串作为键值，而是先算出字符串的哈希值，再把其哈希值作为 key 插入到哈希表里。

二、哈希函数的构造

在构建哈希表时，最重要的就是哈希函数的设计。哈希函数的构造有三个基本要求：

通过 key 可以计算出一个确切的 hash 值
如果 key1 == key2 ，则hash(key1) == hash(key2)
如果 key1 != key2 ，则hash(key1) != hash(key2)

常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

①直接寻址法

直接寻址法是一种比较常用的哈希函数构造方法，它构造出来的哈希函数为一个线性函数，其形式一般如下：

H（key）= key 或者 H（key）=a * key + b

其中 H（key）表示关键字为 key 对应的哈希地址，a 和 b 都为常数。该方法通过取关键字本身或者某个线性函数的值作为哈希地址。例如有一个从 1 岁到 100 岁的人口数字统计表，若直接使用年龄做哈希地址，则有如下表格：

直接定址法

使用该方法构造哈希函数的优点是计算方式简单，计算出来的哈希地址比较平均，但同时我们必须实现知道关键字的分布情况（即可能的值域），因此这种方法适合于数据范围较小且连续的情况。

②除留余数法

如果我们已经知道了整个哈希表的最大长度 m，则可以取一个不大于 m 的数 p，然后让关键字 key 与数 p 做取余运算，用所得到的结果作为哈希地址，其形式一般如下：

H（key）= key % p （ p<=m，m为表长）

举个例子，假设有以下数据{2, 4, 6, 8, 9}，已知表长为10，也就是数组容量为10，则我们可取模数 p 为 10 ，根据除留余数法进行构造后，我们可以得到下图的存储方式。

除留余数法

除留余数法是最常用的一种哈希函数构造方法，在此方法中，模数 p 的取值非常重要，一般来说 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数，或者直接就是长度 m 本身。

③数字分析法

如果关键字本身是由多位字符或者数字组成，就可以考虑抽取其中的变化较多的 2 位或者多位作为该关键字对应的哈希地址。比如下表是若干个由8位十进制数组成的关键字：

数字分析法

通过分析关键字的构成，很明显可以看到关键字的第 1 位和第 2 位都是固定不变的，而第 3 位不是数字 3 就是 4，最后一位只可能取 2、7 和 5，只有中间的 4 位其取值近似随机，所以为了避免冲突，可以从 4 位中任意选取 2 位作为其哈希地址。

④平方取中法

当关键字的每一位都有某些数字重复出现频率很高，无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址，该方法叫做平方取中法。

举个例子：例如关键字序列为{421，423，436}，对各个关键字进行平方后的结果为{177241，178929，190096}，则可以取中间的两位{72，89，00}作为其哈希地址。

平方取中法的原理是：在平方时，运算结果的中间几位和关键字中的每一位都相关，平方运算扩大了关键字之间的差异 ，所以不同的关键字会以较高的概率产生不同的哈希地址。这也是一种较常见的哈希函数构造方法，它适用于事先不知道数据并且数据长度较小的情况。

⑤折叠法

折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。例如某书的编号为：0-442-20586-4，则可以选择下图的分割方式，在对其进行折叠时有两种方式：一种是移位折叠，另一种是间界折叠。

移位折叠是将分割后的每一小部分，按照其最低位进行对齐，然后相加，如图（a）；
间界折叠是从一端向另一端沿分割线来回折叠，如图（b）

折叠法

⑥取随机数法

随机数法是取关键字的一个随机函数值作为它的哈希地址，即：H（key）=random（key），此方法适用于关键字长度不等的情况。这里的随机函数其实是伪随机函数，随机函数是即使每次给定的 key 相同，但是 H（key）都是不同；而伪随机函数正好相反，每个 key 都对应的是固定的 H（key）

如何选择合适的构造方案

如此多的构建哈希函数的方法，在选择的时候，需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面：

关键字的长度。如果长度不等，就选用随机数法。如果关键字位数较多，就选用折叠法或者数字分析法；反之如果位数较短，可以考虑平方取中法；
哈希表的大小。如果大小已知，可以选用除留余数法；
关键字的分布情况；
查找表的查找频率；
计算哈希函数所需的时间（包括硬件指令的因素）

一个好的哈希函数，一般取决于以下几个方面：

函数设计不会太复杂，尽量少的影响性能
哈希函数的定义域必须包括需要存储的全部 key
哈希函数计算出来的地址尽量均匀分布，避免过多的冲突

三、哈希冲突

根据上一节内容可知，哈希函数需要满足：如果 key1 != key2 ，则hash(key1) != hash(key2)。但有些时候，不同的 key 会算出同样的哈希地址。例如对于表长为 25 的哈希表，假设用除留余数法，取模数为19，我们会发现 hash(2) == hash(21)，这种现象称之为哈希冲突。

注意：对于哈希表而言，哈希冲突只能尽可能少，不可能完全避免

对于无法避免的冲突，则需要采取适当的措施去处理。一般来说主要的解决哈希冲突方式分为：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）

①闭散列法

闭散列法也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么我们可以尝试探测寻找剩余的空位，把 key 存放到冲突位置中的“下一个” 空位置中去。

H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量，所谓的下一个指的就是一个增量）

根据不同的增量选取方式，闭散列法的实现一般分为线性探测，二次探测，再哈希法三种

(1)线性探测

顾名思义，线性探测的意思就是，当某两个元素发生冲突时，将当前索引+1，查看该位置是否为空，是的话就插入数据，否则就继续将索引+1，以此类推……直到插入数据位置。比如下图，如果模数为 11 ，此时需要插入38，我们发现 5 号位置已经有60了，则我们不断地把地址+1，最后38被放在了 8 号位置。

线性探测

但这种方法有一个缺点，那就是当数组中连续很长的一个片段都已经插入了数据，此时用线性探测就显得效率没那么高了，因为每次探测的步长都为1，所以这段都已经插入了数据的片段都得进行探测一次，这种现象叫做聚集。我们可以选用 二次探测 来缓解聚集这种现象。

(2)二次探测

二次探测在线性探测的基础上，将每次探测的步长改为了当前下标值 index + 1² 、index + 2² 、 index + 3² …… 直到找到空白位置插入元素为止。

二次探测

二次探测 在一定程度上解决了 线性探测 造成的聚集问题，但是它却容易在另一种程度造成了一种聚集，就比如 1² 、2² 、3² …… n² 上的聚集

代码实现

const int N = 360007;  // N 是最大可以存储的元素数量

class Hash {
 private:
  int keys[N];
  int values[N];

 public:
  Hash() { memset(values, 0, sizeof(values)); }

  int& operator[](int n) {
    // 返回一个指向对应 Hash[Key] 的引用
    // 修改成不为 0 的值 0 时候视为空
    int idx = (n % N + N) % N, cnt = 1;
    while (keys[idx] != n && values[idx] != 0) {
      idx = (idx + cnt * cnt) % N;
      cnt += 1;
    }
    keys[idx] = n;
    return values[idx];
  }
};

(3)再哈希法

再哈希法就是将我们传入的 key 用另一个哈希函数再进行一次哈希化，然后使用新的哈希值作为探测步数 step ，按照这个步数找到第一个空着的位置插入数据，这种方法在很大的程度上解决了聚集的问题。

再哈希的哈希函数可以写成如下形式：step = constant - (key % constant)，其中，constant 是一个自己定的质数常量，且小于数组的容量； key 就是第一次哈希化得到得值。我们通过这个哈希函数算得的步长来进行查找搜索空位置进行插入即可。

②开散列法

开散列法也称链地址法，就是在每个hash槽都开一个链表，如果有多个键值索引到同一个地方，只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 $1...m$ ，哈希表的大小为 $n$ ，那么进行一次插入/查询需要进行期望 $O( \frac {n} {m} )$ 次比较。

开散列法

代码实现

// C++ Version
const int SIZE = 1000000;
const int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];

  int head[M], size;

  int f(int key) { return key % M; }

  int get(int key) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value;
    return -1;
  }

  int modify(int key, int value) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    if (get(key) != -1) return -1;
    data[++size] = (Node){head[f(key)], value, key};
    head[f(key)] = size;
    return value;
  }
};

这里再提供一个封装过的模板，可以像 map 一样用，并且较短

struct hash_map {  // 哈希表模板

  struct data {
    long long u;
    int v, nex;
  };  // 前向星结构

  data e[SZ << 1];  // SZ 是 const int 表示大小
  int h[SZ], cnt;

  int hash(long long u) { return u % SZ; }

  int& operator[](long long u) {
    int hu = hash(u);  // 获取头指针
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

在这里，hash 函数是针对键值的类型设计的，并且返回一个链表头指针用于查询。在这个模板中我们写了一个键值对类型为 (long long, int) 的 hash 表，并且在查询不存在的键值时返回 -1。函数 hash_map() 用于在定义时初始化。

四、哈希表的特点

根据哈希表的存储结构，我们可以得出哈希表的以下特点。

1)访问速度快

由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。

2)需要额外的空间

首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。

3)无序

散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。

4)可能会产生碰撞

没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样

参考资料

版权属于：PCsky
本文链接：http://www.hyouka.club/index.php/archives/198/
转载时须注明出处及本声明

最后修改：2022 年 06 月 15 日 05 : 07 PM

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

邮箱 *

地址

侯
安装软件或者卸载软甲出这个弹框什么意思，区域啥的也设置了nsi...
后浪
找到了，谢谢
后浪
这个主题挺好看的，有深色模式，是自己写的吗还是在哪里可以找到？
橘白猫
我单位的WIN10神州网信系统出现了一个奇葩的问题，不知道你有...
Acg
handsome.min.css的度盘链接有问题，打开是一个图片

【数据结构】哈希表

PCsky • 2022 年 06 月 15 日

前言

哈希表思维导图

一、什么是哈希表

HashTable

二、哈希函数的构造

在构建哈希表时，最重要的就是哈希函数的设计。哈希函数的构造有三个基本要求：

通过 key 可以计算出一个确切的 hash 值
如果 key1 == key2 ，则hash(key1) == hash(key2)
如果 key1 != key2 ，则hash(key1) != hash(key2)

常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

①直接寻址法

直接寻址法是一种比较常用的哈希函数构造方法，它构造出来的哈希函数为一个线性函数，其形式一般如下：

H（key）= key 或者 H（key）=a * key + b

直接定址法

②除留余数法

H（key）= key % p （ p<=m，m为表长）

除留余数法

③数字分析法

数字分析法

④平方取中法

⑤折叠法

移位折叠是将分割后的每一小部分，按照其最低位进行对齐，然后相加，如图（a）；
间界折叠是从一端向另一端沿分割线来回折叠，如图（b）

折叠法

⑥取随机数法

如何选择合适的构造方案

如此多的构建哈希函数的方法，在选择的时候，需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面：

关键字的长度。如果长度不等，就选用随机数法。如果关键字位数较多，就选用折叠法或者数字分析法；反之如果位数较短，可以考虑平方取中法；
哈希表的大小。如果大小已知，可以选用除留余数法；
关键字的分布情况；
查找表的查找频率；
计算哈希函数所需的时间（包括硬件指令的因素）

一个好的哈希函数，一般取决于以下几个方面：

函数设计不会太复杂，尽量少的影响性能
哈希函数的定义域必须包括需要存储的全部 key
哈希函数计算出来的地址尽量均匀分布，避免过多的冲突

三、哈希冲突

注意：对于哈希表而言，哈希冲突只能尽可能少，不可能完全避免

①闭散列法

H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量，所谓的下一个指的就是一个增量）

根据不同的增量选取方式，闭散列法的实现一般分为线性探测，二次探测，再哈希法三种

(1)线性探测

线性探测

(2)二次探测

二次探测在线性探测的基础上，将每次探测的步长改为了当前下标值 index + 1² 、index + 2² 、 index + 3² …… 直到找到空白位置插入元素为止。

二次探测

代码实现

const int N = 360007;  // N 是最大可以存储的元素数量

class Hash {
 private:
  int keys[N];
  int values[N];

 public:
  Hash() { memset(values, 0, sizeof(values)); }

  int& operator[](int n) {
    // 返回一个指向对应 Hash[Key] 的引用
    // 修改成不为 0 的值 0 时候视为空
    int idx = (n % N + N) % N, cnt = 1;
    while (keys[idx] != n && values[idx] != 0) {
      idx = (idx + cnt * cnt) % N;
      cnt += 1;
    }
    keys[idx] = n;
    return values[idx];
  }
};

(3)再哈希法

②开散列法

开散列法

代码实现

// C++ Version
const int SIZE = 1000000;
const int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];

  int head[M], size;

  int f(int key) { return key % M; }

  int get(int key) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value;
    return -1;
  }

  int modify(int key, int value) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    if (get(key) != -1) return -1;
    data[++size] = (Node){head[f(key)], value, key};
    head[f(key)] = size;
    return value;
  }
};

这里再提供一个封装过的模板，可以像 map 一样用，并且较短

struct hash_map {  // 哈希表模板

  struct data {
    long long u;
    int v, nex;
  };  // 前向星结构

  data e[SZ << 1];  // SZ 是 const int 表示大小
  int h[SZ], cnt;

  int hash(long long u) { return u % SZ; }

  int& operator[](long long u) {
    int hu = hash(u);  // 获取头指针
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

四、哈希表的特点

根据哈希表的存储结构，我们可以得出哈希表的以下特点。

1)访问速度快

2)需要额外的空间

3)无序

4)可能会产生碰撞

参考资料

版权属于：PCsky
本文链接：http://www.hyouka.club/index.php/archives/198/
转载时须注明出处及本声明

前言

一、什么是哈希表

二、哈希函数的构造

①直接寻址法

②除留余数法

③数字分析法

④平方取中法

⑤折叠法

⑥取随机数法

如何选择合适的构造方案

三、哈希冲突

①闭散列法

(1)线性探测

(2)二次探测

代码实现

(3)再哈希法

②开散列法

代码实现

四、哈希表的特点

参考资料

发表评论 取消回复

【数据结构】哈希表

前言

一、什么是哈希表

二、哈希函数的构造

①直接寻址法

②除留余数法

③数字分析法

④平方取中法

⑤折叠法

⑥取随机数法

如何选择合适的构造方案

三、哈希冲突

①闭散列法

(1)线性探测

(2)二次探测

代码实现

(3)再哈希法

②开散列法

代码实现

四、哈希表的特点

参考资料

发表评论取消回复