前言

一、unordered系列关联式容器

在C98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。**最好的查询是，进行很少的比较次数就能够将元素找到，因此在C11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。**本博客中只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multiset可查看文档介绍。

二、unordered_map

1.unordered_map的文档介绍

unordered_map文档介绍

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的
   value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键
   和映射值的类型可能不同。
3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。

2unordered_map的接口介绍

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1。

三、unordered_set

unordered_set文档介绍

四、底层结构

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

1.哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( )，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

2.哈希冲突

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题。

**对于两个数据元素的关键字 和 (i != j)，有 != ，但有：Hash( ) == Hash( )，**即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？

3.哈希函数

1. <直接定制法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A/*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况 面试题：字符串中第一个只出现一次字符
2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法–(了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
4. 折叠法–(了解)
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5. 随机数法–(了解)
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。
6. 数学分析法–(了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

4.哈希冲突的解决之闭散列-线性探测和二次探测

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

1. 线性探测
   比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
   线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入

• 通过哈希函数获取待插入元素在哈希表中的位置
• 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

线性探测优点：实现非常简单，线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： = ( + )% m,或者： = ( - )% m。其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

5.哈希冲突的解决之开散列

#pragma once

#include <iostream>
using namespace std;

#include <vector>
#include "Common.h"

// 哈希桶：数组+链表(无头单链表)

template<class T>
struct HashBucketNode
{
	HashBucketNode<T>* next;
	T data;

	HashBucketNode(const T& x = T())
		: next(nullptr)
		, data(x)
	{}
};

// T 如果是整形家族
template<class T>
class T2IntDef
{
public:
	const T& operator()(const T& data)
	{
		return data;
	}
};

class Str2Int
{
public:
	size_t operator()(const string& s)
	{
		const char* str = s.c_str();
		unsigned int seed = 131; // 31 131 1313 13131 131313
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}
		return (hash & 0x7FFFFFFF);
	}
};

// 假设：当前实现的哈希表中元素唯一
// T：哈希表中存储的元素的类型
// T2Int: 将T转换为整形的结果

template<class T, class T2Int = T2IntDef<T>>
class HashBucket
{
	typedef HashBucketNode<T> Node;
public:
	HashBucket(size_t capacity = 53)
		: table(GetNextPrime(capacity))    // n个值为data的构造方法在构造哈希桶
		, size(0)
	{}

	~HashBucket()
	{
		Destroy();
	}

	/* 虽然从代码层面来看，Insert当中存在一个循环，即：遍历链表，检测data是否存在---->表面上Insert的时间复杂度O(N) 但是实际认为Insert的时间复杂度仍旧为O(1)---->因为：在哈希桶中，每个桶对应的链表当中的节点的格式都不是非常多 */
	bool Insert(const T& data)
	{
		// 0. 检测是否需要扩容
		CheckCapacity();

		// 1. 通过哈希函数计算元素所在桶号
		size_t bucketNo = HashFunc(data);

		// 2. 检测元素是否存在
		Node* cur = table[bucketNo];
		while (cur)
		{
			if (data == cur->data)
				return false;

			cur = cur->next;
		}

		// 3. 插入元素
		cur = new Node(data);
		cur->next = table[bucketNo];
		table[bucketNo] = cur;
		++size;
		return true;
	}

	bool Erase(const T& data)
	{
		// 1. 先通过哈希函数计算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 找元素在bucketNo桶中是否处在，存在则删除
		// 核心操作--->删除链表当中只为data的节点
		// 该节点可能是链表中的第一个节点
		// 该节点可能是链表中的非第一个节点

		Node* cur = table[bucketNo];
		Node* prev = nullptr;   // 标记cur的前一个节点
		while (cur)
		{
			if (data == cur->data)
			{
				// 删除cur节点
				// 删除的节点如果是第一个节点
				if (nullptr == prev)
					table[bucketNo] = cur->next;
				else
					prev->next = cur->next;

				delete cur;
				--size;
				return true;
			}
			else
			{
				// 当前节点不是要找的data，则两个指针同时往后移动
				prev = cur;
				cur = cur->next;
			}
		}

		// 哈希桶中不存在值为data的元素，无法删除即删除失败
		return false;
	}

	Node* Find(const T& data)
	{
		// 1. 先通过哈希函数计算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 在检测该元素是否存在对应的链表中
		Node* cur = table[bucketNo];
		while (cur)
		{
			if (data == cur->data)
				return cur;

			cur = cur->next;
		}

		return nullptr;
	}

	size_t Size()const
	{
		return size;
	}

	bool Empty()const
	{
		return 0 == size;
	}

	/
	// 为了方便对哈希桶的理解，实现打印哈希桶的方法
	void Print()
	{
		for (size_t i = 0; i < table.capacity(); ++i)
		{
			Node* cur = table[i];

			cout << "table[" << i << "]:";

			while (cur)
			{
				cout << cur->data << "--->";
				cur = cur->next;
			}

			cout << "NULL" << endl;
		}
		cout << "=========================================" << endl;
	}

	void Swap(HashBucket<T, T2Int>& ht)
	{
		table.swap(ht.table);
		std::swap(size, ht.size);
	}

private:
	// 哈希函数---除留余数法
	size_t HashFunc(const T& data)
	{
		T2Int t2Int;
		return t2Int(data) % table.capacity();
	}

	void Destroy()
	{
		// 循环去销毁：table中的每个链表
		for (size_t i = 0; i < table.capacity(); ++i)
		{
			Node* cur = table[i];

			// 采用：头删法删除链表中的每个节点
			while (cur)
			{
				table[i] = cur->next;
				delete cur;
				cur = table[i];
			}
		}

		size = 0;
	}

	void CheckCapacity()
	{
		if (size == table.capacity())
		{
			// 扩容---将表格放大----然后将桶中的元素往新桶中插入
			HashBucket<T, T2Int> newHT(GetNextPrime(table.capacity()));

			// 将就哈希桶中的节点拆下来，移动到新哈希桶中
			for (size_t i = 0; i < table.capacity(); ++i)
			{
				Node* cur = table[i];
				while (cur)
				{
					// 1. 将cur节点拆下来
					table[i] = cur->next;

					// 2. 将cur节点往newHT中插入
					// 找位置
					size_t bucketNo = newHT.HashFunc(cur->data);

					// 头插法
					cur->next = newHT.table[bucketNo];
					newHT.table[bucketNo] = cur;
					newHT.size++;

					cur = table[i];
				}
			}

			// 已经将旧哈希桶中的元素全部移动到新哈希桶当中了
			this->Swap(newHT);
		}
	}
private:
	// table当中将来存放所有的链表--->实际只需要存放链表首节点的地址
	std::vector<Node*> table;
	size_t size;   // 有效元素的个数
};

开散列与闭散列比较:
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

总结

以上就是今天要讲的内容，本文介绍了哈希冲突和哈希冲突的解决方法之开散列和闭散列，哈希很好的解决了查找效率问题，哈希提供了大量能使我们快速便捷地了解错误的发生，我们务必掌握。另外如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。