C++【初识哈希】

✨个人主页： 北 海
🎉所属专栏： C++修行之路
🎃操作环境： Visual Studio 2019 版本 16.11.17

文章目录

• 🌇前言
• 🏙️正文
• • 1、哈希思想
  • 2、哈希函数
  • • 2.1、哈希函数的设计原则
    • 2.2、常见的哈希函数
  • 3、哈希冲突
  • • 3.1、冲突的原因
    • 3.2、解决方法
  • 4、unordered_set / unordered_map
  • • 4.1、使用
    • 4.2、与 set/map 的区别
    • 4.3、性能对比
• 🌆总结

🌇前言

哈希（Hash）是一个广泛的概念，其中包括哈希表、哈希冲突、哈希函数等，核心为 元素（键值） 与 存储位置（哈希值） 之间的映射关系，哈希值 可以通过各种哈希函数进行计算，需要尽量确保 “唯一性”，避免冲突，除此之外，哈希函数还可用于 区块链 中，计算 区块头（Head）中的信息，本文将带你认识哈希，学习其中的各种知识

🏙️正文

1、哈希思想

哈希（Hash） 是一种 映射 思想，规定存在一个唯一的 哈希值 与 键值 之前建立 映射 关系，由这种思想而构成的数据结构称为 哈希表（散列表）

哈希表中的数据查找时间可以做到 O(1)

这是非常高效的，比 AVL树 还要快

哈希表 中 插入数据 和 查找数据 的步骤如下：

• 插入数据：根据当前待插入的元素的键值，计算出哈希值，并存入相应的位置中
• 查找数据：根据待查找元素的键值，计算出哈希值，判断对应的位置中存储的值是否与 键值 相等

比如在 数组 中利用哈希思想，构建哈希表，存储数据：5、49、27、38、55

假设此时 数组 的大小 capacity 为 8，哈希函数 计算哈希值：HashI = key % capacity

数据存储如下：

显然，这个哈希表并没有把所有位置都填满，数据分布无序且分散

因此，哈希表 又称为 散列表

2、哈希函数

元素对应的存储位置（哈希值）需要通过 哈希函数 进行计算，哈希函数 并非固定不变，可以根据需求自行设计

2.1、哈希函数的设计原则

在进行 映射 时，要尽量确保 唯一性，尽量让每一个元素都有自己的 映射 位置，这样在查找时，才能快速定位 元素

哈希函数 的设计原则如下：

1. 哈希函数的定义域必须包括需要存储的全部键值，且如果哈希表允许有 m 个地址，其值域为 [0, m-1]
2. 哈希函数计算出来的哈希值能均匀分布在整个哈希表中
3. 哈希函数应该尽可能简单、实用

哈希函数 的设计没必要动用太多数学高阶知识，要确保 实用性

2.2、常见的哈希函数

哈希函数 的发展已经有很多年历史了，在前辈的实践之下，留下了这些常见的 哈希函数

1、直接定址法（常用）

函数原型：HashI = A * key + B

• 优点：简单、均匀
• 缺点：需要提前知道键值的分布情况
• 适用场景：范围比较集中，每个数据分配一个唯一位置

2、除留余数法（常用）

假设 哈希表 的大小为 m

函数原型：HashI = key % p (p < m)

• 优点：简单易用，性能均衡
• 缺点：容易出现哈希冲突，需要借助特定方法解决
• 适用场景：范围不集中，分布分散的数据

3、平方取中法（了解）

函数原型：HashI = mid(key * key)

• 适用场景：不知道键值的分布，而位数又不是很大的情况

假设键值为 1234，对其进行平方后得到 1522756，取其中间的三位数 227 作为 哈希值

4、折叠法（了解）

折叠法是将键值从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按 哈希表 表长，取后几位作为散列地址

• 适用场景：事先不需要知道键值的分布，且键值位数比较多

假设键值为 85673113，分为三部分 856、731、13，求和：1600，根据表长（假设为 100），哈希值 就是 600

5、随机数法（了解）

选择一个随机函数，取键值的随机函数值为它的 哈希值

函数原型：HashI = rand(key)
其中 rand 为随机数函数

• 适用场景：键值长度不等时

哈希函数 还有很多很多种，最终目的都是为了计算出重复度低的 哈希值

最常用的是 直接定址法 和 除留余数法

3、哈希冲突

哈希冲突（哈希碰撞） 是面试中的常客，可以通过一个 哈希冲突 间接引出 哈希 中的其他知识点

3.1、冲突的原因

哈希值 是 键值 通过 哈希函数 计算得出的 位置标识符，难以避免重复问题

比如在上面的 哈希表 中，存入元素 20，哈希值 HashI = 20 % 8 = 4，此时 4 位置中并没有元素，可以直接存入

但是如果继续插入元素 36，哈希值 HashI = 36 % 8 = 4，此时 4 位置处已经有元素了，无法继续存入，此时就发生了 哈希冲突

不同的 哈希函数 引发 哈希冲突 的概率不同，但最终都会面临 哈希冲突 这个问题，因此需要解决一些方法，解决哈希冲突

3.2、解决方法

主要的解决方法有两种：闭散列 与 开散列

闭散列（开放定址法）

规定：当哈希表中存储的数据量 与 哈希表的容量 比值（负载因子）过大时，扩大哈希表的容量，并重新进行映射

因为有 负载因子 的存在，所以 哈希表是一定有剩余空间的

当发生 哈希冲突 时，从冲突位置向后探测，直到找到可用位置

像这种线性探测（暴力探测）可以解决 哈希冲突 问题，但会带来新的问题：踩踏

踩踏：元素的存储位置被别人占用了，于是也只能被迫线性探测，引发连锁反应，插入、查找都会越来越慢

哈希冲突 越多，效率 越低

优化方案：二次探测，每次向后探测 i ^ 2 步，尽量减少踩踏

尽管如此，闭散列 的实际效果 不尽人意，因为其本质上就是一个 零和游戏，实际中还是 开散列 用的更多一些

开散列（链地址法、开链法、哈希桶）

所谓 开散列 就在原 存储位置 处带上一个 单链表，如果发生 哈希冲突，就将 冲突的值依次挂载即可

因此也叫做 链地址法、开链法、哈希桶

开散列 中不需要 负载因子，如果每个位置都被存满了，直接扩容就好了，当然扩容后也需要重新建立映射关系

开散列 中进行查找时，需要先根据 哈希值 找到对应位置，并在 单链表 中进行遍历

一般情况下，单链表的长度不会太长的，因为扩容后，整体长度会降低

如果 单链表 真的过长了（几十个节点），我们还可以将其转为 红黑树，此时效率依旧非常高

图片出自：2021dragon

值得一提的是 哈希表（开散列法）最快时间复杂度为 O(N)，平均是 O(1)

哈希表（开散列法） 和 快排 一样很特殊，时间复杂度不看最坏的，看 平均时间复杂度，因为 最快的情况几乎不可能出现

以上就是解决 哈希冲突 的两种方法，后面在模拟实现 哈希表 时会详细讲解

4、unordered_set / unordered_map

哈希表 最xx的地方在于 查找速度非常快

快过红黑树！

因此在 C++11 标准中，利用 哈希表 作为底层结构，重写了 set / map，就是 unordered_set / unordered_map

图片出自：C++新特性之三：标准库中的新增容器

4.1、使用

哈希表 版的 unordered_set / unordered_map 与 红黑树 版的 set / map 在功能上 没有差别

可以直接无缝衔接

关于 set 和 map 的使用 详见：C++【set 和 map 学习及使用】

unordered_set 的使用

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

int main()
{
	vector<int> arr = { 7,3,6,9,3,1,6,2 };
	unordered_set<int> s1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	unordered_set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//判空、求大小
	cout << "===================" << endl;
	cout << "empty(): " << s1.empty() << endl;
	cout << "size(): " << s1.size() << endl;
	cout << "max_size(): " << s1.max_size() << endl;

	//插入元素
	cout << "===================" << endl;
	cout << "insert(5): ";
	s1.insert(5);
	for (auto e : s1) cout << e << " ";
	cout << endl;

	//删除元素
	cout << "===================" << endl;
	cout << "erase(6): ";
	s1.erase(6);
	for (auto e : s1) cout << e << " ";
	cout << endl;

	//交换、查找、清理
	cout << "===================" << endl;
	unordered_set<int> s2(arr.begin() + 5, arr.end());
	s1.swap(s2);
	cout << "s1: ";
	for (auto e : s1) cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (auto e : s2) cout << e << " ";
	cout << endl;

	cout << "s1.find(9): ";
	cout << (s1.find(9) != s1.end()) << endl;

	cout << "s2.clear(): " << endl;
	s2.clear();

	cout << "s1: ";
	for (auto e : s1) cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (auto e : s2) cout << e << " ";
	cout << endl;

	return 0;
}

unordered_map 的使用

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

int main()
{
	vector<pair<string, int>> arr{ make_pair("z", 122), make_pair("a", 97),  make_pair("K", 75), make_pair("h", 104), make_pair("B", 66) };

	unordered_map<string, int> m1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	unordered_map<string, int>::iterator it = m1.begin();
	while (it != m1.end())
	{
		cout << "<" << it->first << ":" << it->second << "> ";
		++it;
	}
	cout << endl;

	//判空、求大小、解引用
	cout << "===================" << endl;
	cout << "empty(): " << m1.empty() << endl;
	cout << "size(): " << m1.size() << endl;
	cout << "max_size(): " << m1.max_size() << endl;
	cout << "m1[""a""]: " << m1["a"] << endl;

	//插入元素
	cout << "===================" << endl;
	cout << "insert(""a"", 5): ";
	m1.insert(make_pair("a", 5));
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//删除元素
	cout << "===================" << endl;
	cout << "erase(""a""): ";
	m1.erase("a");
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//交换、查找、清理
	cout << "===================" << endl;
	unordered_map<string, int> m2(arr.begin() + 2, arr.end());
	m1.swap(m2);
	cout << "m1.swap(m2)" << endl;
	cout << "m1: ";
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m2: ";
	for (auto e : m2) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m1.find(""B""): ";
	cout << (m1.find("B") != m1.end()) << endl;

	cout << "m2.clear()" << endl;
	m2.clear();

	cout << "m1: ";
	for (auto e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m2: " << endl;
	for (auto e : m2) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	return 0;
}

照搬 set / map 使用的代码，可以无缝衔接，所以说正常使用就好了，无非就是名字长一些

C++ 为了确保向前兼容性，无法修改原来的名字，因此只能加上 unordered 以示区分
相比之下，Java 中两个不同版本的 set / map 就非常容易区分

• 红黑树版：TreeSet / TreeMap
• 哈希表版：HashSet / HashMap

注意： unordered_set / unordered_map 默认不允许出现键值冗余，如果相要存储重复的数据，可以使用 unordered_multiset / unordered_multimap

4.2、与 set/map 的区别

哈希表 版 与 红黑树 版的主要区别有两个

• 迭代器：哈希表版 是单向迭代器，红黑树版 是双向迭代器
• 遍历结果：哈希表版 无序，红黑树 有序

因为 unordered_set 是 单向迭代器，自然无法适配 反向迭代器

两种不同底层数据结构的遍历结果：

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>

using namespace std;

int main()
{
	vector<int> v = { 2,3,45,2,345,231,21,543,121,34 };
	set<int> TreeSet(v.begin(), v.end());
	unordered_set<int> HashSet(v.begin(), v.end());

	cout << "TreeSet: ";
	for (auto e : TreeSet)
		cout << e << " ";
	cout << endl << endl;

	cout << "HashSet: ";
	for (auto e : HashSet)
		cout << e << " ";
	cout << endl;
	return 0;
}

显然，哈希表 实现的 unordered_set / unordered_map 遍历结果为 无序

哈希表 究竟比 红黑树 强多少？

4.3、性能对比

下面是性能测试代码，包含 大量重复、部分重复、完全有序 三组测试用例，分别从 插入、查找、删除 三个维度进行对比

注：测试性能用的是 Release 版，这里的基础数据量为 100 w

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>

using namespace std;

int main()
{
	const size_t N = 1000000;

	unordered_set<int> us;
	set<int> s;

	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand());	//大量重复
		//v.push_back(rand()+i);	//部分重复
		//v.push_back(i);	//完全有序
	}

	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;

	size_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;


	size_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << endl;

	size_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	size_t end4 = clock();
	cout << "unordered_set find:" << end4 - begin4 << endl << endl;

	cout << s.size() << endl;
	cout << us.size() << endl << endl;;

	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;

	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
	
	return 0;
}

插入大量重复数据

插入数据 大量重复 —- 结果：

• 插入：哈希 比 红黑 快 88%
• 查找：哈希 比 红黑 快 100%
• 删除：哈希 比 红黑 快 37%

插入部分重复数据

插入数据 部分重复 —- 结果：

• 插入：哈希 与 红黑 差不多
• 查找：哈希 比 红黑 快 100%
• 删除：哈希 比 红黑 快 41%

插入大量重复数据

插入数据 完全有序 —- 结果：

• 插入：哈希 比 红黑 慢 52%
• 查找：哈希 比 红黑 快 100%
• 删除：哈希 比 红黑 慢 58%

总的来说，在数据 随机 的情况下，哈希各方面都比红黑强，在数据 有序 的情况下，红黑更胜一筹

单就 查找 这一个方面来说：哈希 一骑绝尘，远远的将红黑甩在了身后

🌆总结

以上就是本次关于 C++【初识哈希】的全部内容了，在本文中，我们主要学习了哈希的相关知识，包括哈希思想、哈希函数、哈希冲突及其解决方法，最后还学习了 C++11 中基于哈希表的新容器，见识了哈希表查找的快，不是一般的快。在下一篇文章中，我们将会对哈希表进行模拟实现，同时也会用一张哈希表同时封装实现 unordered_set 和 unordered_map

相关文章推荐

C++ 进阶知识

C++【一棵红黑树封装 set 和 map】

C++【红黑树】

C++【AVL树】

C++【set 和 map 学习及使用】

C++【二叉搜索树】

C++【多态】

C++【继承】

STL 之 泛型思想

C++【模板进阶】

C++【模板初阶】