【C++】哈希表基础：开放定址法 & 什么是哈希冲突？

摘要

哈希通过哈希函数建立关键字与存储位置的映射以实现快速查找，包含标准库实现与直接定址法等形式，且使用哈希函数时会出现哈希冲突。

一、哈希（Hash）概念

哈希（hash）又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进行快速查找。

1. 哈希的核心思想

哈希技术的核心在于通过哈希函数建立Key到存储位置的直接映射，使得在理想情况下能够实现O(1)时间复杂度的查找操作。

2. 标准库中的哈希实现

在实际编程中，我们常用的unordered_map和unordered_set就是基于哈希表实现的：

• unordered_map：基于哈希表的键值对容器
• unordered_set：基于哈希表的集合容器

与之对应的有序版本是：

• map - 基于红黑树（有序）
• set - 基于红黑树（有序）

二、哈希的特殊实现

1. 直接定址法

1. 当关键字的范围比较集中时，直接定址法就是非常简单高效的方法。比如一组关键字都在[0,99]之间，那么我们开一个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母，那么我们开一个26个数的数组，每个关键字ascii码 - ‘a’ ascii码就是存储位置的下标。
2. 也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分已经用过了，其次在string章节的下面OJ也用过了。
3. 直接定址法的优势在于它的极致简单和高效。由于不需要复杂的哈希函数计算，也没有哈希冲突的问题，它的时间复杂度是严格的O(1)。在关键字分布紧凑且连续的理想情况下，这是最优的解决方案。

外面通过这段找字符串中第一个唯一字符的算法题辅助理解

class Solution {
public:
	int firstUniqChar(string s) 
	{
		// 每个字⺟的ascii码-'a'的ascii码作为下标映射到hash数组，数组中存储出现的次数
		int hash[26] = {0};
		// 统计次数
		for(auto ch : s)
		{
			hash[ch-'a']++;
		} 
		for(size_t i = 0; i < s.size(); ++i)
		{
			if(hash[s[i]-'a'] == 1)
			return i;
		}
		return -1;
	}
};

但是直接定址法也有明显的局限性。当关键字分布稀疏时，会造成大量的空间浪费。比如关键字可能取值为[1, 1000000]但实际只有100个元素，如果开100万个位置的数组就会极其浪费空间。此外，直接定址法要求关键字必须是整数或者能容易地转换为整数索引。

三、哈希冲突

因为直接定址法的局限性我们引入了哈希函数（核心思想：使用一个函数 H(key)，将大范围的关键字映射到一个固定的小范围[0, M-1] 内。）。

然而，引入哈希函数带来了一个新的、无法避免的问题——哈希冲突（哈希碰撞）。

• 让我们用最常见的哈希函数来解释哈希冲突
• 除留余数法:hashi = key % size，其中hashi计算的结果为哈希地址，即元素使用关键码计算出在表中对应的存储位置

在这里插入图片描述

当两个不同的关键字 key1 和 key2，经过哈希函数计算后，得到了相同的地址，即 H(key1) = H(key2)，就发生了冲突。

对于如何解决哈希冲突，请看下一章！

总结

哈希是高效的数据组织方式，虽有不同实现形式但各有适用场景，哈希冲突是其使用哈希函数映射时的必然问题。