C++数据结构：哈希 -- unordered系列容器、哈希表的结构以及如何通过闭散列的方法解决哈希冲突_二次探测法解决冲突

目录

一. unordered系列关联式容器

1.1 unrodered_map和unordered_set 综述

1.2 常见的接口函数（以unordered_map为例）

1.3 unordered系列与map和set的效率对比

二. 哈希表的底层结构

2.1 什么是哈希

2.2 哈希函数

2.3 哈希冲突

三. 通过闭散列的方法解决哈希冲突问题

3.1 线性探测法

3.2 二次探测法

四. 线性探测法和二次探测法的实现

4.1 哈希表存储的数据类型

4.2 哈希表的扩容 

4.3 插入数据操作insert

4.4 数据查找操作find

4.5 数据删除操作erase

附录：线性探测法和二次探测法模拟实现哈希表完整版代码

---

一. unordered系列关联式容器

1.1 unrodered_map和unordered_set 综述

在C++98中，STL库提供了map和set两种容器，它们的底层都是通过红黑树来实现的，可以实现时间复杂度为O(log N)的查找。如果数据量N过多，就会造成红黑树的层数很大，查找效率依旧不会理想。因此，在C++11中，标准STL库又引入了unordered_map和unordered_set这两个容器。map和set与unordered系列容器的区别是：

• map和set是有序的，unordered系列容器是无序的。
• map和set的迭代器支持双向迭代，unordered系列容器仅支持单向迭代。
• 在增删查改方面。unordered系列容器的效率高于map和set。

unordered系列容器的底层是通过哈希表来实现的。

stl库中对unordered_map和unordered_set类模板的声明见图1.1，这里尤其要注意Hash类，这是个仿函数，可以由用户自主实现。默认情况下，该仿函数仅仅是将输入的参数转换为size_t类型返回，但是对于string类等特殊数据作为Key时，则需要一些算法将这些特殊类型转换为size_t，这是仿函数Hash所实现的。

1.2 常见的接口函数（以unordered_map为例）

unordered_map和unordered_set接口函数的使用于map和set基本一致。

• 构造相关函数

• 容量相关函数

• 迭代器相关函数

• 元素访问函数

• 修改相关函数

注意：通过迭代器位置和迭代器区间删除数据的erase函数返回被删除的最后一个数据后面那个位置处的迭代器，指定Key值删除数据的erase函数返回删除数据的个数。

1.3 unordered系列与map和set的效率对比

运行代码1.1的测试程序，依次向map和unordered_map中插入200000个数据，比较两者的插入、查找、删除数据的效率，从图1.2的运行结果可以看出，unordered_map的增删查效率要高于map。因此，虽然unordered系列容器相比于map和set既不有序、也不支持双向迭代，但依旧有其优势：unordered系列容器的增删查效率高。

代码1.1：（unordered_map与map的效率对比）

#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
 
using namespace std;
 
void TestHash()
{
	srand((unsigned int)time(NULL));
	std::unordered_map<int, int> hashMap;
	std::map<int, int> mp;
 
	size_t N = 200000;
	std::vector<int> v;
	for (size_t i = 0; i < N; ++i)
	{
		int x = rand() + i;
		v.push_back(x);
	}
 
	size_t sz = v.size();
 
	//map插入数据时间
	size_t begin1 = clock();
	for (auto& e : v)
	{
		mp.insert(std::make_pair(e, e));
	}
	size_t end1 = clock();
 
	//unordered_map插入数据时间
	size_t begin2 = clock();
	for (auto& e : v)
	{
		hashMap.insert(std::make_pair(e, e));
	}
	size_t end2 = clock();
 
	std::cout << "map insert: " << end1 - begin1 << std::endl;
	std::cout << "unordered_map insert: " << end2 - begin2 << std::endl;
 
	//map查找数据时间
	size_t begin3 = clock();
	for (auto& e : v)
	{
		mp.find(2);
	}
	size_t end3 = clock();
 
	//unordered_map查找数据时间
	size_t begin4 = clock();
	for (auto& e : v)
	{
		hashMap.find(e);
	}
	size_t end4 = clock();
 
	std::cout << "map find: " << end3 - begin3 << std::endl;
	std::cout << "unordered_map find: " << end4 - begin4 << std::endl;
 
	//map删除数据时间
	size_t begin5 = clock();
	for (auto& e : v)
	{
		mp.erase(e);
	}
	size_t end5 = clock();
 
	//unordered_map删除数据时间
	size_t begin6 = clock();
	for (auto& e : v)
	{
		hashMap.erase(e);
	}
	size_t end6 = clock();
 
	std::cout << "map erase: " << end5 - begin5 << std::endl;
	std::cout << "unordered_map erase: " << end6 - begin6 << std::endl;
}
 
int main()
{
	TestHash();
	return 0;
}

二. 哈希表的底层结构

2.1 什么是哈希

对于理想的查找，我们希望拿到给定的Key之后，只要一次查找就可以找到与Key配对的Value值，或者说是以O(1)的时间复杂度查找。

如果我们可以将Key值与存储位置建立一定的映射关系，那么就可以在拿到Key值的同时就通过相应的规则在与之映射的位置存储pair<Key, Value>，这样就可以实现时间复杂度为O(1)的插入和查找。这就是哈希表结构，Key与存储位置之间的换算公式，称为哈希函数。

在我之前的博客[数据结构基础]排序算法第四弹 -- 归并排序和计数排序_【Shine】光芒的博客-CSDN博客中所讲到的计数排序，就是用哈希表数据结构实现的。

2.2 哈希函数

哈希函数，就是关键码Key与存储位置的映射函数，常用的哈希函数实现方法有两种：

1. 直接定值法 -- Hash(key) = A*Key + B
2. 除留余数法 -- Hash(key) = key % p

直接定值法

直接定值法通过简单地线性映射，获得Key对应的存储位置。

• 优点：映射关系简单，分布均匀。
• 缺点：需要实现知道关键字的分布情况，适用于范围较小且较为连续的数据。

如图2.1所示的映射，以及计数排序，都是使用直接定值法。

除留余数法

设哈希散列中运行存储数据的地址数为m，取不大于m的数据p作为被除数，按照哈希函数：Hash(Key) = Key % p，来获取与关键码Key匹配的存储地址。

2.3 哈希冲突

哈希冲突，就是两个不同的Key值，经过一定的哈希函数转换过后，其计算所得的存储位置相同，除留余数法，就很容易造成哈希冲突，如：

• 当p=10的情况下，使用Hash(key) = Key%p 作为哈希函数，向哈希散列中插入数据。当Key=1和Key=11是会有哈希冲突的问题，因为 1%10 = 11%10 = 1。

解决哈希冲突有两大类方法：

1. 闭散列 -- 开放定值法（线性探测、二次探测）
2. 开散列 -- 哈希桶

三. 通过闭散列的方法解决哈希冲突问题

3.1 线性探测法

线性探测，就是在直接通过哈希函数计算获得映射位置后，如果发生冲突，就在这个位置的前后，通过++/--操作，找到没有被占用的位置。但是，新找到的位置有可能会与之后插入的元素产生哈希冲突。

3.2 二次探测法

二次探测，并不是指探测两次，而是2的平方。如果某个Key对于的Hash位置pos发生冲突，那么先去的位置查找看是否冲突，如果还是冲突就去的位置处查找，然后就是，依次类推，直到找到不冲突的位置。

四. 线性探测法和二次探测法的实现

这里对insert插入键值对、find查找key以及erase删除数据进行实现

4.1 哈希表存储的数据类型

在哈希表的每个位置，要存储一键值对，来记录关键字Key和用于配对的Value。同时，还应定义状态枚举类型常量State，用于记录每个位置是存在数据EXIST、还没有数据EMPTY还是之前有数据但是被删除了DELETE。

代码4.1：（hashDate -- 哈希表数据类型的定义）

enum State
{
	EMPTY,
	EXIST,
	DELETE
};
 
template<class K, class V>
struct hashDate
{
	std::pair<K, V> _kv;
	State _state = EMPTY;
};

4.2 哈希表的扩容 

如果哈希表没有剩余空间后再进行扩容，则容易产生大量的哈希冲突，造成查找效率的下降。因此，引入散列表载荷因子a，当a大于一定值时，就进行扩容。

a是表示哈希散列表装满程度的因子，定义为：

• a = 装入表中的元素个数 / 表的长度（可容纳元素个数）

a越大，散列表中数据越满，越容易产生哈希冲突，一般而言，一般设置扩容时a的值为0.7~0.8，当大于这个临界值时，将会扩容。

为了保证散列表中capacity()内每个位置都可以使用下标[]进行访问，以插入数据，应当使用resize进行而不是reserve扩容，resize扩容可以给新增的空间赋初值，将新增的空间的_state设为EMPTY，表明其没有被占用。

哈希表扩容不能仅仅是增容，由于映射关系发生改变，还应当改变表中数据的存放位置。扩容一般只发生在插入操作insert时，直接创建临时哈希散列复用插入操作，要比编码计算映射位置方便。

4.3 插入数据操作insert

哈希散列插入数据流程：

1. 查找原来哈希表中是否存在要插入的数据，如果存在，不再插入，函数终止执行。
2. 判断是否需要扩容，需要就执行扩容操作。
3. 根据哈希函数计算插入数据所应存放的位置，并通过线性探测或二次探测的方法，解决哈希冲突的问题。（由于哈希表始终不满，一定能找到不发生哈希冲突的位置）
4. 在最终找到的不发生哈希冲突的位置处插入数据。

代码4.2：（哈希表数据插入insert函数）

	bool insert(const std::pair<K, V>& date)
	{
		//key已经存在，不进行插入操作
		if (find(date.first))
		{
			return false;
		}
 
		//检查扩容
		if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
		{
			//如果哈希表中没有存储数据（容量为0），或者插入新数据后存储的数据多于哈希表的容量的70%，就进行扩容
			//这里的哈希表容量是_table.size()而不是_table.capacity()，因为下标大于等于_table.size()是无法进行随机访问
			size_t newCapacity = _size == 0 ? 10 : 2 * _table.size();
			//_table.resize(newCapacity);
 
			//扩容之后每个Key对应的哈希映射的位置发生改变
			//这里创建一个新的临时Hash表，将原来哈希表中的有效数据依次插入到临时的哈希表中
			//然后使用swap函数，交换原本的哈希表和新的哈希表
			HashTable tmpHash;
			tmpHash._table.resize(newCapacity);
 
			for (size_t i = 0; i < _table.size(); ++i)
			{
				if (_table[i]._state == EXIST)
				{
					tmpHash.insert(_table[i]._kv);
				}
			}
 
			_table.swap(tmpHash._table);
		}
 
		//插入数据
		//1.线性探测解决哈希冲突问题
		Hash hash;    //创建Hash类对象，用于调用将Key转换为size_t类型的仿函数
		size_t mapPos = hash(date.first) % _table.size();   //通过哈希函数获取映射位置
		size_t start = mapPos;
 
		while (_table[mapPos]._state == EXIST)
		{
			//发生了哈希冲突，通过线性探测来解决哈希冲突问题
			//线性探测：在冲突位置附近寻找没有被占用的位置
			++mapPos;
			mapPos %= _table.size();
		}
 
		2.二次探测解决哈希冲突问题
		//Hash hash;
		//size_t i = 0;
		//size_t start = hash(date.first) % _table.size();
		//size_t mapPos = start + i;
 
		//while (_table[mapPos]._state == EXIST)
		//{
		//	++i;
		//	mapPos = (start + i * i) % _table.size();
		//}
 
		_table[mapPos]._kv = date;
		_table[mapPos]._state = EXIST;
		++_size;
 
		return true;
	}

4.4 数据查找操作find

通过哈希函数，找到Key对应的理论存储位置，如果发生冲突就按照线性探测或二次探测的规律到理论位置的周围去查找，直到找到Key值或者发现EMPTY。

发现EMPTY表明哈希散列中没有Key，返回nullptr。

代码4.3：（查找函数Find）

	//Key查找函数
	hashDate<K, V>* find(const K& key)
	{
		if (_size == 0)
		{
			return nullptr;
		}
 
		Hash hash;
		size_t mapPos = hash(key) % _table.size();   //哈希映射位置
		size_t start = mapPos;
 
		//处理哈希冲突问题
		while (_table[mapPos]._state != EMPTY)
		{
			if (_table[mapPos]._state != DELETE && _table[mapPos]._kv.first == key)
			{
				return &_table[mapPos];
			}
 
			++mapPos;
			mapPos %= _table.size();
 
			//如果所有位置都遍历一遍（全为DELETE），那么break掉while循环
			//此时哈希表为空，所有位置的数据都被删除，不进行break处理会死循环
			if (mapPos == start)
			{
				break;
			}
		}
 
		return nullptr;
	}

4.5 数据删除操作erase

通过Find找到Key的位置，如果Key存在于哈希表中，将那个位置的_state改为DELETE即可。

代码4.4：（哈希表数据删除erase函数）

	bool erase(const K& key)
	{
		hashDate<K, V>* pos = find(key);
		if (pos)
		{
			//找到要删除数据的位置，直接将状态置为DELETE即可
			pos->_state = DELETE;
			return true;
		}
		else
		{
			//要删除的key不存在，直接返回，不进行任何操作
			return false;
		}
	}

附录：线性探测法和二次探测法模拟实现哈希表完整版代码

#include<iostream>
#include<vector>
 
enum State
{
	EMPTY,
	EXIST,
	DELETE
};
 
template<class K, class V>
struct hashDate
{
	std::pair<K, V> _kv;
	State _state = EMPTY;
};
 
//用于获取哈希表键值Key的仿函数
//Key用于与存储位置建立映射关系
template<class K>
struct HashKey
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
 
template<class K, class V, class Hash = HashKey<K>>
class HashTable
{
public:
	//数据插入函数
	bool insert(const std::pair<K, V>& date)
	{
		//key已经存在，不进行插入操作
		if (find(date.first))
		{
			return false;
		}
 
		//检查扩容
		if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
		{
			//如果哈希表中没有存储数据（容量为0），或者插入新数据后存储的数据多于哈希表的容量的70%，就进行扩容
			//这里的哈希表容量是_table.size()而不是_table.capacity()，因为下标大于等于_table.size()是无法进行随机访问
			size_t newCapacity = _size == 0 ? 10 : 2 * _table.size();
			//_table.resize(newCapacity);
 
			//扩容之后每个Key对应的哈希映射的位置发生改变
			//这里创建一个新的临时Hash表，将原来哈希表中的有效数据依次插入到临时的哈希表中
			//然后使用swap函数，交换原本的哈希表和新的哈希表
			HashTable tmpHash;
			tmpHash._table.resize(newCapacity);
 
			for (size_t i = 0; i < _table.size(); ++i)
			{
				if (_table[i]._state == EXIST)
				{
					tmpHash.insert(_table[i]._kv);
				}
			}
 
			_table.swap(tmpHash._table);
		}
 
		//插入数据
		//1.线性探测解决哈希冲突问题
		Hash hash;    //创建Hash类对象，用于调用将Key转换为size_t类型的仿函数
		size_t mapPos = hash(date.first) % _table.size();   //通过哈希函数获取映射位置
		size_t start = mapPos;
 
		while (_table[mapPos]._state == EXIST)
		{
			//发生了哈希冲突，通过线性探测来解决哈希冲突问题
			//线性探测：在冲突位置附近寻找没有被占用的位置
			++mapPos;
			mapPos %= _table.size();
		}
 
		2.二次探测解决哈希冲突问题
		//Hash hash;
		//size_t i = 0;
		//size_t start = hash(date.first) % _table.size();
		//size_t mapPos = start + i;
 
		//while (_table[mapPos]._state == EXIST)
		//{
		//	++i;
		//	mapPos = (start + i * i) % _table.size();
		//}
 
		_table[mapPos]._kv = date;
		_table[mapPos]._state = EXIST;
		++_size;
 
		return true;
	}
 
	//Key查找函数
	hashDate<K, V>* find(const K& key)
	{
		if (_size == 0)
		{
			return nullptr;
		}
 
		Hash hash;
		size_t mapPos = hash(key) % _table.size();   //哈希映射位置
		size_t start = mapPos;
 
		//处理哈希冲突问题
		while (_table[mapPos]._state != EMPTY)
		{
			if (_table[mapPos]._state != DELETE && _table[mapPos]._kv.first == key)
			{
				return &_table[mapPos];
			}
 
			++mapPos;
			mapPos %= _table.size();
 
			//如果所有位置都遍历一遍（全为DELETE），那么break掉while循环
			//此时哈希表为空，所有位置的数据都被删除，不进行break处理会死循环
			if (mapPos == start)
			{
				break;
			}
		}
 
		return nullptr;
	}
 
	//数据删除函数
	bool erase(const K& key)
	{
		hashDate<K, V>* pos = find(key);
		if (pos)
		{
			//找到要删除数据的位置，直接将状态置为DELETE即可
			pos->_state = DELETE;
			return true;
		}
		else
		{
			//要删除的key不存在，直接返回，不进行任何操作
			return false;
		}
	}
 
	//哈希表打印函数
	void Print()
	{
		for (size_t i = 0; i < _table.size(); ++i)
		{
			if (_table[i]._state == EXIST)
			{
				printf("[%d,%d] ", i, _table[i]._kv.first);
			}
			else
			{
				printf("[%d,*] ", i);
			}
		}
		std::cout << std::endl;
	}
 
private:
	std::vector<hashDate<K, V>> _table;   //哈希表容器
	size_t _size = 0;   //哈希表目前所含的数据量
};