【数据结构】万字一文手把手解读哈希————（开/闭散列）解决哈希冲突完整详解（6）

前言
大家好吖，欢迎来到 YY 滴数据结构系列，热烈欢迎！本章主要内容面向接触过C++的老铁
主要内容含：

欢迎订阅 YY滴数据结构专栏！更多干货持续更新！以下是传送门！

一.哈希（散列）的基本概念
- 1.哈希（散列）的基本概念
- 2.哈希表的简单基本例子
二.哈希冲突(哈希碰撞)
三.哈希函数
- 1.哈希函数设计原则
- 2.常用的两种哈希函数
- - 【1】直接定址法–(常用)
  - 【2】除留余数法–(常用)
【※】哈希表中的荷载因子
四.解决哈希冲突法一：闭散列-“开放地址法”
- 1. 线性探测＆二次探测
- 2.闭散列哈希中的基本状态
- 3.闭散列哈希的基本结构
- 4.线性探测中处理”查找”
- 5.线性探测中处理”插入”
- - 【1】注意闭散列扩容问题
- 6.线性探测中处理”删除”
- 7. 闭散列适应多种类型转换————”仿函数”＆”类模板特化”&“仿函数在类模板中充当默认模板实参的应用”
- - 【1】仿函数
  - 【2】类模板特化
  - 【3】仿函数在类模板中充当默认实参的应用
- 8.闭散列哈希完整代码展示
- 9.闭散列缺点
五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”
- 1. 开散列概念
- 2.开散列哈希基本形式
- 3.开散列插入
- - 【1】哈希桶基本插入问题
  - 【2】注意闭散列扩容问题
  - 【3】注意闭散列扩容后的操作
  - 【4】闭散列完整插入操作
- 4. 开散列查找操作
- 5. 开散列哈希完整代码展示
六.哈希表的使用

一.哈希（散列）的基本概念

1.哈希（散列）的基本概念

理想的搜索方法：不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构， 通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系 ，那么在查找时通过该函数可以很快找到该元素

该方式即为 哈希(散列)方法 ，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

2.哈希表的简单基本例子

例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity;
capacity为存储元素底层空间总的大小

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

但是 当插入44时 ，就会出现问题： 不同值映射到相同位置 ，这就是第二部分要讲的” 哈希冲突问题 “

二.哈希冲突(哈希碰撞)

一句话理解哈希冲突: 不同值映射到相同位置

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

引起哈希冲突的一个原因可能是： 哈希函数设计不够合理 。这就是第二部分要讲的”哈希函数”

三.哈希函数

我们先要确定一点：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是 无法避免哈希冲突

1.哈希函数设计原则

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

2.常用的两种哈希函数

【1】直接定址法–(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

【2】除留余数法–(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数Hash(key) = key% p(p<=m), 将关键码转换成哈希地址

【※】哈希表中的荷载因子

四.解决哈希冲突法一：闭散列-“开放地址法”

一句话理解闭散列： 当前位置被占用了，按规则找到下一个位置（占用别人应该在的位置）

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

1. 线性探测＆二次探测

一句话理解 线性探测： 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止 ,示例如下所示：

线性探测缺点： 一旦发生 哈希冲突 ，所有的冲突连在一起，容易产生 数据“堆积”
即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低。如何缓解呢？
二次探测 是为了避免该问题而生；找下一个空位置的方法为： = ( + )% m, 或者： = ( – )% m。其中： i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。示例如下所示：

2.闭散列哈希中的基本状态

每一个元素格子可以分成三种状态：
EXIST（存在）
EMPTY（空）
DELETE（已被删除）

enum STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};

3.闭散列哈希的基本结构

    template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		STATE _state = EMPTY;
	};

   vector<HashData<K, V>> _table;
   size_t _n = 0; // 存储有效数据的个数————可用于识别荷载因子

4.线性探测中处理”查找”

代码如下所示：

HashData<const K, V>* Find(const K& key)
		{
			// 线性探测
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._state == EXIST
					&& _table[hashi]._kv.first == key)
				{
					return (HashData<const K, V>*) & _table[hashi];
				}

				++hashi;
				hashi %= _table.size();
			}

5.线性探测中处理”插入”

【1】注意闭散列扩容问题

插入过程基本程序设计思路：
当荷载因子达到某个临界值_n * 10 / _table.size() >= 7，进入扩容
扩容过程： 1.设置新表大小 2.创建新表 3.遍历旧表的数据插入到新表即可 4.交换新表旧表首元素地址
正常插入过程遵循线性探测：
1.通过哈希函数找到相应映射的下表（hashi）
2.但遇到当前hashi已经被占据时_table[hashi]._state == EXIST，
进行 二次探测 hashi %= _table.size();重新寻找新hashi
3.找到状态为EMPTY的hashi时，存入数据，调整状态
_table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n;

bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			// 扩容
			//if ((double)_n / (double)_table.size() >= 0.7)
			if (_n * 10 / _table.size() >= 7) //荷载因子
			{
				size_t newSize = _table.size() * 2;
				// 遍历旧表，重新映射到新表
				HashTable<K, V, HashFunc> newHT;
				newHT._table.resize(newSize);

				// 遍历旧表的数据插入到新表即可
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newHT.Insert(_table[i]._kv);
					}
				}

				_table.swap(newHT._table);
			}

			// 线性探测
			HashFunc hf;
			size_t hashi = hf(kv.first) % _table.size();
			while (_table[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _table.size();
			}

			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;

			return true;
		}

6.线性探测中处理”删除”

删除过程基本程序设计思路：
利用查找函数find接收返回值
将该hashi下表对应的状态设置成DELETE即可

// 按需编译
		bool Erase(const K& key)
		{
			HashData<const K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;

				return true;
			}

			return false;
		}

7. 闭散列适应多种类型转换————“仿函数”＆“类模板特化”&“仿函数在类模板中充当默认模板实参的应用”

【1】仿函数

一句话解释 仿函数 ：用一个类重载（），让其实现函数的功能

仿函数在类模板中的应用传送门：传送门

使用仿函数的基本操作：重载（）——operator()

template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

【2】类模板特化

使用仿函数的进阶操作：让闭散列适应多种类型转换
场景举例：正常情况下，我们输入int double，他都会通过仿函数重载的（）转换成对应的ASCLL码值，但是当传入的是字符串则会出现问题，因此我们需要把类模板 特化一下————struct DefaultHashFunc<string>
特化在类模板中的应用传送门：传送门

template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

【3】仿函数在类模板中充当默认实参的应用

仿函数在类模板中充当默认模板实参传送门：传送门

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	//调用时
	HashFunc hf;
	size_t hashi = hf(kv.first) % _table.size();
	...};

8.闭散列哈希完整代码展示

template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

namespace open_address
{
	enum STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		STATE _state = EMPTY;
	};

	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_table.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			// 扩容
			//if ((double)_n / (double)_table.size() >= 0.7)
			if (_n * 10 / _table.size() >= 7)
			{
				size_t newSize = _table.size() * 2;
				// 遍历旧表，重新映射到新表
				HashTable<K, V, HashFunc> newHT;
				newHT._table.resize(newSize);

				// 遍历旧表的数据插入到新表即可
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newHT.Insert(_table[i]._kv);
					}
				}

				_table.swap(newHT._table);
			}

			// 线性探测
			HashFunc hf;
			size_t hashi = hf(kv.first) % _table.size();
			while (_table[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _table.size();
			}

			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<const K, V>* Find(const K& key)
		{
			// 线性探测
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._state == EXIST
					&& _table[hashi]._kv.first == key)
				{
					return (HashData<const K, V>*) & _table[hashi];
				}

				++hashi;
				hashi %= _table.size();
			}

			return nullptr;
		}

		// 按需编译
		bool Erase(const K& key)
		{
			HashData<const K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;

				return true;
			}

			return false;
		}

	private:
		vector<HashData<K, V>> _table;
		size_t _n = 0; // 存储有效数据的个数
	};
}

9.闭散列缺点

发生哈希冲突后，几个位置映射的值会 相互影响

五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”

1. 开散列概念

开散列法又叫 链地址法(开链法) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合， 每一个子集合称为一个桶 ，各个桶中的元素通过一个 单链表 链接起来，各链表的头结点存储在哈希表中。
开散列中每个桶中放的都是发生 哈希冲突 的元素。

2.开散列哈希基本形式

//哈希桶
namespace hash_bucket
{
HashTable...//哈希表
HashNode...//节点

vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
}

//哈希表
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	typedef HashNode<K, V> Node;
	....};

//节点
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)
		{}
	};

3.开散列插入

【1】哈希桶基本插入问题

采取 头插方式

// 头插
  Node* newnode = new Node(kv);
  newnode->_next = _table[hashi];
  _table[hashi] = newnode;

【2】注意闭散列扩容问题

引入：
如果不扩容，不断插入某些桶越来越长效率得不到保障，负载因子适当放大一些，一般负载因子控制在1，平均下来就是每一个桶一个数据

// 负载因子到1就扩容
if (_n == _table.size())
{
	size_t newSize = _table.size()*2;
	vector<Node*> newTable;
	newTable.resize(newSize, nullptr);
	if(...)//剩余操作
}

【3】注意闭散列扩容后的操作

注意：这里我们采用 遍历旧表，顺手牵羊，把节点牵下来挂到新表的方式
原因：重新开空间开节点，消耗大，效率低

// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
	Node* cur = _table[i];//旧表
	while (cur)
	{
	    Node* next = cur->_next;//保存下一个地址
        //找到新的对应位置
	    size_t hashi = hf(cur->_kv.first) % newSize; //hf为仿函数，在开散列相关章可以查看
	     //头插到新表
		cur->_next = newTable[hashi];
		newTable[hashi] = cur;
		cur = next;
	}
	 //把旧表置空
	_table[i] = nullptr;
}
//最后交换新旧表首元素地址
_table.swap(newTable);

【4】闭散列完整插入操作

bool Insert(const pair<K, V>& kv)
		{
			if(Find(kv.first))
			{
				return false;
			}

			HashFunc hf;

			// 负载因子到1就扩容
			if (_n == _table.size())
			{
				size_t newSize = _table.size()*2;
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);

				// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						// 头插到新表
						size_t hashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

			size_t hashi = hf(kv.first) % _table.size();
			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return true;
		}

4. 开散列查找操作

Node* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

5. 开散列哈希完整代码展示

namespace hash_bucket
{
	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)
		{}
	};

	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				_table[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			if(Find(kv.first))
			{
				return false;
			}

			HashFunc hf;

			// 负载因子到1就扩容
			if (_n == _table.size())
			{
				size_t newSize = _table.size()*2;
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);

				// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						// 头插到新表
						size_t hashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

			size_t hashi = hf(kv.first) % _table.size();
			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;	
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first <<":"<< cur->_kv.second<< "->";
					cur = cur->_next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}

	private:
		vector<Node*> _table; // 指针数组
		size_t _n = 0; // 存储了多少个有效数据
	};
}

六.哈希表的使用

#include"HashTable.h"

int main()
{
	HashTable<int, int> ht;
	int a[] = { 1,111,4,7,15,25,44,9 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Erase(15);

	auto ret = ht.Find(4);
	//ret->_kv.first = 41;
	ret->_kv.second = 400;

	//HashTable<string, string, StringHashFunc> dict;
	HashTable<string, string> dict;
	dict.Insert(make_pair("sort", "排序"));
	dict.Insert(make_pair("left", "xxx"));
	auto dret = dict.Find("left");
	//dret->_kv.first = "xx";//不可修改，const
	dret->_kv.second = "左边";

	string s1("xxx");
	string s2("xxx");


	DefaultHashFunc<string> hf;
	cout << hf(s1) << endl;
	cout << hf(s2) << endl;
	cout << hf("bacd") << endl;
	cout << hf("abcd") << endl;
	cout << hf("abbe") << endl;
	cout << hf("https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=STATE&fenlei=256&rsv_pq=0xdd48647300054f47&rsv_t=1cd5rO%2BE6TJzo6qf9QKcibznhQ9J3lFwGEzmkc0Goazr3HuQSIIc2zD78Pt0&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=2&rsv_n=2&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=STAT%2526gt%253B&rsp=5&inputT=656&rsv_sug4=796") << endl;

	return 0;
}

文章出处登录后可见！

已经登录？立即刷新

【数据结构】万字一文手把手解读哈希————（开/闭散列）解决哈希冲突完整详解（6）

目录

一.哈希（散列）的基本概念

1.哈希（散列）的基本概念

2.哈希表的简单基本例子

二.哈希冲突(哈希碰撞)

三.哈希函数

1.哈希函数设计原则

2.常用的两种哈希函数

【1】 直接定址法–(常用)

【2】除留余数法–(常用)

【※】哈希表中的荷载因子

四.解决哈希冲突法一：闭散列-“开放地址法”

1. 线性探测＆二次探测

2.闭散列哈希中的基本状态

3.闭散列哈希的基本结构

4.线性探测中处理”查找”

5.线性探测中处理”插入”

【1】注意闭散列扩容问题

6.线性探测中处理”删除”

7. 闭散列适应多种类型转换————“仿函数”＆“类模板特化”&“仿函数在类模板中充当默认模板实参的应用”

【1】仿函数

【2】类模板特化

【3】仿函数在类模板中充当默认实参的应用

8.闭散列哈希完整代码展示

9.闭散列缺点

五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”

1. 开散列概念

2.开散列哈希基本形式

3.开散列插入

【1】哈希桶基本插入问题

【2】注意闭散列扩容问题

【3】注意闭散列扩容后的操作

【4】闭散列完整插入操作

4. 开散列查找操作

5. 开散列哈希完整代码展示

六.哈希表的使用

相关推荐

【1】直接定址法–(常用)