【C++】《【C++】unordered_map 与 unordered_set 完整解析以及哈希底层、哈希冲突、闭散列与开散列》-171主机测评

一.unordered 系列关联式容器

在 C++98 中，STL 的map、set底层基于红黑树实现，查找复杂度O(logN)，查找次数等于树高，数据量很大时查询效率存在局限。为了获得更快的平均查找速度，C++11 引入 4 种 unordered 哈希关联容器：unordered_map/unordered_set/unordered_multimap/unordered_multiset，底层是哈希表。

遍历特性：不保证 key 有序；迭代器为单向前向迭代器，不能逆向遍历。

Key 重复规则

unordered_map、unordered_set：key 唯一，不能重复

unordered_multimap、unordered_multiset：允许 key 重复

[] 下标操作

unordered_map支持[]；unordered_set 没有 [] 运算符

multiset、multimap 由于 key 可重复，不能使用[]

复杂度：平均(O(1)，最坏哈希冲突严重时O(N)；红黑树容器稳定O(logN)。
使用取舍：需要有序选 map/set；追求平均查找速度、无需有序选 unordered 系列。

unordered 系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。在一般情况下，建议使用 unordered 系列的关联式容器。

1.unordered_map

（1)unordered_map介绍

unordered_map – C++ Reference

【翻译如下】

unordered_map 是关联式容器，存储由键（key）和映射值（mapped value）组合而成的元素，能够根据键快速检索单个元素。

在 unordered_map 中，键一般用来唯一标识元素；映射值是和该键关联的内容对象。键的类型和映射值的类型可以不相同。

内部存储特点：容器内元素不会按照键或者映射值进行排序。元素依靠哈希值分到不同桶（buckets）中，从而支持通过键直接快速访问元素，平均时间复杂度为常数级别 O (1)。

与 map 对比：通过键访问单个元素时，unordered_map 速度比 map 更快；但是遍历一段区间元素时，整体效率通常更低。

支持下标运算符operator[]，可以传入键，直接访问对应的映射值。

迭代器类型：容器提供的迭代器至少是前向迭代器（forward iterators，单向迭代器）。

（2）unordered_map 的接口说明

a. 构造函数

https://cplusplus.com/reference/unordered_map/unordered_map/unordered_map/

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

int main() {
// 1. 空构造，后面再赋值
unordered_map<string, int> m1;
m1["a"] = 1;
m1["b"] = 2;

// 2. 直接初始化
unordered_map<string, int> m2 = {{"x", 10}, {"y", 20}};

// 3. 拷贝构造
unordered_map<string, int> m3 = m2;

// 输出看看
cout << "m1[a] = " << m1["a"] << endl;
cout << "m2[x] = " << m2["x"] << endl;
cout << "m3[y] = " << m3["y"] << endl;

return 0;
}

b. 容量函数

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

int main() {
unordered_map<string, int> score;

// 判断是否为空的
if (score.empty()) {
cout << "还没人得分呢" << endl;
}

// 放几个数据进去
score["hjq"] = 95;
score["hz"] = 87;

// 再瞅瞅
cout << "现在有 " << score.size() << " 个人的成绩" << endl;

if (!score.empty()) {
cout << "有人得分了" << endl;
}

return 0;
}

c. 迭代器

begin/end：可读写迭代器；

cbegin/cend：只读迭代器；

迭代器区间 `[begin,end)`，左闭右开，用于范围遍历；

没有 rbegin、rend 反向迭代器（只有前向单向迭代器，不能后退）。

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

int main()
{

unordered_map<int, string> m;
m[1] = "张三";
m[2] = "李四";
m[3] = "王五";

cout << "使用begin()和end()遍历：" << endl;
//用迭代器遍历，begin开始，end作为结束位置
for (auto it = m.begin(); it != m.end(); it++)
{
cout << it->first << " " << it->second << endl;
}

cout << "\\n使用cbegin()和cend()只读遍历：" << endl;
for (auto it = m.cbegin(); it != m.cend(); it++)
{
cout << it->first << " " << it->second << endl;
}
return 0;
}

d. 元素访问

https://cplusplus.com/reference/unordered_map/unordered_map/operator%5B%5D/

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

int main()
{
unordered_map<int, string> mp;
//1.key不存在，[]会自动插入，value为默认空字符串
cout << mp[10] << endl;
//此时容器里已经多了(10,"")

//2.key存在，[]直接取出对应value并修改
mp[10] = "hello";
cout << mp[10] << endl;

return 0;
}

注意：operator[]内部会尝试执行插入。若容器中没有该 key，则插入一条 key 和默认值V()组成的元素，返回默认值；若 key 已经存在，插入不会生效，直接返回该 key 对应的 value。

unordered_map<int,string> mp;
cout << mp[1]; //没有key=1，自动插入(1,"")，返回空字符串
mp[1] = "hi"; //key已存在，不会新增，直接修改value

e. 查询操作

https://cplusplus.com/reference/unordered_map/unordered_map/find/

https://cplusplus.com/reference/unordered_map/unordered_map/count/

#include <iostream>
#include <unordered_map>
#include <string>

int main() {

std::unordered_map<std::string, int> hashTable;

// 插入数据
hashTable["apple"] = 5;
hashTable["banana"] = 3;
hashTable["cherry"] = 7;

// 1. 使用 find: 查找 key 为 "banana" 的元素
auto it = hashTable.find("banana");
if (it != hashTable.end()) {
std::cout << "找到 banana，值为: " << it->second << std::endl;
}
else {
std::cout << "未找到 banana" << std::endl;
}

// 查找不存在的 key
auto it2 = hashTable.find("grape");
if (it2 != hashTable.end()) {
std::cout << "找到 grape，值为: " << it2->second << std::endl;
}
else {
std::cout << "未找到 grape" << std::endl;
}

//2. 使用 count：统计 key 为 "apple" 的个数
size_t count1 = hashTable.count("apple");
std::cout << "apple 的个数: " << count1 << std::endl;

size_t count2 = hashTable.count("grape");
std::cout << "grape 的个数: " << count2 << std::endl;

return 0;
}

unordered_map 的 key 是唯一的，不会存在重复，所以它的 count 方法最多返回 1。找到目标 key 就返回 1，找不到返回 0。这点和支持重复键的 multimap 不一样，后者 count 可以大于 1。

f. 修改操作

https://cplusplus.com/reference/unordered_map/unordered_map/insert/

https://cplusplus.com/reference/unordered_map/unordered_map/erase/

https://cplusplus.com/reference/unordered_map/unordered_map/clear/

https://cplusplus.com/reference/unordered_map/unordered_map/swap/

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

int main() {
// 1. insert：插入键值对
unordered_map<string, int> m;
m.insert({ "apple", 5 });
m.insert({ "banana", 3 });
m.insert({ "cherry", 7 });
m["date"] = 10; // 另一种插入方式

cout << "插入后: ";
for (auto& p : m) {
cout << p.first << ":" << p.second << " ";
}
cout << endl;

// 2. erase：删除
m.erase("banana"); // 根据key删除
cout << "删除banana后: ";
for (auto& p : m) {
cout << p.first << ":" << p.second << " ";
}
cout << endl;

// 3. clear：清空
unordered_map<string, int> m2 = { {"x", 1}, {"y", 2} };
cout << "清空前大小: " << m2.size() << endl;
m2.clear();
cout << "清空后大小: " << m2.size() << endl;

// 4. swap：交换
unordered_map<string, int> a = { {"A", 1}, {"B", 2} };
unordered_map<string, int> b = { {"C", 3}, {"D", 4}, {"E", 5} };

cout << "交换前 a大小:" << a.size() << " b大小:" << b.size() << endl;
a.swap(b);
cout << "交换后 a大小:" << a.size() << " b大小:" << b.size() << endl;

return 0;
}

g. 桶操作

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

int main() {
unordered_map<string, int> m;

// 插入一些数据
m["apple"] = 5;
m["banana"] = 3;
m["cherry"] = 7;
m["date"] = 10;
m["grape"] = 8;

// 1. bucket_count()：返回桶的总个数
cout << "桶的总个数: " << m.bucket_count() << endl;

// 2. bucket_size(n)：返回n号桶中有效元素个数
cout << "\\n各个桶的元素个数:" << endl;
for (size_t i = 0; i < m.bucket_count(); i++) {
cout << i << "号桶: " << m.bucket_size(i) << "个元素" << endl;
}

// 3. bucket(key)：返回元素key所在的桶号
cout << "\\n各元素所在的桶号:" << endl;
cout << "apple 在 " << m.bucket("apple") << " 号桶" << endl;
cout << "banana 在 " << m.bucket("banana") << " 号桶" << endl;
cout << "cherry 在 " << m.bucket("cherry") << " 号桶" << endl;
cout << "date 在 " << m.bucket("date") << " 号桶" << endl;
cout << "grape 在 " << m.bucket("grape") << " 号桶" << endl;

return 0;
}

2.unordered_set

unordered_set – C++ Reference

(1)unordered_set 的介绍

【翻译如下】：

无序集合（Unordered Set）

unordered_set 是一类容器，用来存储唯一元素，元素没有固定顺序；它支持根据元素的值快速查找单个元素。

在 unordered_set 中，元素的值同时就是它的键，用来唯一标识自身。键不可修改，所以元素一旦存入容器就不能改动 —— 但可以插入、删除元素。

在底层，unordered_set 的元素不做排序，而是根据哈希值分到不同桶（bucket）中，这样就能直接依靠值快速访问单个元素，平均时间复杂度为常数级别。

按键访问单个元素时，unordered_set 的速度比 set 更快；但如果需要对一部分元素做范围遍历，它的效率通常更低。

该容器的迭代器至少满足前向迭代器（forward iterator）的要求。

（2）unordered_set 的接口说明

a. 构造函数

https://cplusplus.com/reference/unordered_set/unordered_set/unordered_set/

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

int main() {
// 1. 默认构造：空集合
unordered_set<int> s1;
s1.insert(1);
s1.insert(2);
s1.insert(3);
cout << "s1: ";
for (int x : s1) cout << x << " ";
cout << endl;

// 2. 拷贝构造：复制另一个集合
unordered_set<int> s2(s1);
cout << "s2(拷贝s1): ";
for (int x : s2) cout << x << " ";
cout << endl;

// 3. 迭代器区间构造：用数组初始化
int arr[] = { 10, 20, 30, 40, 50 };
unordered_set<int> s3(arr, arr + 5);
cout << "s3(从数组): ";
for (int x : s3) cout << x << " ";
cout << endl;

// 4. 列表初始化：直接指定元素
unordered_set<int> s4 = { 100, 200, 300, 400 };
cout << "s4(列表初始化): ";
for (int x : s4) cout << x << " ";
cout << endl;

// 5. 指定桶的数量
unordered_set<int> s5(20); // 创建20个桶
s5.insert(1);
s5.insert(2);
cout << "s5桶数: " << s5.bucket_count() << endl;

return 0;
}

b. 容量函数

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

int main() {
unordered_map<string, int> m;

cout << m.empty() << endl;
cout << m.size() << endl;

m["a"] = 1;
m["b"] = 2;

cout << m.empty() << endl;
cout << m.size() << endl;

m.clear();
cout << m.empty() << endl;
cout << m.size() << endl;

return 0;
}

empty() 空返回1，非空返回0
size() 元素个数

c. 迭代器

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

int main() {
unordered_map<string, int> m;
m["apple"] = 5;
m["banana"] = 3;
m["cherry"] = 7;

// begin() / end()：遍历
cout << "begin/end遍历: ";
for (auto it = m.begin(); it != m.end(); it++) {
cout << it->first << ":" << it->second << " ";
}
cout << endl;

// cbegin() / cend()：const遍历（不能修改）
cout << "cbegin/cend遍历: ";
for (auto it = m.cbegin(); it != m.cend(); it++) {
cout << it->first << ":" << it->second << " ";
}
cout << endl;

// 范围for（底层也是用begin/end）
cout << "范围for遍历: ";
for (auto& p : m) {
cout << p.first << ":" << p.second << " ";
}
cout << endl;

return 0;
}

d. 查询操作

https://cplusplus.com/reference/unordered_set/unordered_set/find/

https://cplusplus.com/reference/unordered_set/unordered_set/count/

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

int main() {
unordered_map<string, int> m;
m["a"] = 1;
m["b"] = 2;

auto it = m.find("a");
cout << (it != m.end()) << endl; // 1（找到）

it = m.find("c");
cout << (it != m.end()) << endl; // 0（没找到）

cout << m.count("a") << endl; // 1
cout << m.count("c") << endl; // 0

return 0;
}

注意：unordered_set 存储的元素本身就作为 key，不允许存在重复元素。所以它的 count() 函数返回值只能是 0 或者 1，最大值就是 1。返回 1 代表该元素存在，返回 0 代表不存在。

对比：unordered_multiset 允许存放重复元素，它的count返回值可以大于 1，代表这个值一共出现了多少次。

e. 修改操作

https://cplusplus.com/reference/unordered_set/unordered_set/insert/

https://cplusplus.com/reference/unordered_set/unordered_set/erase/

https://cplusplus.com/reference/unordered_set/unordered_set/clear/

https://cplusplus.com/reference/unordered_set/unordered_set/swap/

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

int main() {
unordered_map<string, int> m;

// insert
m.insert({"a", 1});
m.insert({"b", 2});
m["c"] = 3;

// erase
m.erase("b");

// clear
m.clear();
cout << m.size() << endl;

// swap
unordered_map<string, int> m1 = {{"x", 10}, {"y", 20}};
unordered_map<string, int> m2 = {{"z", 30}};
m1.swap(m2);
cout << m1.size() << " " << m2.size() << endl;

return 0;
}

f. 桶操作

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

int main() {
unordered_map<string, int> m;
m["a"] = 1;
m["b"] = 2;
m["c"] = 3;
m["d"] = 4;

cout << m.bucket_count() << endl; // 桶总数

cout << m.bucket_size(0) << endl; // 0号桶元素个数
cout << m.bucket_size(1) << endl; // 1号桶元素个数

cout << m.bucket("a") << endl; // a在几号桶
cout << m.bucket("b") << endl; // b在几号桶

return 0;
}

二.底层结构

之所以unordered 系列的关联式容器效率比较高，是因为其底层使用了哈希结构。

1.哈希概念

顺序结构、二叉平衡树这两种结构里，元素关键码和它实际存放的存储位置没有预先绑定的映射关系。所以查找目标元素时，只能依靠多次关键码比对来寻找。顺序查找的时间复杂度是 O(N)；二叉平衡树查找的时间复杂度是树高O(log₂ N) 。这类查找方式的效率，由查找过程中关键码的比较次数决定。

于是就有了一种理想查找思路：不需要多次比较，通过计算直接定位到目标元素的存储位置，一次访问就能拿到元素。思路是这样：设计一个哈希函数hashFunc，建立关键码与存储位置之间的映射关系。查找的时候，直接用这个函数算出位置，快速定位元素。

【插入元素】用待插入元素的关键码代入哈希函数，算出对应的存储位置，再把元素存到这个位置上。

【搜索元素】对目标关键码执行同样的哈希计算，将算出的结果当作存储地址，到该位置取出元素，再比对关键码。如果关键码一致，查找成功。

这种查找方式就叫做哈希（散列）方法；其中用来做转换的函数叫哈希（散列）函数；用这套规则构建出来的存储结构，叫做哈希表（Hash Table，也叫散列表）。

举个例子：现有数据集合 {1，7，6，4，5，9}。我们设定哈希函数：hash(key) = key % capacity。其中 capacity 代表哈希表底层数组的总空间大小。用取模作为哈希函数，计算出来的结果就是元素要存放的数组下标。

用该方法进行搜索查找不必进行多次关键码的比较，因此搜索的速度比较快。

2.哈希冲突

在搜索过程总，对于两个数据元素的关键字 ki 和 kj (i != j)，有 ki != kj，但有：Hash(ki) == Hash(kj) 即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为 “同义词”。

举例如下：

// 假设哈希函数：hash(key) = key % 10
hash(11) = 1
hash(21) = 1 // 11 ≠ 21，但哈希地址相同 –> 哈希冲突
// 11 和 21 互为同义词

3.哈希函数

引起哈希冲突，很常见的一个原因就是哈希函数本身设计得不好。

设计哈希函数一般要把握这几条原则：

定义域要覆盖所有需要存入的关键字。假设哈希表一共有 n 个存储位置，那么函数算出来的结果，也必须落在 0 ~ n‑1 这个下标区间里，不能越界。

计算出来的哈希地址尽量分散开，均匀分布在整个哈希表空间。尽量不要让大量关键字扎堆映射到同一个位置，以此减少冲突发生的概率。

计算逻辑不能太复杂。哈希函数本身运算要快，如果计算开销太大，会拖慢查找、插入的整体效率。

就算哈希函数设计得很不错，也做不到完全消除冲突。如果哈希表里存的数据越来越多，装填因子变大，冲突照样会变多。

4.常见哈希函数

a.直接定址法（常用）

直接定址法是比较基础的哈希构造方法，取关键字的线性函数结果作为哈希地址：Hash（Key）= A*Key + B，A、B 为自定义常数，A 也可以取 1，此时就是关键字本身直接作为哈希地址。

优点：实现简单，不会产生哈希冲突，地址分布天然均匀。

缺点：必须提前掌握关键字的整体分布范围；当关键字离散、跨度很大时，会造成哈希表数组空间巨大，大量位置闲置浪费内存。

适用场景：关键字范围较小、数值连续的场景。

举例：

计数排序，直接把元素值当作数组下标；

OJ 算法题统计字符频次，直接拿字符 ASCII 码作为下标映射；

把取值范围有限的 int 变量的值，直接当作哈希表的存储下标。

代码示例如下：

#include <iostream>
using namespace std;

// 直接定址法 Hash(Key) = A*Key + B
int hashFunc(int key, int A, int B)
{
return A * key + B;
}

int main()
{
const int A = 2;
const int B = 1;
int hashTable[20] = { 0 };

int keys[] = { 1,2,3,4 };
for (int k : keys)
{
int pos = hashFunc(k, A, B);
hashTable[pos] = k;
cout << "key=" << k << " 哈希地址=" << pos << endl;
}
return 0;
}

for (int k : keys) 这是 C++11 引入的范围 for（范围 for 循环）

2.除留余数法（常用）

开辟一块固定大小的哈希表空间，假设哈希表地址总数为 n。哈希函数公式就是说：Hash(key) = key % n，把关键字对 n 取模，得到的余数就是哈希地址，将元素存入哈希表对应下标位置。

补充：这里的n不是随便选的，尽量选质数，可以有效降低冲突发生概率；如果 n 取偶数，很多关键字的取模结果会扎堆，冲突会变多。

缺点

原生只支持整数关键字，字符串、浮点数不能直接拿来取模；这类数据需要先转换成整数，再做除留余数计算。

不同 key 算出来余数一样，就会产生哈希冲突，冲突无法彻底避免。

适用场景：绝大多数整数关键字哈希场景，实际写代码、考试出现频率很高。

代码示例如下：

#include <iostream>
using namespace std;

//除留余数法哈希函数
int hashFunc(int key, int n)
{
return key % n;
}

int main()
{
int n = 11; //哈希表容量，选质数，降低冲突
int hashTable[11] = { 0 };
int keys[] = { 1,4,5,6,7,9 };
int len = sizeof(keys) / sizeof(keys[0]);

for (int i = 0; i < len; i++)
{
int k = keys[i];
int addr = hashFunc(k, n);
cout << "key=" << k << " 哈希地址:" << addr << endl;
hashTable[addr] = k;
}
return 0;
}

问题补充：这里为什么要选择质数呢？

公式：Hash(key) = key % n

简单说：如果 n 是合数（非质数），关键字如果含有 n 的因子，取模结果就会大量聚集在部分下标，冲突变多；选质数可以打散这种聚集，让地址分布更均匀。

给大家举个通俗例子：假设 n=10（合数，因子 2、5）如果一组 key 全是偶数：2,4,6,8,12,14 key%10 结果只会落到 0,2,4,6,8，奇数下标 1、3、5、7、9 永远用不上，一半空间直接浪费，大量数据挤在少数位置，冲突暴增。

如果换成质数 n=11：同样这组偶数做取模，结果会分散到 0‑10 全部下标，不会扎堆。

简单图示一下：

3.平方取中法（了解）

把关键字做平方，再从平方后的结果里挑中间的几位，当作哈希地址。

举两个例子：关键字 1234，平方之后得到 1522756，截取中间 3 位 227，就是哈希地址。关键字 4321，平方得到 18671041，可以截取中间 3 位 671，也可以取 710。

之所以取中间部分，是因为数字平方后，中间几位会受原数字每一位的影响，更容易把地址打散开来。

适用情况：我们事先不清楚关键字的分布，并且关键字本身位数不算太大。

缺点：

截取出来的地址大小不好控制，有可能超出哈希表的下标范围，拿到结果往往还要再加工；

关键字数值大的时候，平方计算容易发生数据溢出；

现实开发里很少用，主要是课本理论了解。

4.折叠法（了解）

把一个长关键字，从左到右切成好几段，每段位数保持一致，最后一段不够长也没关系。把切出来的几段数字全部加在一起，最后按照哈希表的长度，拿相加结果的后面几位当作哈希地址。

折叠法有两种做法：

移位叠加：切出来的几段直接对齐相加。
间界叠加（翻转折叠）：相邻的分段首尾颠倒之后再相加，打散数据的效果会更好。

适用场景：不知道关键字的分布情况，而且关键字本身位数特别多，像手机号、长串编号这类数据就适合用。

缺点：

需要自己确定每一段切多少位；

还是会出现哈希冲突；

实际开发几乎不用，主要是课本概念了解。

举个例子：关键字 5824232416，我们需要 3 位的哈希地址，按 3 位一段切开：582、423、241、6 移位叠加计算：582 + 423 + 241 + 6 = 1252，取后 3 位 252，这就是哈希地址。

5.随机数法（了解）

挑选一个随机函数，把关键字传入随机函数，用函数返回的结果当作哈希地址:H(key) = random(key)。一般在各个关键字长度参差不齐的时候会考虑这个办法。

缺点：

同一个关键字，每次调用随机函数必须得到相同结果，普通的真随机函数不能拿来用，得用伪随机函数；

依旧会产生哈希冲突；

实际开发很少用，仅做理论了解。

注意点：不能用真正完全随机的函数，不然同一个 key 每次算出来地址不一样，后续查找就找不到数据了。

#include <iostream>
using namespace std;

//简单伪随机，同一个key输出固定值
int randomHash(int key)
{
//简单伪随机算法
return (key * 1103515245 + 12345) % 100;
}

int main()
{
int keys[] = { 12, 345, 6789 };
int len = sizeof(keys) / sizeof(keys[0]);
for (int i = 0; i < len; i++)
{
int k = keys[i];
int addr = randomHash(k);
cout << "key=" << k << " 哈希地址=" << addr << endl;
}
return 0;
}

6.数学分析法（了解）

现有一批 d 位的关键字，每一位上可以出现 r 种符号。这些符号在每一位上出现频次并不一样：有些位各个符号出现概率差不多，分布均匀；有些位就很集中，只有少数几种数值反复出现。

数字分析法就是结合哈希表的实际大小，挑选出符号分布比较均匀的若干位，直接拿这部分作为哈希地址。

举个实际例子：保存公司员工信息，拿手机号当作关键字。手机号前 7 位大多是运营商号段，大量员工的这部分数字会一模一样，这几位分布极不均匀，不能选用。我们就选取手机号末尾 4 位当作哈希地址。如果只截取之后冲突还是比较多，还可以对截取出来的数字做二次加工：

数字反转：1234 –> 4321
循环右移：1234 –> 4123
循环左移：1234–> 1432
分段叠加：1234，前两位加后两位，12+34=46

适用场景关键字位数比较大，并且我们提前掌握这批关键字的整体分布，其中存在部分数位分布均匀。

缺点必须事先分析全部关键字每一位的分布情况；换另一批数据，之前选好的位可能就不再均匀，这套哈希函数就失效了。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

//数字分析法示例：截取手机号后4位，可选择反转
int numAnalyseHash(string phone, bool reverse_flag = false)
{
string seg = phone.substr(phone.size() – 4, 4); //截取末尾4位
if (reverse_flag)
{
reverse(seg.begin(), seg.end());
}
return stoi(seg);
}

int main()
{
string phone1 = "13800138000";
string phone2 = "13800138123";
cout << phone1 << " 截取后4位哈希地址：" << numAnalyseHash(phone1) << endl;
cout << phone2 << " 截取后4位反转哈希地址：" << numAnalyseHash(phone2, true) << endl;
return 0;
}

但是：哈希函数设计再巧妙，只能降低冲突发生的概率，不可能完全消除哈希冲突。

5.哈希冲突解决

哈希冲突主要有两种解决方式：闭散列（开放定址法）和开散列（链地址法）。

a. 闭散列（开放定址法）

所有数据全部存放在哈希表数组内部，不新开其他空间。一旦出现哈希冲突，就按照固定规则，在原数组里继续往后找空位，把数据存进去。

特点：

只用一个数组，不借助链表
冲突多了容易扎堆、聚集
不能直接删除元素，直接删会打断查找路径，需要做删除标记
装填因子不能太大，否则冲突爆炸

b.开散列（链地址法）

哈希表数组只存每个位置的链表头结点。只要哈希地址相同的元素，直接挂在同一条链表后面。

特点：

冲突元素直接进链表，不会挤占数组空间
不会出现数据扎堆，效率更稳定
支持装填因子大于 1
需要额外开辟链表空间

三.解决哈希冲突两种常见方法的介绍

1.闭散列（开放定址法）

闭散列也叫开放定址法，是解决哈希冲突的常用方式。主要逻辑很简单：所有数据都只存在哈希表的数组里，不额外开链表。

当我们通过哈希函数算出一个存储位置时，如果这个位置已经被占了，就说明发生了哈希冲突。只要哈希表还没存满，数组里一定还有空位，我们就按照固定规则，向后不断寻找下一个空闲位置，把当前要存储字存进去。

插入数据流程：先通过哈希函数算出基准下标。如果该位置为空，直接存入；如果已经有数据，就持续往后找空位，找到就插入。如果数组全部占满，没有空位，就必须扩容哈希表。

查找数据流程：先计算哈希下标，直接定位到对应位置。取出数据后必须比对关键字：如果刚好是要找的数据，直接返回；如果不是，说明这里发生过哈希冲突，需要继续往后遍历探测位置，逐一比对，直到找到目标数据，或者遇到空位（说明数据不存在）。

核心特点：

全程只用一个数组，不用链表，结构简单

冲突数据会扎堆堆积，数据越多、冲突越严重，查找效率会下降

不能直接删除元素：直接清空位置会打断探测路径，导致后续数据查找不到，只能做删除标记

（1）找下一个空位置（闭散列探测方式）

当两个不同关键字，算出的哈希地址一模一样，就会出现哈希冲突。如果当前位置已经存了数据，就不能直接覆盖，需要往后找新的空位存放。

只要哈希表没有存满，数组里一定还有空闲位置，按照规则继续往后探测、依次查找空位。如果数组全部被占满，没有任何空位，就需要对哈希表进行扩容。

常用的找空位方式只有两种：

线性探测

二次探测（二次哈希探测）

没有 “二次线性探测” 这个说法，标准名称是二次探测。

① 线性探测（闭散列常用）

线性探测的规则很简单：一旦当前哈希位置发生冲突、已经被占用，就从冲突位置开始，挨个向后依次查找，一直找到第一个空位置为止，把数据存进去。

【插入】

大致插入流程

先用哈希函数算出当前元素对应的哈希下标。

如果这个位置是空的，直接插入数据。

如果位置已经有数据（发生哈希冲突），就从当前位置往后逐个遍历探测。

找到空位就插入；如果遍历完整个表都没有空位，就对哈希表进行扩容。

当我们在计算：

hash(44) = 44%10 = 4 哈希值(44) = 44%10 = 4

会出现哈希冲突：哈希地址 4 已经存放了数据，从冲突位置开始往后找空位置。

【删除】（闭散列）

使用闭散列解决哈希冲突的时候，不能直接物理删掉数组里的元素。如果直接把元素清空，会破坏线性探测的查找链路，导致其他发生过冲突而向后存放的数据找不到。

举例子： 4 存放在下标 4，44 哈希算出来也是下标 4，发生冲突，线性探测往后放到下标 8。如果直接把下标 4 的 4 清空，之后查找 44 的时候，探测走到下标 4 发现是空位，就会判定 44 不存在，直接结束查找，找不到真正存在下标 8 的 44。

所以闭散列一般用伪删除（标记删除），不去抹除数据，只给位置打上状态标记。给哈希表的每个位置设置三种状态：

enum State{
EMPTY, // 该位置为空，从未存放过数据
EXIST, // 该位置存有有效元素
DELETE // 元素曾经存在，已经被逻辑删除
};

插入：只可以向EMPTY的位置存放；遇到DELETE的位置，也可以复用该位置存入新数据。
查找：碰到DELETE标记不能停止，要继续向后探测；只有遇到EMPTY，才代表数据不存在。
删除：不把数据擦掉，仅仅把状态改成DELETE。

删除这里有一个缺点：就是说：伪删除只是打标记，不会释放空间。如果大量删除，表中DELETE标记会越来越多，降低查找效率，这种情况需要对哈希表扩容并重新整理。

【线性探测的实现】

代码如下：

// 注意：假如实现的哈希表中元素唯一，即key相同的元素不再进行插入
// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起

// 哈希表每个位置状态枚举
enum State{EMPTY, EXIST, DELETE};

template<class K, class V>
class HashTable
{
//存储单元结构体：保存键值对 + 位置状态标记
struct Elem
{
pair<K, V> _val; // key‑value键值对
State _state; // 标记：EMPTY空 / EXIST有效数据 / DELETE逻辑删除
};

public:
//构造函数：初始化哈希表，默认容量3
HashTable(size_t capacity = 3)
: _ht(capacity), _size(0)
{
//全部位置初始化为空状态
for(size_t i = 0; i < capacity; ++i)
_ht[i]._state = EMPTY;
}

//插入键值对，key重复返回false，插入成功返回true
bool Insert(const pair<K, V>& val)
{
_CheckCapacity(); //检测装填因子，达到阈值进行扩容
size_t hashAddr = HashFunc(val.first); //计算初始哈希地址
size_t startAddr = hashAddr;

//线性探测：跳过已经存有有效数据的位置；EMPTY、DELETE位置可以用于插入
while(_ht[hashAddr]._state != EMPTY && _ht[hashAddr]._state != DELETE)
{
//探测途中遇到相同key，代表重复，禁止插入
if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == val.first)
return false;

hashAddr++;
if(hashAddr == _ht.capacity())
hashAddr = 0; //到达数组末尾，回绕到数组头部

//绕回起点，代表表已经存满，无法插入
if(hashAddr == startAddr)
return false;
}

//找到合适位置，写入数据，标记为有效
_ht[hashAddr]._state = EXIST;
_ht[hashAddr]._val = val;
_size++; //有效元素计数+1
return true;
}

//查找key，找到返回数组下标，找不到返回-1
int Find(const K& key)
{
size_t hashAddr = HashFunc(key);
size_t startAddr = hashAddr;
//遇到EMPTY空位直接停止查找
while(_ht[hashAddr]._state != EMPTY)
{
//找到有效匹配key，返回下标
if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key)
return (int)hashAddr;

hashAddr++;
if(hashAddr == _ht.capacity())
hashAddr = 0; //探测越界，回绕头部

//完整遍历一圈，没有找到目标
if(hashAddr == startAddr)
break;
}
return -1; //没有该元素返回-1
}

//伪删除：只打DELETE标记，不清空数据，保护探测链路
bool Erase(const K& key)
{
int index = Find(key);
if(-1 != index)
{
_ht[index]._state = DELETE;
_size–; //有效元素数量减一
return true;
}
return false;
}

//返回当前有效元素个数
size_t Size()const
{
return _size;
}
//判断哈希表是否为空
bool Empty() const
{
return _size == 0;
}
void Swap(HashTable<K, V>& ht);

private:
//扩容检测，装填因子超标则扩容
void _CheckCapacity()
{
//此处仅声明，扩容逻辑：开辟更大vector，把EXIST状态元素重新哈希插入新表
}

//哈希函数：除留余数法，计算哈希地址
size_t HashFunc(const K& key)
{
return key % _ht.capacity();
}
private:
vector<Elem> _ht; //底层数组，存放所有哈希表单元
size_t _size; //记录有效元素（EXIST）的数量
};

线性探测

优点：实现逻辑简单，编码容易。

缺点：容易产生聚集（数据堆积）。发生冲突后，后续元素会顺着探测路径连续占用位置，就算关键字原本哈希地址并不相同，也会挤在一片连续区域。堆积出现之后，插入、查找、删除都要执行更多次探测比较，哈希表整体搜索效率明显下降。

如何缓解呢？

出现堆积之后，插入和查找的效率都会大幅下降。插入元素时，要从冲突位置不断向后遍历，才能找到空闲位置；查找元素时，同样需要顺着探测路径多次比对，只有探测遇到空位置，才能判定目标元素不存在。大量的探测比较，直接拉低整体搜索效率。

这里我先给大家结论，后面会有解答：

缓解手段： ①使用二次探测，缓解数据聚集； ②控制装填因子，及时扩容； ③改用开散列链地址法。

② 二次探测

线性探测会出现数据堆积，原因就是冲突之后只能挨着往后一个一个找空位，冲突的数据就挤到一块了。

二次探测就是用来改善这个堆积问题。探测位置公式：Hash(key) = key % n + i² ( i = 1,2,3… )，通过哈希函数 Hash(key) 计算出元素的关键码 key 对应的位置再加上 i 的平方，n 是表的大小。

注意：不是直接 key%n+i^2。出原始下标先用除留余数算，发生冲突后，再叠加i的平方做偏移，一般正负偏移都会用。

简单流程：

用key%n算出元素本该存放的位置

如果位置被占，就按i^2算新位置，i 不断增大，直到找到空位

优点：多个数据冲突到同一个起始位置时，二次探测靠平方偏移把数据打散，不会扎堆挤在相邻位置，缓解线性探测的数据堆积问题。

缺点：

只能缓解堆积，没法彻底消除，还会产生次级聚集；

就算表里还有空位，也有可能找不到可用位置；

哈希表容量尽量选素数，装填因子最好控制在 0.5 以内，超了就要扩容。

如果上面要插入 44，产生冲突，使用解决后的情况为：

二次探测装填因子说明：

研究表明：当哈希表长度为质数，且装填因子 α ≤ 0.5时，二次探测一定能找到空位完成插入，并且每个位置最多只会被探测一次。

也就是说只要哈希表还留有一半空闲位置，就不会出现找不到插入位置的问题。搜索的时候不用考虑表存满的情况，但做插入操作时，要保证装填因子不能超过 0.5；一旦超过，就必须扩容。

但有缺点：二次探测空间利用率不高，最多只能用到一半的表空间，这是闭散列（开放定址）哈希表的短板

公式：有效元素个数/哈希表的总长度

【二次探测相比线性探测的好处】

如果多个数据冲突到同一个位置，二次探测会把这些数据打散存到不同地方，不会像线性探测那样，冲突的数据挤成一大片，出现数据堆积。

【插入】

假设要插入 333 和 33，产生冲突，分别使用线性探测和二次探测，解决后的情况为：

【闭散列的实现】

哈希表其实就是数组，只不过是按照某种映射关系把元素存放进去的数组。

1.怎么往哈希表里插入元素？

先看要不要扩容：算一下负载因子，如果超过规定阈值，就先做扩容。
接着用哈希函数算出元素一开始该放的下标。
如果这个位置已经存有数据（状态 EXIST），代表出现哈希冲突，用线性探测或者二次探测继续找可用空位，找到之后再插入。
如果位置是空的（EMPTY），或者是之前删除留下的位置（DELETE），就直接把元素插进去。

2.怎么在哈希表里查找元素？

先判断哈希表是不是空表，如果是空，直接查找失败，返回 nullptr。

用哈希函数算出目标元素对应的起始下标。如果这个位置不是空白（状态是 EXIST 或者 DELETE），就开始向后探测查找，碰到 EMPTY 空位就直接停止。

探测途中遇到状态为 EXIST 的元素，就对比是不是要找的值，匹配上就查找成功，返回元素地址；不匹配就继续往下找。
如果一路查到 EMPTY 空位都没找到目标，说明表里没有这个元素，返回 nullptr。

如果一开始算出来的位置就是 EMPTY，直接返回 nullptr。

3.怎么标记哈希表每个位置的存放状态？

不能直接拿 0 或者‑1 当做空位置标记，因为实际存储的数据本身就有可能是 0、‑1，会出现混淆。

解决办法：哈希表的每个位置，除了存数据本身，额外再加一个状态标记，用来记录这个位置是三种状态之一：空、已有元素、已删除。

4.怎么删除哈希表里的元素？

使用开放定址（闭散列）解决冲突的时候，不能直接把元素物理删掉。如果直接清空该位置，会打断探测链路，导致其他元素找不到。

举个例子，如果直接删掉 333，这个位置直接变成空。后续去查找 44 的时候，探测到这个空位就直接停止，就会误以为 44 不存在。

所以线性探测一般用伪删除（标记删除）。每个位置除了存数据，额外带一个状态标记：空、存在、已删除。删除的时候只把状态改成 “已删除”，数据不动，不直接清空位置。查找时遇到 “已删除” 标记会继续往后探测，不会直接终止查找。

问题思考：

【思考 1】

除留余数法要求 key 得是整数才能做取模运算，那是不是意味着闭散列哈希表只能存整型 key？如果是字符串或者自定义类型该怎么办？

像 string 这类类型，没法直接进行取模计算哈希下标。解决方案就是提供对应的哈希仿函数，把非整型的 key 转换成一个整数，之后再用除留余数法算出存储位置。

// 默认哈希仿函数：用于size_t，以及可以隐式转换为size_t的整型类型
template<class K>
struct HashFunc
{
// key：元素的关键码
// 如果key是整型，直接转成size_t返回
// 如果是浮点数，会发生隐式转换为size_t（浮点数转整数会截断小数部分）
size_t operator()(const K& key)
{
return key;
}
};

// 专门处理string类型的哈希仿函数，把string转为可用于取模的size_t
struct HashFuncString
{
size_t operator()(const string& key)
{
// 方式1：累加每个字符的ASCII码
// 缺点：不同字符串有可能累加得到相同哈希值，发生哈希冲突，不能保证key唯一
size_t hash_key = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash_key += key[i];
}
return hash_key;
}
};

【思考2】

unordered 系列容器底层是哈希表，但平时使用的时候，我们并没有手动传哈希仿函数。 string 作为 key 又特别常用，总不能每次用 string 都自己手写一份哈希仿函数，那它内部是怎么处理的？

答案：对 string 类型，给哈希仿函数写模板特化版本。当传入的 key 是 string 时，编译器就会匹配到这个特化版本，自动调用对应的哈希转换逻辑，不用我们手动传仿函数。

// 默认仿函数类（针对size_t类型和能够隐式类型转换成size_t的类型）
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};

// 特化仿函数（把string类型转换成可以取模的size_t类型）
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash_key = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash_key *= 131;
hash_key += key[i];
}
return hash_key;
}
};

通用模板 HashFunc<K> 适用于整型，还有能隐式转成 size_t 的类型。直接返回 key，后面拿这个值做除留余数取模，就能算出哈希下标。

注意：string 不能用这个通用模板，string 没法隐式转换成 size_t，直接用会编译报错。

模板特化 HashFunc<string> template<> 表示这是全特化。当模板参数 K 是 string 的时候，编译器会优先选用这个特化版本，不会再跑上面的通用模板。

算法逻辑：hash_key = hash_key * 131 + 当前字符的 ASCII 值先乘质数 131，再加字符。相比直接把字符 ASCII 简单相加，能明显减少不同字符串算出同一个哈希值的情况，降低冲突。最后返回 size_t 类型的哈希值，外部拿到这个值再对哈希表容量取模，得到存放的下标。

为什么不需要手动传仿函数？

用 string 当 key 的时候，编译器自动匹配这个特化仿函数，我们写代码时不用手动传，效果和 unordered_map 里面的逻辑差不多。

小提示：就算用 131 加权算法，也没法彻底消除哈希冲突，只是冲突变少。出现冲突，还是要靠线性探测或者二次探测这类开放定址方案处理。

【闭散列的结构（KV模型）】

// 闭散列
namespace close_hash
{
// 标记哈希表中某个位置的存储状态
enum Status
{
EMPTY, // 此位置空
EXIST, // 此位置已有元素
DELETE // 此位置元素已被删除
};

// 定义哈希表中元素的结构
template<class K, class V>
struct HashData
{
pair<K, V> _kv; // 键值对
Status _status = EMPTY; // 存储状态标记，默认为空
};

// 仿函数（解决哈希函数采用除留余数法时，将不能取模的类型转换成可以取模的size_t类型）
// 默认仿函数类
template<class K>
struct HashFunc
{
// 针对size_t类型和能够隐式类型转换成size_t的类型
size_t operator()(const K& key)
{
return key;
}
};

// 特化仿函数
template<>
struct HashFunc<string>
{
// 把string类型转换成可以取模的size_t类型
size_t operator()(const string& key)
{
size_t hash_key = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash_key *= 131;
hash_key += key[i];
}
return hash_key;
}
};

// 定义哈希表（KV模型）
// Hash = HashFunc<K>：仿函数，给一个默认的仿函数
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
// 构造、拷贝构造、赋值重载、析构都不需要写，调用vector的就行了
HashData<K, V>* Find(const K& key); // 查找元素
bool Insert(const pair<K, V>& kv); // 插入元素
bool Erase(const K& key); // 删除元素
private:
vector<HashData<K, V>> _tables; // 哈希表底层容器
size_t _n = 0; // 存储的有效元素个数，默认为0

// 注意：因为元素不是挨着挨着存的，所以需要一个变量去表示有效元素个数
};
}

【查找元素】

这里写了线性探测 / 二次探测两个版本。

HashData<K, V>* Find(const K& key)
{
// 先检查哈希表是否为空
if (_tables.size() == 0) // 说明查找失败
{
return nullptr;
}

// 1、先通过哈希函数计算出要查找元素在哈希表中对应的位置
size_t start = Hash()(key) % _tables.size();
size_t i = 0;
size_t index = start;

// 2、该位置不为空
while (_tables[index]._status != EMPTY)
{
/*
* 当前位置存储状态为存在，才去判断当前位置是不是要查找的元素。为什么呢？
* 因为我们采用标记的伪删除法来删除一个元素，并没有清除元素的关键码，所以还可以被查找到
*/
if (_tables[index]._status == EXIST && key == _tables[index]._kv.first)
{
return &_tables[index]; // 返回该元素的地址
}

i++;
index = start + i; // 线性探测
// index = start + i * i; // 二次探测

index %= _tables.size(); // 如果超出表尾了，又从表头继续开始找
}
// 3、该位置为空
return nullptr;
}

【插入元素】

1.为什么闭散列要控制存放的元素数量？

如果表里元素太多，插入的时候就很容易出现哈希冲突。冲突一多，不管是插入还是查找，效率都会掉得很厉害。

查找的时候，要一直探测直到碰到真正的空位才会停下。所以闭散列不能把表存满。一旦全部占满，没有 EMPTY 空位，去查一个不存在的 key，代码就会陷入死循环。

所以有效元素数量涨到一定程度，就必须做扩容。减少冲突，保证读写的效率。

2.哈希表什么情况下进行扩容？又是如何扩容？

这里我们引入一个东西：负载因子

负载因子越大，哈希表里存放的元素就越多，出现哈希冲突的概率越高，但内存空间浪费更少。
负载因子越小，哈希表里存放的元素就越少，哈希冲突概率越低，但会浪费更多存储空间。

void CheckCapacity()
{
if(_size * 10 / _ht.capacity() >= 7)
{
HashTable<K, V, HF> newHt(GetNextPrime(_ht.capacity()));
for(size_t i = 0; i < _ht.capacity(); ++i)
{
if(_ht[i]._state == EXIST)
newHt.Insert(_ht[i]._val);
}
Swap(newHt);
}
}

1.if(_size * 10 / _ht.capacity() >= 7) 判断扩容条件这是负载因子的判断，用整数运算避免浮点数。负载因子 = _size / capacity，这里判断负载因子≥0.7 就扩容。 _size *10 / capacity >=7等价于 _size / capacity >= 0.7。

注意：线性探测一般阈值取 0.7；二次探测阈值一般取 0.5。

2.HashTable<K, V, HF> newHt(GetNextPrime(_ht.capacity())); 创建新哈希表，调用GetNextPrime()获取比原容量更大的质数作为新表容量。闭散列除留余数法，容量选质数，有助于降低哈希冲突。

3.遍历旧表做重新插入

for(size_t i = 0; i < _ht.capacity(); ++i)
{
if(_ht[i]._state == EXIST)
newHt.Insert(_ht[i]._val);
}

只搬移状态为EXIST的有效元素。 DELETE、EMPTY位置直接丢弃，伪删除标记不会拷贝到新表。放到新表要调用Insert，因为新表容量变了，哈希下标全部要重新计算，不能直接拷贝下标。

4.Swap(newHt); 交换新旧哈希表内部资源。底层容器、有效元素数量全部交换。交换完成后，旧表的数据就交给局部对象newHt，函数结束局部对象析构，自动释放旧内存。

比如闭散列的容量是10，负载因子是 0.7，10 * 0.7 = 7，也就是说，当容量超过 7 的时候就会进行扩容操作。

这里有几点注意事项：

【注意1】

如果闭散列容量是 10，里面有 n 个有效元素，怎么判断负载因子是否超过 0.7？

不能直接写 if (n / 10 >= 0.7)。 n 和 10 都是 int，整数除法会直接取整，算出来结果只能是 0，判断失效。

注意：(double)(n / 10) >= 0.7 这行写法是错的！括号位置不对，是先做整数除法，再强转 double，依旧会出错。

两种正确写法：

强转版本（把 n 先转 double）

if ((double)n / 10 >= 0.7)

整数运算，避免浮点数：两边同时乘 10

if (n * 10 / 10 >= 7)

我在这里示例容量是 10，实际代码要替换成真实的表容量。

【注意 2】

如果允许插入重复的 key，闭散列表里就会多个位置存一样的关键码，后续查找、删除的时候就会出现逻辑混乱。那怎么避免存重复数据？

插入之前先调用 Find (key) 查一遍。如果查到这个 key 已经存在哈希表里面，就直接放弃插入；不存在才执行插入操作。

bool Insert(const pair<K, V>& kv)
{
// 防止数据冗余
if (Find(kv.first) != nullptr)
{
return false; // 若待插入元素的关键码已存在表中，则插入失败
}

// 1、如果表为空或表的负载因子>=0.7，那么需要检查哈希表是否需要扩容
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7) // 注意
{
// 计算新容量（按2倍扩容）
size_t new_size = _tables.size() == 0 ? 10 : _tables.size() * 2;

// 开始扩容
// 定义一个新的哈希表（局部变量）
HashTable<K, V, Hash> new_hash_table;
new_hash_table._tables.resize(new_size); // 更改新表容量

// 遍历旧表中的所有元素，重新计算它在新表中的位置，一一插入到新表中
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._status == EXIST) // EXIST: 此位置已有元素
{
new_hash_table.Insert(_tables[i]._kv); // 递归调用Insert，复用代码
}
}

// 交换新表和旧表的内容（即交换新旧表vector的内容）
_tables.swap(new_hash_table._tables);
}

// 2、再通过哈希函数计算出待插入元素在哈希表中的位置
// 这里要模size()，不能模capacity()，因为vector中能存放元素的个数为size()
size_t start = Hash()(kv.first) % _tables.size();
size_t i = 0;
size_t index = start;

// 3、该位置有元素，说明发生了哈希冲突，则使用线性检测找到下一个空位置
while (_tables[index]._status == EXIST) // EXIST: 表示该位置已经有元素
{
i++; // 往后找
index = start + i; // 线性探测
// index = start + i * i; // 二次探测

// 如果超出表尾了，又从表头继续开始找
index %= _tables.size();
}

// 4、该位置没有元素则直接插入
_tables[index]._kv = kv;
_tables[index]._status = EXIST; // 标记该位置的存储状态：存在
_n++; // 有效元素个数+1

// 5、插入成功，返回true
return true;
}

/*
1.去重判断：调用Find查找key，key已存在直接返回false，禁止重复key。
2.扩容判断：表为空或者负载因子>=0.7触发扩容；使用整数运算_n*10/_tables.size()>=7，规避浮点数。
3.扩容逻辑：创建局部新哈希表，resize开辟新空间；遍历旧表，只迁移_status为EXIST的有效元素，调用Insert，在新表重新计算哈希下标。
4.swap交换vector，局部对象出作用域自动释放旧表资源。
5.计算起始下标：仿函数算出哈希值，对_tables.size()取模，不能用capacity。
6.线性探测：只避开EXIST已占用位置，EMPTY、DELETE位置均可插入；index取模实现循环回绕。
7.写入键值对，状态置EXIST，有效元素计数_n++，返回true。
注意：扩容后旧表DELETE伪删除标记全部丢失；二次探测替换index那一行代码即可。
*/

【测试如下】插入元素过程中，分别用线性探测和二次探测来找下一个空位置。

【删除元素】

// 删除元素
bool Erase(const K& key)
{
// 查找，判断该元素是否在表中
HashData<K, V>* ret = Find(key);

// 待删除元素的关键码不在表中
if(ret == nullptr)
{
return false;
}

// 待删除元素的关键码在表中
ret->_status = DELETE; // 伪删除，标记该位置的存储状态为：删除
_n–; // 有效元素个数-1

return true;
}
// /*
// 解析：
// 1.调用Find(key)查找目标节点，找不到返回nullptr，直接返回false代表删除失败。
// 2.闭散列不能直接清空节点内容，使用伪删除，仅把状态置为DELETE，不清空kv。
// 3.不能直接清空节点，否则会破坏探测链，导致后面的元素查找失败。
// 4._n减1，DELETE状态不计入有效元素数量。
// 5.返回true代表删除成功。
// 注意：扩容拷贝元素时，DELETE标记的节点会被丢弃，不会迁移到新表。
// */

【闭散列的效率】从上面能够看出，开放寻址法（闭散列）并不是完美的方案。最好情况下，一次命中，时间复杂度为 O (1)；最坏情况下需要遍历整张哈希表，时间复杂度退化到 O (n)；平均时间复杂度为 O (1)，前提是控制好负载因子。

2.开散列(链地址法）

（1）开散列概念

开散列也叫哈希桶、链地址法。先用哈希函数算出关键码对应的哈希位置，哈希地址一样的元素就归到同一组，这一组就叫一个桶。桶里面的元素用单链表串起来，各个链表的头结点存放在哈希表数组中。

查找数据的时候，先做哈希运算拿到数组下标，再遍历这个桶的链表比对 key 就行。看上去复杂度跟闭散列差不多，实际不一样。哈希冲突不会频繁发生，再加上会动态扩容，冲突概率进一步降低，桶里的链表不会像闭散列那样出现大量元素扎堆堆积的现象。

从上面两幅图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

（2）开散列实现

【开散列的结构（KV模型）】

【思考】

除留余数法要求 key 是整型才能做取模运算，那是不是代表开散列只能存整型的 key？那字符串、自定义类型这类 key 该怎么处理？

如果 key 是 string 或者其他自定义类型，可以传入对应的仿函数，把无法直接取模的类型，转换成 size_t 类型的哈希值，之后再做取模计算。

namespace hash_bucket
{
// 定义哈希表节点结构（KV模型）
template<class K, class V>
struct HashNode
{
pair<K, V> _kv; // 数据域：键值对
HashNode<K, V>* _next; // 后继指针

// 构造函数
HashNode(const pair<K, V>& kv)
: _kv(kv)
, _next(nullptr)
{}
};

/*
* 哈希仿函数：除留余数法只支持整型取模，
* 对于string、自定义类等非整型key，通过该仿函数转换得到size_t类型哈希值
*/
// 默认仿函数类，处理整型，可以直接强转为size_t的类型
template<class K>
struct HashFunc
{
// 针对size_t类型和能够隐式类型转换成size_t的类型
size_t operator()(const K& key)
{
return key;
}
};

/*
* string特化版本：字符串不能直接取模，遍历字符计算哈希值返回size_t
* 使用131作为乘数，减少哈希冲突概率
*/
// 特化仿函数
template<>
struct HashFunc<string>
{
// 把string类型转换成可以取模的size_t类型
size_t operator()(const string& key)
{
size_t hash_key = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash_key *= 131;
hash_key += key[i];
}
return hash_key;
}
};

/*
* 开散列哈希桶（链地址法）
* K：键类型，V：值类型，Hash：哈希仿函数，提供默认HashFunc<K>
* _tables：vector存放每个桶链表的头指针
* _n：统计哈希表里有效节点总数量，用于计算负载因子
*/
// 定义哈希表结构（KV模型）
// Hash = HashFunc<K>：仿函数，给一个默认的仿函数
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;

public:
// 构造、拷贝构造、赋值重载需要自己写，因为这里是哈希桶结构
// …
/*
* 析构函数：释放全部桶内链表节点
* 遍历vector数组，对每个不为空的桶，遍历单链表逐个delete释放节点，防止内存泄漏
*/
~HashTable() // 析构函数
{
// 遍历哈希表，找到不为空的哈希桶
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur) // 哈希桶不为空，释放哈希桶中的所有节点
{
Node* next = cur->_next; // 记录cur指向节点的下一个节点
delete cur; // 释放节点
cur = next; // 继续去释放下一个节点
}
_tables[i] = nullptr;
}
_n = 0;
}

Node* Find(const K& key); // 查找节点
bool Insert(const pair<K, V>& kv); // 插入节点
bool Erase(const K& key); // 删除节点

private:
vector<Node*> _tables; // 哈希表存储各链表的头结点地址
size_t _n = 0; // 哈希表中有效节点的个数，缺省为0
};
}

【查找节点】

开散列的查找效率，主要取决于对应桶里面链表的长度，链表越短查找越快。

查找节点思路：先判断哈希表是不是空表，如果是空，直接返回 nullptr。用哈希函数算出 key 对应的桶下标，接着遍历这个桶里的链表挨个比对 key。找到就返回该节点的地址，遍历完没找到就返回空。

Node* Find(const K& key)
{
// 1、先检查哈希表是否为空
if (_tables.size() == 0)
{
return nullptr;
}
// 哈希表数组还没有开辟空间，不存在任何数据，直接返回空。

// 2、再通过哈希函数计算出该元素所映射的位置（即映射的哈希桶位置）
size_t index = Hash()(key) % _tables.size();
// 调用哈希仿函数得到哈希值，对数组长度取模，算出key落在哪个桶。

// 3、遍历该哈希桶，查找节点
Node* cur = _tables[index]; // cur指向该哈希桶
while (cur) // 遍历该哈希桶的所有节点
{
if (key == cur->_kv.first)
{
return cur; // 找到了，返回节点地址
}
cur = cur->_next;
}
// 只遍历当前桶的单链表，挨个比对key，匹配就返回节点地址。

// 4、没找到，返回空
return nullptr;
// 链表遍历完，没有匹配的key，返回nullptr。
}

【插入节点】

1.负载因子

哈希桶一般把负载因子控制在 1 以内，代表平均每个桶挂 1 个节点；负载因子等于 1 的时候就要做扩容。

2.开散列扩容逻辑

桶的总数量固定，不停插入元素后，部分桶里的链表会越变越长。极端情况下一个桶挂大量节点，查找效率会明显下降，所以要在合适时机扩容。开散列理想状态是每个桶只挂一个节点，再插入新元素就极易产生冲突。所以约定：有效元素总数等于桶的数量时，触发扩容。

思路：

先判断要不要扩容：哈希表为空，或者负载因子达到 1，就执行扩容。
扩容时，把旧表里全部有效节点重新计算哈希，迁移到新桶数组，再交换新旧哈希表。
接着用哈希函数算出待插入 key 对应的桶下标。
遍历当前桶检查 key 是否已经存在：不存在就头插新节点； key 已经存在，不允许重复插入，直接插入失败。

bool Insert(const pair<K, V>& kv)
{
// 1、扩容检查
// 当哈希表为空，或者负载因子（元素个数/桶个数）>= 1 时，需要扩容
if (_n == _tables.size())
{
// 计算新容量：如果当前为0则设为10，否则扩大为2倍
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
// （注：也可以用素数表扩容，这里注释掉了）
// size_t newSize = GetNextPrime(_tables.size());

// 创建新哈希表
vector<Node*> newTables;
newTables.resize(newSize);

// 2、转移旧表节点到新表
// 遍历旧表的每一个桶
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i]; // cur指向当前桶的第一个节点

// 如果当前桶不为空，开始转移
while (cur != nullptr)
{
Node* next = cur->_next; // 保存下一个节点，防止丢失

// 重新计算当前节点在新表中的位置（哈希地址）
size_t index = Hash()(cur->_kv.first) % newSize;

// 头插法将当前节点插入新表的对应桶中
cur->_next = newTables[index];
newTables[index] = cur;

cur = next; // 继续处理下一个节点
}
// 当前桶所有节点转移完毕，将旧表指针置空
_tables[i] = nullptr;
}
// 旧表和新表交换，旧表（vector）会自动释放
_tables.swap(newTables);
}

// 3、计算插入位置
// 用哈希函数计算 key 对应的桶号
size_t index = Hash()(kv.first) % _tables.size();

// 4、查重
// 遍历该桶，检查 key 是否已存在（不允许重复）
Node* cur = _tables[index];
while (cur)
{
if (kv.first == cur->_kv.first)
{
return false; // key 已存在，插入失败
}
cur = cur->_next;
}

// 5、头插新节点
Node* newNode = new Node(kv); // 创建新节点
newNode->_next = _tables[index]; // 新节点指向原第一个节点
_tables[index] = newNode; // 桶头指向新节点
_n++; // 元素个数+1

return true; // 插入成功
}

（3）开散列的思考

1.只能存储key为整形的元素，其他类型怎么解决？

//1、默认哈希函数（处理整型）
// 哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法
// 整形数据不需要转化
template<class T>
class DefHashF
{
public:
size_t operator()(const T& val)
{
return val; // 整型直接返回自身
}
};

// 2、字符串哈希函数（处理字符串）
// key为字符串类型，需要将其转化为整形
class Str2Int
{
public:
size_t operator()(const string& s)
{
const char* str = s.c_str(); // 获取C风格字符串
unsigned int seed = 131; // 种子值（常用质数：31、131、1313等）
unsigned int hash = 0; // 哈希值初始为0

// 遍历字符串每个字符
while (*str)
{
hash = hash * seed + (*str++); // 累乘加字符
}
return (hash & 0x7FFFFFFF); // 取31位，保证非负（去掉符号位）
}
};

// 3、哈希桶类（使用哈希函数）
// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
template<class V, class HF>
class HashBucket
{
// …
private:
// 哈希函数：将key转为整型，再模容量得到桶号
size_t HashFunc(const V& data)
{
return HF()(data.first) % _ht.capacity(); // HF()是哈希函数对象
}
};

2.除留余数法，模数最好选用素数。那扩容时怎么快速拿到接近两倍大小的素数？

哈希表扩容的时候，调用GetNextPrime(_tables.size())获取下一个素数。这样既能让哈希表大小保持为素数，实现近似二倍的扩容效果，计算哈希下标时也可以对素数取模，减少哈希冲突。

// 素数表扩容 =
// 素数表，放了经过筛选的28个素数
// 作用：哈希表扩容时，选择素数作为桶的个数，可以减少哈希冲突
// 原因：取模运算时，素数的模数能更好地分散数据，避免周期性聚集
size_t GetNextPrime(size_t prime)
{
// 素数表（28个经过筛选的素数）
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};

// 遍历素数表，找到第一个大于当前容量的素数
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i]; // 返回合适的素数作为新容量
}
return primeList[i]; // 若都比当前容量小，返回最后一个
}

3.扩容问题

哈希桶负载因子一般控制在 1 以内，也就是平均每个桶挂一个节点，负载因子等于 1 就需要触发扩容。

如果遇到极端情况，所有节点全都挂在同一个桶里，链表会越变越长。查找、删除的效率会大幅下降；但插入是头插，受这个问题的影响不大。

那GetNextPrime(_tables.size())是解决扩容大小的问题。还有另一种处理思路：当单个桶里链表长度过长时，可以把链表转换成红黑树来提升查询性能。

不过 C++ 标准库的哈希桶没有采用这套方案，Java 的 HashMap 是这么实现的。红黑树的查询效率比长链表更高，JDK 里默认规则：单个桶节点数量超过 8，链表就转为红黑树。

【删除节点】

思路：

先判断哈希表是不是空表，如果是空，直接删除失败。
用哈希函数算出 key 对应的桶下标。
遍历当前桶的链表，找到目标节点，同时记录它的前驱节点。如果找到了目标节点，区分是头节点还是普通中间节点，按对应逻辑完成删除；
遍历完没找到该节点，删除失败。

// 删除节点
bool Erase(const K& key)
{
// 1、先判断哈希表是否为空
if (_tables.size() == 0)
{
return false; // 表为空，删除失败
}

// 2、通过哈希函数计算出待删除节点所映射哈希桶的位置
size_t index = Hash()(key) % _tables.size();

// 3、遍历该哈希桶，查找待删除节点，以及它的前驱节点
Node* cur = _tables[index]; // cur指向当前桶的第一个节点
Node* prev = nullptr; // 记录前驱节点（用于删除非头节点）
while (cur)
{
if (key == cur->_kv.first) // 找到该节点了
{
//情况1：删除头节点
if (cur == _tables[index]) // cur是头节点
{
_tables[index] = cur->_next; // 桶头指向下一个节点
}
//情况2：删除非头节点
else // cur不是头节点
{
prev->_next = cur->_next; // 前驱节点跳过cur，指向cur的下一个
}

delete cur; // 释放节点内存
cur = nullptr; // 置空，避免野指针
_n–; // 有效节点个数-1

return true; // 删除成功
}
prev = cur; // 更新前驱指针
cur = cur->_next; // 继续遍历下一个节点
}
return false; // 遍历完没找到，删除失败
}

【开散列的效率】

开散列扩容时选用接近两倍大小的素数，目的就是尽可能降低哈希冲突。理想情况下哈希表的时间复杂度可以达到 O (1)，一旦发生大量哈希冲突，桶内链表变长，实际的查询效率就不再是 O (1)。

（4）开散列与闭散列对比

链地址法（开散列）每个节点要多存一个指针，看上去会多消耗一点内存。

但闭散列（开放地址法）必须预留大量空闲位置，才能保证查找性能，比如二次探查法要求负载因子不能超过 0.7。数组里每个存储单元占用的空间远大于一个指针。综合算下来，开散列实际反而更省内存。

【C++】《【C++】unordered_map 与 unordered_set 完整解析以及哈希底层、哈希冲突、闭散列与开散列》

一.unordered 系列关联式容器

1.unordered_map

（1)unordered_map介绍

（2）unordered_map 的接口说明

2.unordered_set

(1)unordered_set 的介绍

（2）unordered_set 的接口说明

二.底层结构

1.哈希概念

2.哈希冲突

3.哈希函数

4.常见哈希函数

5.哈希冲突解决

a. 闭散列（开放定址法）

b.开散列（链地址法）

三.解决哈希冲突两种常见方法的介绍

1.闭散列（开放定址法）

2.开散列(链地址法）

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

一.unordered 系列关联式容器

1.unordered_map

（1)unordered_map介绍

（2）unordered_map 的接口说明

2.unordered_set

(1)unordered_set 的介绍

（2）unordered_set 的接口说明

二.底层结构

1.哈希概念

2.哈希冲突

3.哈希函数

4.常见哈希函数

5.哈希冲突解决

a. 闭散列（开放定址法）

b.开散列（链地址法）

三.解决哈希冲突两种常见方法的介绍

1.闭散列（开放定址法）

2.开散列(链地址法）

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发