哈希(超详细版)

平平无奇。。。

4184人浏览 · 2024-11-14 11:55:42

平平无奇。。。 · 2024-11-14 11:55:42 发布

前言:我们在前面学习过了顺序结构和平衡树，我们知道顺序结构查找元素的效率为o(N)，平衡树查找元素效率为o(logN),它们都是通过比较一定次数才能查找到想要查找的元素，那么有没有一种结构能让我们不用通过比较就能直接查找到元素呢？答案是有的，大名鼎鼎的哈希就满足这种条件。

1.哈希概念

哈希就是通过某种函数，让元素的存储位置它的关键码标建立一一映射关系,在查找时,通过该函数可以很快的查找到所需的元素。

2.常见的哈希函数

我们知道哈希是需要通过哈希函数，让元素存储的位置和它的关键码建立一一映射的关系，那么我们接下来会讲解几个常用的哈希函数。

(1)直接定址法:给每一个元素都映射一个唯一的位置。

在这里插入图片描述

通俗点讲就是给每一个元素找一个唯一的位置，但是该方法有着致命的缺点，就是我们首先要知道元素的分布情况，从而开辟出足够容纳这些元素的空间。

显而易见，这种方法只能用于查找较少和连续的情况

在大量且不连续的数据中查找元素，直接定址法就会有很大的缺陷，那么我们需要有其他方法来处理大量且不连续的情况

(2)除留余数法:在限定大小的空间内将元素值一一映射进去，映射的公式是index(下标)=key%空间大小

在这里插入图片描述
我们细细观察图片，我们就会发现当我们在图片的基础上再插入14呢？通过公式算出14需要插入到的下标为4，但是我们发现4里面已经有数据了，我们把这种情况叫做哈希冲突。

哈希冲突:不同的元素映射到同一个位置

既然出现了问题，我们就得想方法解决问题，那么我们该如何解决哈希冲突呢？
解决哈希冲突有两种常用的方法:闭散列和开散列,听到这两个名词是不是感觉很懵逼，别着急，让我慢慢为你解释。

(1)闭散列(也叫开放定址法):当发生哈希冲突时，我们可以先判断哈希表有没有装满，如果未装满，那么我们就可以key放到冲突位置的下一个位置去。

注意:闭散列不能随便删除一个元素，例如如果删除了4这个元素，那么就不能找到14这个元素了，因为14这个元素的地址是依赖于4的地址的。所以线性探测只能通过标记法来表示伪删除一个元素

那么我们该如何寻找下一个位置呢？

线性探测:从发生哈希冲突的位置开始依次往后去寻找空位置来充当“下一个位置”

在这里插入图片描述

二次探测:从发生哈希冲突的位置开始2次方往后寻找“下一个位置”

(2)开散列(也叫拉链法，也叫哈希通，也叫开链法)（最优解）:把具有相同的地址的元素归类到一个集合(桶)里面，各个桶里面的元素通过链式结构把它们串联起来，再把链表的头节点存储在哈希表中。

在这里插入图片描述

3.哈希表的模拟实现(这里采用的是除留余数法)

我们知道除留余数法法会发生哈希冲突，我们有两种方法可以解决哈希冲突，我会为大家分别分享这两种解决方法的模拟实现。

1.哈希表插入数据

1.闭散列的模拟实现

为了防止和库里面的哈希实现冲突，我们需要加个命名空间进行封装。

namespace CLOSE_HASH//闭散列开放定址法
{

}

(1)要模拟实现哈希表，我们要先明白哈希表中的结点，需要有什么，哈希表中的元素需要有存放的数据，还有表示该位置的状态(为了解决哈希表中一个数据被删除了，从而导致找不到下一个数据)。

template<class T>
struct HashData
{
	T _data;
	State _state;//表示状态
}

(2)需要使用枚举类型来列出哈希表中元素的状态

enum State
{
	EMPTV,//表示空
	EXITS,//表示存在
	DELETE,//表示删除
};

(3)然后我们先给哈希表中的元素写出构造函数

默认将哈希表中的元素状态设置成空

	HashData(const T& data = T(), State state = EMPTV)
		:_data(data)
		, _state(state)
	{}

(4)当我们实现完了，哈希表中的元素里面的存放的东西，那么接下来我们需要处模拟出哈希表本身了，哈希表是一个表，其实本质就是一个数组，只不过该数组里面元素是表示哈希结点。，既然有哈希表了，那么我们还需要搞一个能表明哈希表中元素个数的变量。

我们还需要知道哈希表的模板参数需要有几个，由于哈希表是unordered_map和unordered_set的底层结构，那么最少需要两个模板参数，一个表示key，另一个表示value。

但是为了能同时满足unordered_map和unordered_set的使用，模板参数列表中还需要一个仿函数(KeyOfT)来提取出unordered_map和unordered_set的key键，然后进行判断，是存value还是pari<key,value>。

template<class K, class T, class KeyOfT>

template<class K, class T, class KeyOfT>
class HashTable
{
	typedef HashData<T> HashData;
		//底层是数组
	private:
		std::vector<HashData> _tables;
		size_t _num = 0;//表示存了多少个数据
};

(5)我们已经搭建好了哈希表的框架，然后我们需要开始实现哈希表的插入了。

哈希表插入数据，需要先探测该位置状态是否为空，如果为空才能插入。
在这里插入图片描述


			/*10.线性探测*/
			//先计算d中的key在表中映射的位置
			size_t index = koft(d) % _tables.size();
			//线性探测
			while (_tables[index]._state==EXITS)//存在往后探测
			{
				//如果表中有该值了，就不能插入了
				if (koft(_tables[index]._data) == koft(d))
				{
					return false;
				}
			/* 冲突了就往后加加寻找位置*/
				++index;
				//如果找到最后一个数据的下一个位置，需要从表头找
				if (index == _tables.size())
				{
					index = 0;
				}
			}

找到了位置，我们就需要插入数据了。

//插入数据
_tables[index]._data = d;
//再把该位置状态标记成插入
_tables[index]._state = EXITS;
_num++;

当随着我们不断插入数据时，那么哈希冲突发生的概率也会越来越大，那么我们该如何解决这个问题呢？
我们可以引入一个负载因子来表示哈希表中元素满的程度，负载因子=哈希表中实际存储的元素个数/哈希表的大小,我们可以发现负载因子越小，插入数据的效率越高(因为哈希表中元素少了，空位置就多了)，但是负载因子如果过于小的话，会造成空间浪费，那么经过前人的实现研究发现，当负载因子=0.7时，就可以开始增容了。


			if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)//这里是把负载因子扩大10,防止浮点数运算带来精度问题
			{
				HashTable<K, T, KeyOfT> newht;//创建一个哈希表对象
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				newht._tables.resize(newsize);//将该哈希表进行扩容

				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXITS)
					{
						//直接使用新的哈希对象调用insert
						//直接把数据插入到新的哈希表中
						newht.Insert(_tables[i]._data);
					}

				}

				//直接把新的哈希表和旧的哈希表进行交换
				_tables.swap(newht._tables);
			}

到这里为止，哈希表闭散列方法插入就已经完成了。
全部代码

//4.插入
bool Insert(const T& d)
{
	KeyOfT koft;
	if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)//这里是把负载因子扩大10,防止浮点数运算带来精度问题
	{
		HashTable<K, T, KeyOfT> newht;//创建一个哈希表对象
		size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		newht._tables.resize(newsize);//将该哈希表进行扩容

		for (size_t i = 0; i < _tables.size(); i++)
		{
			if (_tables[i]._state == EXITS)
			{
				//直接使用新的哈希对象调用insert
				//直接把数据插入到新的哈希表中
				newht.Insert(_tables[i]._data);
			}

		}

		//直接把新的哈希表和旧的哈希表进行交换
		_tables.swap(newht._tables);
	}

	/*10.线性探测*/
	//先计算d中的key在表中映射的位置
	size_t index = koft(d) % _tables.size();
	//线性探测
	while (_tables[index]._state==EXITS)//存在往后探测
	{
		//如果表中有该值了，就不能插入了
		if (koft(_tables[index]._data) == koft(d))
		{
			return false;
		}
	/* 冲突了就往后加加寻找位置*/
		++index;
		//如果找到最后一个数据的下一个位置，需要从表头找
		if (index == _tables.size())
		{
			index = 0;
		}
	}

	//插入数据
	_tables[index]._data = d;
	//再把该位置状态标记成插入
	_tables[index]._state = EXITS;
	_num++;

	return true;
}

2.开散列的模拟实现

开散列是通过在哈希表中每一个元素中挂上一个哈希桶，把哈希冲突的元素存入对应的哈希桶中，接下来由我来为大家画图分析开散列方法插入数据的过程。
在这里插入图片描述
全部代码

bool Insert(const T& data)
{
	//先算出需要插入数据的位置在表中的位置
	KeyOfT koft;
	//通过控制负载因子让哈希桶效率更高(一般让负载因子为1)
	//如果负载因子等于1，则增容，避免大量的哈希冲突
	if (_tables.size() == _num)
	{
		//增容
		std::vector<Node*> newtables;
		size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		//开辟空间
		newtables.resize(newsize);

		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				//先计算数据在新表中位置
				size_t index = koft(data) % newtables.size();
				cur->_next = newtables[index];
				newtables[index] = cur;

				//迭代cur
				cur = next;
			}
			//先把旧表置空
			_tables[i] = nullptr;
		}
		//再把新表和旧表交换
		_tables.swap(newtables);
	}
	//计算数据在表中映射的位置
	size_t index = koft(data) % _tables.size();

	//1.先查找这个值在不在表中
	Node* cur = _tables[index];
	while (cur)
	{
		//如果该值存在
		if (koft(cur->_data) == koft(data))
		{
			return false;
		}
		else
		{
			cur = cur->_next;
		}
	}

	//2.头插到挂载的链表中(尾插也可以)
	Node* newnode = new Node(data);
	//指向第一个
	newnode->_next = _tables[index];
	//再让自己变成第一个
	_tables[index] = newnode;

	++_num;
	return true;
}

2.哈希表查找数据

先通过处理余数法寻找出key在哈希表中的位置，然后再从该位置往哈希桶中寻找数据，找不到就返回nullptr

		Node* Find(const K& key)
		{
			KeyOfT koft;
			size_t index = key % _tables.size();
			//先找出cur在表中位置
			Node* cur = _tables[index];
			while (cur)
			{
				if (koft(cur->_data) == key)
				{
					return cur;
				}
				else
				{
					//找不到去下一个位置找
					cur = cur->_next;
				}
			}
			//找不到
			return nullptr;
		}

3.哈希表删除数据

需要在哈希表中删除数据，那么也需要先在哈希表中找到数据，才能进行删除，由于和查找思路差不多，删除和单链表的元素删除思路差不多，所以就不过多叙述了，直接上代码。

bool Erase(const K& key)
{
	KeyOfT koft;
	size_t index = key % _tables.size();
	//先保存单链表的前一个结点
	Node* prev = nullptr;
	//先找出cur在表中位置
	Node* cur = _tables[index];
	while (cur)
	{
		if (koft(cur->_data) == key)
		{
			//表示删除的结点在第一个结点
			if (prev == nullptr)
			{
				//让表的指针指向下一个结点
				_tables[index] = cur->_next;
			}
			else
			{
				//找到了
				prev->_next = cur->_next;
			}
			delete cur;

			return true;
		}
		else
		{
			prev = cur;
			//找不到去下一个位置找
			cur = cur->_next;
		}
	}
	return false;
}

测试哈希表

有句话说的好，代码写完莫大意，测试一把再欢喜。那么接下来我们就来测试一下我们写的哈希表吧！

1.先测插入数据(使用开散列的方法进行插入)


	void TestHashTable()
	{
		HashTable<int, int, SetKeyOfT<int>> ht;
		ht.Insert(4);
		ht.Insert(14);
		ht.Insert(24);
		ht.Insert(5);
		ht.Insert(15);
		ht.Insert(25);
		ht.Insert(6);
		ht.Insert(16)；
	}

在这里插入图片描述
2.哈希表删除数据

	void TestHashTable()
	{
		HashTable<int, int, SetKeyOfT<int>> ht;
		ht.Insert(4);
		ht.Insert(14);
		ht.Insert(24);
		ht.Insert(5);
		ht.Insert(15);
		ht.Insert(25);
		ht.Insert(6);
		ht.Insert(16);

		ht.Erase(24);
	}

int main()
{
	OPEON_HASH::TestHashTable();
	return 0;
}

在这里插入图片描述
3.哈希表查找数据(返回该数据的地址)

	void TestHashTable()
	{
		HashTable<int, int, SetKeyOfT<int>> ht;
		ht.Insert(4);
		ht.Insert(14);
		ht.Insert(24);
		ht.Insert(5);
		ht.Insert(15);
		ht.Insert(25);
		ht.Insert(6);
		ht.Insert(16);

		cout<<ht.Find(14)<<endl;
	}
int main()
{
	OPEON_HASH::TestHashTable();
	return 0;
}