前言

哈希表是一种 键值对（key-value） 数据结构，具有高效的查找、插入和删除性能。它广泛用于需要快速访问数据的场景，例如字典、缓存、数据库索引等。

简介

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。
一个哈希函数的好不好，取决于以下三点：

哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值域必须在0 到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

哈希表的基本概念

键值对（key-value）存储：
- 键（key）：数据的唯一标识，类似索引。
- 值（value）：与键相关联的数据。
哈希函数（Hash Function）：
- 用于将键（key）映射到哈希表中的特定位置（索引）。
- 理想的哈希函数应具有以下特点：
  - 快速计算。
  - 均匀分布，尽可能减少冲突（两个不同的键映射到相同的索引）。
哈希表的性能：
- 查找、插入、删除的平均时间复杂度为 (O(1))。
- 在极端情况下（哈希冲突过多），时间复杂度可能退化为 (O(n))。

哈希表的实现原理

数组存储：
- 哈希表底层通常是一个固定大小的数组，每个数组单元称为 桶（bucket）。
哈希函数：
- 根据键计算出数组的索引值： $\text{Index} = \text{HashFunction}(\text{Key}) \% \text{TableSize}$
哈希冲突（Collision）：
- 不同的键通过哈希函数映射到相同的索引时，称为冲突。
冲突解决策略：
- 链地址法（Separate Chaining）：
  - 每个桶使用链表存储多个键值对。
  - 插入冲突时，在存储数据后面加一个指针，指向后面冲突的数据，将新元素添加到链表的尾部。
  - ![[Pasted image 20241118171656.png]]
- 开放地址法（Open Addressing）：
  - 当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去
  - 闭散列中主要处理方法有线性探测和二次探测
    
    线性探测：计算哈希地址，将数据存放在计算出来的哈希位置上，如果该位置有数据则往后查找第一个空闲位置插入。但是当我们的元素越多时，我们产生的哈希冲突的次数就会越多。
    二次探测：通过该位置的哈希冲突次数的平方来向后查找新的位置，将产生哈希冲突的数据分散，使不堆积在一起。
    以上两种方法都有很大的缺陷，就是空间利用率低。在这个基础上，引进一种新的技术来解决哈希冲突——开散列（链地址法）
扩容：
- 当哈希表中的元素数量接近数组大小（负载因子达到阈值），会动态扩展哈希表的大小，并重新分布所有键值对（称为 rehash）。

哈希表的特点

优点：

快速查找：平均时间复杂度 (O(1))。
动态扩展：大多数哈希表会在容量接近满时自动扩展。
灵活性：可以存储复杂的数据结构（如对象、类等）。

缺点：

无法保持顺序：存储元素是无序的，无法按插入顺序访问。
哈希冲突：大量冲突会导致性能下降。
内存占用高：通常需要分配比实际存储元素更多的空间。
不支持范围查找：不像有序结构（如二叉搜索树）支持范围查找。

C++ 中的哈希表实现

标准库容器：

1. unordered_map

用途：存储键值对，键唯一。
时间复杂度：平均 (O(1))，最坏 (O(n))。
底层实现：链地址法。

示例：

#include <unordered_map>
#include <iostream>
using namespace std;

int main() {
    unordered_map<string, int> map;
    map["apple"] = 10;
    map["banana"] = 20;

    // 查找元素
    cout << "Value of apple: " << map["apple"] << endl;

    return 0;
}

输出：
1
Value of apple: 10

2. unordered_set

用途：存储唯一键，无关联值。

示例：

#include <unordered_set>
#include <iostream>
using namespace std;

int main() {
    unordered_set<int> set = {1, 2, 3, 4};

    // 查找元素
    if (set.find(2) != set.end()) {
        cout << "2 found in set" << endl;
    }

    return 0;
}

输出：
1
2 found in set

3. unordered_multimap 和 unordered_multiset

允许存储重复的键。

哈希表的应用场景

快速查找：
- 例如，电话号码簿、用户信息存储等。

计数问题：

统计字符串中字母的出现频率。

#include <unordered_map>
#include <iostream>
using namespace std;

int main() {
    string str = "hello world";
    unordered_map<char, int> freq;

    for (char c : str) {
        freq[c]++;
    }

    for (auto& pair : freq) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

输出：
1
2
3
4
5
6
7
h: 1
e: 1
l: 3
o: 2
w: 1
r: 1
d: 1

字母异位词分组：
- 通过将字符串排序后的结果作为键，将字母异位词归为一组。
缓存（Cache）：
- 实现快速访问最近使用的数据（结合哈希表和链表实现 LRU 缓存）。

常见问题与优化

哈希冲突的解决：
- 优化哈希函数，减少冲突。
- 使用适当的负载因子。
内存消耗过多：
- 如果数据规模较小，可以考虑有序映射（std::map）。
扩容和重哈希：
- 如果数据量大，可以提前设置哈希表的初始大小以减少重哈希的开销。

哈希表 vs 其他数据结构

特性	哈希表（`unordered_map`）	有序映射（`map`）	动态数组（`vector`）
查找/插入时间复杂度	(O(1))	(O(\log n))	(O(n))（非索引查找）
是否保持元素顺序	否	是	是
是否支持范围查询	否	是	否
内存使用	较高	较低	较低

哈希表相关容器的对比

容器	是否允许重复	是否有序	平均时间复杂度	备注
`std::unordered_map`	否	否	O(1)	哈希表实现，键值对存储
`std::unordered_set`	否	否	O(1)	哈希表实现，只存储键
`std::unordered_multimap`	是	否	O(1)	哈希表实现，允许重复键
`std::unordered_multiset`	是	否	O(1)	哈希表实现，允许重复元素
`std::map`	否	是	O(log⁡n)	红黑树实现，按键有序存储
`std::multimap`	是	是	O(log⁡n)	红黑树实现，允许重复键
`std::set`	否	是	O(log⁡n)	红黑树实现，按键有序存储
`std::multiset`	是	是	O(log⁡n)	红黑树实现，允许重复元素