哈希表的底层实现及其在unordered_set与unordered_map中的封装

Shaw0xyz

1. 引言

哈希表是一种高效的数据结构，能够在平均情况下提供常数时间复杂度的插入、删除和查找操作。在C++标准库中，`unordered_set`和`unordered_map`是基于哈希表实现的两个容器。本文将详细介绍哈希表的底层实现原理，并讨论其在`unordered_set`和`unordered_map`中的封装方式。

2. 哈希表的基本概念

2.1 哈希函数

哈希表依赖于哈希函数将键值映射到存储位置。一个好的哈希函数应该能够均匀地分布键值，减少冲突。

2.2 冲突解决

当两个或多个键被哈希到同一位置时，就会发生冲突。常见的冲突解决方法包括链地址法（拉链法）和开放地址法。

3. 哈希表的底层实现

3.1 链地址法

链地址法使用一个链表或其他数据结构存储哈希冲突的所有元素。每个哈希桶（bucket）对应一个链表，当发生冲突时，新元素将被添加到相应链表中。

3.1.1 插入操作

插入元素时，首先计算哈希值，然后根据哈希值找到对应的桶，将元素添加到桶的链表中。

3.1.2 查找操作

查找元素时，首先计算哈希值，然后在对应桶的链表中查找目标元素。

3.1.3 删除操作

删除元素时，首先计算哈希值，然后在对应桶的链表中找到并移除目标元素。

3.2 开放地址法

开放地址法在发生冲突时，通过探测空闲位置来存储新元素。常见的探测方法有线性探测、二次探测和双重哈希。

3.2.1 插入操作

插入元素时，首先计算哈希值，如果目标位置被占用，则根据探测规则查找下一个空闲位置。

3.2.2 查找操作

查找元素时，首先计算哈希值，如果目标位置不匹配，则根据探测规则查找下一个位置，直到找到目标元素或空闲位置。

3.2.3 删除操作

删除元素时，需要标记删除位置，以便后续查找操作可以继续探测。

4. `unordered_set`和`unordered_map`的封装

4.1 `unordered_set`

`unordered_set`是基于哈希表实现的集合容器，存储唯一的元素，提供常数时间复杂度的插入、删除和查找操作。

4.1.1 插入操作

插入操作时，`unordered_set`使用哈希函数计算元素的哈希值，将元素存储到对应的桶中，如果发生冲突，则将元素添加到桶的链表中。

1. unordered_set<int> uset;
   
2. uset.insert(5);
   
3. uset.insert(10);

复制代码

4.1.2 查找操作

查找操作时，`unordered_set`根据哈希值找到对应的桶，在桶的链表中查找目标元素。

1. if (uset.find(5) != uset.end()) {
   
2.     cout << "Found 5" << endl;
   
3. }

复制代码

4.1.3 删除操作

删除操作时，`unordered_set`在对应桶的链表中找到并移除目标元素。

1. uset.erase(5);

复制代码

4.2 `unordered_map`

`unordered_map`是基于哈希表实现的键值对容器，提供常数时间复杂度的插入、删除和查找操作。

4.2.1 插入操作

插入操作时，`unordered_map`使用哈希函数计算键的哈希值，将键值对存储到对应的桶中，如果发生冲突，则将键值对添加到桶的链表中。

1. unordered_map<int, string> umap;
   
2. umap[1] = "one";
   
3. umap[2] = "two";

复制代码

4.2.2 查找操作

查找操作时，`unordered_map`根据哈希值找到对应的桶，在桶的链表中查找目标键，并返回相应的值。

1. if (umap.find(1) != umap.end()) {
   
2.     cout << "Key 1 has value " << umap[1] << endl;
   
3. }

复制代码

4.2.3 删除操作

删除操作时，`unordered_map`在对应桶的链表中找到并移除目标键值对。

1. umap.erase(1);

复制代码

5. 结论

本文详细介绍了哈希表的底层实现原理，并讨论了其在`unordered_set`和`unordered_map`中的封装方式。通过理解哈希表的工作机制，可以更好地利用这些高效的数据结构，提高程序的性能和效率。希望本文能为您在实际编程中提供有用的参考。