哈希表的底层实现及其在unordered_set与unordered_map中的封装
本帖最后由 Shaw0xyz 于 2024-7-14 12:18 编辑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`使用哈希函数计算元素的哈希值，将元素存储到对应的桶中，如果发生冲突，则将元素添加到桶的链表中。
unordered_set<int> uset;
uset.insert(5);
uset.insert(10);
4.1.2 查找操作
查找操作时，`unordered_set`根据哈希值找到对应的桶，在桶的链表中查找目标元素。
if (uset.find(5) != uset.end()) {
cout << "Found 5" << endl;
}
4.1.3 删除操作
删除操作时，`unordered_set`在对应桶的链表中找到并移除目标元素。
uset.erase(5);
4.2 `unordered_map`
`unordered_map`是基于哈希表实现的键值对容器，提供常数时间复杂度的插入、删除和查找操作。
4.2.1 插入操作
插入操作时，`unordered_map`使用哈希函数计算键的哈希值，将键值对存储到对应的桶中，如果发生冲突，则将键值对添加到桶的链表中。
unordered_map<int, string> umap;
umap = "one";
umap = "two";
4.2.2 查找操作
查找操作时，`unordered_map`根据哈希值找到对应的桶，在桶的链表中查找目标键，并返回相应的值。
if (umap.find(1) != umap.end()) {
cout << "Key 1 has value " << umap << endl;
}
4.2.3 删除操作
删除操作时，`unordered_map`在对应桶的链表中找到并移除目标键值对。
umap.erase(1);
5. 结论
本文详细介绍了哈希表的底层实现原理，并讨论了其在`unordered_set`和`unordered_map`中的封装方式。通过理解哈希表的工作机制，可以更好地利用这些高效的数据结构，提高程序的性能和效率。希望本文能为您在实际编程中提供有用的参考。
页:
[1]