开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构之＜哈希表＞ -> 正文阅读

[数据结构与算法]数据结构之＜哈希表＞

🌈前言

本篇文章进行数据结构中哈希表的学习！！！

🌅哈希表

🚁1、哈希概念

概念：

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

理想的搜索方法：

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

当向该结构进行：

插入元素：根据待插入元素的关键码，再使用一个函数计算出该元素的存储位置并按此位置进行存放
搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：我们有一组数据 {1，3，6，8，9}
哈希函数设置为：hash(key) = key % capacity，capacity为存储元素底层空间总的大小

在这里插入图片描述

总结：使用该方法，不用对关键码进行多次比较，所以搜索速度很快！！！

🚂2、哈希冲突

哈希冲突：

对于两个数据元素的关键字K_i和K_j（i != j），有K_i ！= K_j，但也有：Hash(K_i) == Hash(K_j)，即：
不同关键字通过相同的哈希函数计算出相同的映射地址，该现象成为哈希冲突或哈希碰撞
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

🚃3、哈希函数

引起哈希冲突的原因可能是：哈希函数设计不够合理。哈希函数设计原则：

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

常见哈希函数：

直接定址法（常用）：

取关键字的某个线性函数为散列地址：Hash(Key) = A * Key + B，优点：简单，均匀，但是需要事先知道关键字的分布状况
使用场景：适合查找比较小且连续的情况：【字符串中第一次出现一次的字符】

除留余数法（常用）

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

平方取中法（了解）

假设关键字为1234，它平方就是1522756，抽取中间值3位227作为哈希地址；再比如关键字为4321，它平方就是18671041，抽取中间值3位671（或710）作为哈希地址
应用场景：不知道关键字的分布，而位数又不是很大的情况

折叠法（了解）

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

随机数法（了解）

选择一个随机函数，取关键字的随机函数值作为它的哈希地址，即：Hash（Key）= random(Key)，其中random为随机数函数

🚄4、哈希冲突解决方法

🌈前言：解决哈希冲突的两种常用方法：闭散列和开散列

🚅4.1、闭散列

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

🚆4.1.1、线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止

插入：

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

在这里插入图片描述

删除：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索，比如：删除元素11，直接删除会给后面查找22带来很大的影响
线性探测可以设计一个枚举来标记哈希表中每个位置的状态是”空“，”存在“还是”删除“，然后使用伪标记法进行删除，将状态改为”DELETE“

// 哈希表每个空间给个标记
enum State
{
    EMPTY,    // 空状态
    EXIST,	  // 存在状态
    DELETE    // 已删除状态
}

闭散列的扩容：

在这里插入图片描述

关于关键值(key)自定义类型问题：

如果关键值是自定义类型时，我们就不能将他隐式的转换成为无符号整数，需要实现一个仿函数来进行转换，一般只需要转换string，后面增加直接特化即可

// key为sring
template <typename K>
struct HashDF
{
	size_t operator()(const string& str)
	{
		size_t hash_sum = 0;

		for (auto& e : str)
		{
			hash_sum = hash_sum * 131 + e;
		}
		return hash_sum;
	}
};

// 模板特化...
template <>
struct HashDF<...>
{};

线性探测的实现：

namespace CloseHash
{
	// key为sring
	template <typename K>
	struct HashDF
	{
		size_t operator()(const string& str)
		{
			size_t hash_sum = 0;

			for (auto& e : str)
			{
				hash_sum = hash_sum * 131 + e;
			}
			return hash_sum;
		}
	};

	// 哈希表中值的状态
	enum State
	{
		EMPTY,	// 空
		EXIST,	// 存在
		DELETE	// 删除
	};

	template<typename K, typename V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY; // 插入扩容时默认初始化为空状态
	};

	template<typename K, typename V, typename Function = HashDF<K>>
	class HashTable
	{
	private:
		typedef HashData<K, V> HD;
	public:
		bool Insert(const pair<K, V>& kv)
		{
			// unordered_map不允许冗余
			if (Find(kv.first) != nullptr)
				return false;

			// 负载因子到0.75及以上，就扩容
			if (_tables.size() == 0 || _n * 100 / _tables.size() >= 75)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

				// 扩容以后，需要重新映射 -- 如果直接拷贝，则导致映射位置的改变
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize);

				// 遍历旧表，插入newHT
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}
				// 使用vector中swap成员函数进行交换
				newHT._tables.swap(_tables);
			}

			// 将插入的值转换成无符号整形然后%哈希表（有效数据）大小 -- 处理负数情况
			size_t starti = df(kv.first);
			starti %= _tables.size();

			size_t hashi = starti;
			size_t i = 1;

			while (_tables[hashi]._state == EXIST)
			{
				// hashi = starti + (i * i); // 二次探测
				hashi = starti + i;			 // 线性探测
				++i;
				hashi %= _tables.size();
			}

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

			return true;
		}

		bool erase(const K& key)
		{
			// 查找是否存在
			HD* p = Find(key);
			// 不为空则修改值的状态未DELETE（删除）
			if (p != nullptr)
			{
				p->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}

		HD* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			size_t starti = df(key);
			starti %= _tables.size();

			size_t hashi = starti;
			size_t i = 1;

			// 值的状态不为空就继续查找
			while (_tables[hashi]._state != EMPTY)
			{
				// 值的状态不为删除状态并且key相等
				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				hashi = starti + i;
				++i;
				hashi %= _tables.size(); // 防止非法访问
			}
			return nullptr;
		}
	private:
		vector<HD> _tables;
		size_t _n = 0; // 存储关键字个数
		Function df;
	};

在这里插入图片描述

总结：

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

🚇4.1.2、二次探测

二次探测：线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题

插入：

找下一个空位置的方法为：H = (H₀ + i²) % m,或者：H = (H₀ - i²) % m,。其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小

在这里插入图片描述

注意：二次探测就不实现了，跟线性探测基本一致，就是hashi每次走i²步

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容
闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

🚈4.2、开散列

🚉4.2,1、概念及结构

开散列的概念：

开散列也叫链地址法（哈希桶），首先对关键码集合用散列（哈希）函数计算散列地址，具有相同地址的关键码归于同一子集合
每一个集合称为一个桶，各个桶的元素通过一个链表链接起来，各链表的头节点存储在哈希表中…

// 哈希表节点 -- 这里实现的是键对值结构
template <typename K, typename V>
struct HashNode
{
public:
	HashNode(const pair<K, V>& kv)
		: _kv(kv)
		, _next(nullptr)
	{}
public:
	pair<K, V> _kv;
	HashNode<K, V>* _next;
};

template <typename K, typename V, typename hashF = HashDF<K>>
	class HashTable
{
private:
	vector<Node*> _tables;
	size_t _n = 0;
	hashF HashDF;
};

🚐4.2,2、插入

开散列的插入：

哈希桶的结构：哈希桶其实是一个数组指针，每个桶（数组中的元素）里面存储的是一个链表
链表里面有指向下一个节点的指针和值域
插入数据就相当于对链表进行头插就行了，将关键码映射的地址直接头插到对应的桶中

在这里插入图片描述

注意：从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素，冲突的值在链表中进行头插

bool Insert(const pair<K, V>& kv)
{
	// 判断key是否存在哈希桶中，不冗余版本
	if (Find(kv.first))
		return false;

	// 跟闭散列的方法一样需要继续模表大小，找桶位置
	size_t hashi = kv.first;
	hashi %= _tables.size();

	// 构造需要插入的键对值，然后插入到映射的位置 -- 画图
	Node* newNode = new Node(kv);
	newNode->_next = _tables[hashi];
	_tables[hashi] = newNode;
	++_n;

	return true;
}

插入操作：
在这里插入图片描述

🚑4.2,3、扩容

开散列的扩容

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容
开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容

void _CheckCapacity()
{
	if (_tables.size() == 0 || _tables.size() == _n)
	{
		size_t NewSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

		// 把旧哈希桶的节点重新映射到新开辟的哈希桶
		HashTable newHT;
		newHT._tables.resize(NewSize, nullptr);

		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur != nullptr)
			{
				// 将旧哈希桶的值挪到新哈希桶中 -- 头插
				Node* next = cur->_next; // 保存下一个节点，挪动后防止找不到
				// 需要重新映射新扩容后的哈希桶，模新长度的哈希桶
				size_t hashi = HashDF(cur->_kv.first) % NewSize; 
				cur->_next = newHT._tables[hashi];
				newHT._tables[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}
		newHT._tables.swap(_tables);
	}
}

🚒4.2,4、删除

开散列的删除：

删除其实很简单，比find和insert难度还低
首先找到这个关键码映射在哪个桶中然后在这个桶中进行查找，找到进行删除，相当于链表的删除

bool erase(const K& key)
{
		// 找这个关键字(key)在哪个桶中
		size_t hashi = key;
		hashi %= _tables.size();
		
		// 维护一个前驱指针，找到删除节点后直接链接到删除节点下一个节点
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur != nullptr)
		{
			if (cur->_kv.first == key)
			{
				// 删除位置为"头"
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				--_n;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
		}
}

在这里插入图片描述

🚓4.2,5、思考

开散列的思考：

只能存储key为整形的元素，那么自定义类型要怎么解决呢？？？

这时候就体现到仿函数的价值了，可以套一层仿函数来进行转换
可以将这个自定义类型底层可以转换的东西都转换成无符号整形

// 仿函数：处理特殊的Key值问题 -- 后面需要对数据进行无符号整形转换
template <typename K>
struct HashDF
{
	size_t operator()(const K& key)
	{
		return static_cast<size_t>(key);
	}
};

template <>
struct HashDF<string>
{
	size_t operator()(const string& str)
	{
		size_t HDS = 0;
		for (auto& e : str)
		{
			HDS = HDS * 131 + static_cast<size_t>(e);
		}
		return HDS;
	}
};

template <typename K, typename V, typename hashF = HashDF<K>>
	class HashTable
{
private:
	vector<Node*> _tables;
	size_t _n = 0;
	hashF HashDF;
}

🚔5、哈希桶完整代码

#pragma once

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

// 哈希桶（指针数组）：哈希表中存储指针，这个指针存储映射的值，映射相同位置时，创建新的节点直接链到这个指针中
namespace BUCKetHash
{
	// 仿函数：处理特殊的Key值问题 -- 后面需要对数据进行无符号整形转换
	template <typename K>
	struct HashDF
	{
		size_t operator()(const K& key)
		{
			return static_cast<size_t>(key);
		}
	};

	template <>
	struct HashDF<string>
	{
		size_t operator()(const string& str)
		{
			size_t HDS = 0;
			for (auto& e : str)
			{
				HDS = HDS * 131 + static_cast<size_t>(e);
			}
			return HDS;
		}
	};

	// 哈希表节点
	template <typename K, typename V>
	struct HashNode
	{
	public:
		HashNode(const pair<K, V>& kv)
			: _kv(kv)
			, _next(nullptr)
		{}
	public:
		pair<K, V> _kv;
		HashNode<K, V>* _next;
	};

	template <typename K, typename V, typename hashF = HashDF<K>>
	class HashTable
	{
	private:
		typedef HashNode<K, V> Node;
	public:
		HashTable() = default;
		HashTable(const HashTable& ht)
		{
			_tables.resize(ht._tables.size(), nullptr);
			for (size_t i = 0; i < ht._tables.size(); ++i)
			{
				Node* cur = ht._tables[i];
				while (cur != nullptr)
				{
					this->Insert(cur->_kv);
					cur = cur->_next;
				}
			}
		}

		HashTable& operator=(const HashTable ht)
		{
			HashTable tmp(ht);
			this->_n = tmp._n;
			tmp._tables.swap(_tables);
			return *this;
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				while (cur != nullptr)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			if (_tables.size() == 0 || _tables.size() == _n)
			{
				size_t NewSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				// 这种方法是拷贝，效率低
				/*HashTable newHT;
				newHT._tables.resize(NewSize, nullptr);

				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur != nullptr)
					{
						newHT.Insert(_tables[i]->_kv);
					}
				}
				newHT._tables.swap(_tables);*/

				// 把旧哈希桶的节点重新映射到新开辟的哈希桶
				HashTable newHT;
				newHT._tables.resize(NewSize, nullptr);

				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur != nullptr)
					{
						// 将旧哈希桶的值挪到新哈希桶中 -- 头插
						Node* next = cur->_next; // 保存下一个节点，挪动后防止找不到
						size_t hashi = HashDF(cur->_kv.first) % NewSize; // 需要重新映射新扩容后的哈希桶，模新长度的哈希桶

						cur->_next = newHT._tables[hashi];
						newHT._tables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				newHT._tables.swap(_tables);
			}

			// 跟闭散列的方法一样需要继续模表大小
			size_t hashi = HashDF(kv.first);
			hashi %= _tables.size();

			// 构造需要插入的键对值，然后插入到映射的位置 -- 画图
			Node* newNode = new Node(kv);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			++_n;

			return true;
		}

		bool erase(const K& key)
		{
			size_t hashi = HashDF(key);
			hashi %= _tables.size();

			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur != nullptr)
			{
				if (cur->_kv.first == key)
				{
					// 删除位置为"头"
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			// 查找跟闭散列差不多
			size_t hashi = HashDF(key);
			hashi %= _tables.size();

			// 对映射的位置进行循环遍历查找
			Node* cur = _tables[hashi];
			while (cur != nullptr)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}
	private:
		vector<Node*> _tables;
		size_t _n = 0;
		hashF HashDF;
	};
}