哈希表的实现01

发布于：2025-05-15 ⋅ 阅读:(15) ⋅ 点赞:(0)

文章目录

很高兴和大家见面，给生活加点impetus！！开启今天的编程之路！！
在这里插入图片描述
今天我们进入哈希章节，为封装unordered系列打下坚实基础
作者：٩( ‘ω’ )و260
我的专栏：C++进阶，C++初阶，数据结构初阶，题海探骊，c语言
欢迎点赞，关注！！

哈希表的实现01

哈希概念

哈希(hash)又称散列，是⼀种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进行快速查找。

特点：无序+建立映射关系（存取都是用这个映射关系）

直接定址法

使用条件：当数据范围比价集中的时候，可以直接创建一个Hash数组来存放数据。效率非常高。
例题：字符串中第一个唯一字符
这里因为只含有小写字母，所以我们可以直接创建一个大小为26的Hash数组。a映射0，b映射1，以此类推

但是：该方法的缺陷也特别明显，当我的数据过于分散，就会造成大量的空间浪费，比如：我需要映射1和10000，那么1到10000之间的空间是不是都被浪费了呢？
因此：直接定址法只适用于数据集中的时候

哈希冲突

哈希冲突：本质上就是同一个位置可能会映射多个值，也被叫做哈希碰撞
理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。

在一个哈希表中，当哈希冲突越多的时候，哈希表的效率会被直线下降。因为建立的映射关系，哈希表的效率能够达到O（1）。所以，当发生哈希冲突的时候，需要进行处理

负载因子

假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子=N/M。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低

在库中：当负载因子大于0.7的时候就需要对数组进行扩容，因为负载因子越大，越容易出现哈希冲突，因为被占用的位子更多，所以需要扩容。
总之：哈希表是永远具有空位置的

将关键字转换为整数

我们将key映射到哈希表中，我们常见的方法是对整数进行取模操作，这样就可以得到一个银映射值。
如果不能取模怎么办？如果是string，负数，这些能区取模吗？肯定是不行的，所以，我们需要将将不能取模的使用一定的操作转换为整形。
这里我们需要传递一个仿函数。
只有当我们需要求key的映射的时候，才需要使用到这个仿函数，因为我们是将其转换成整形之后再来求模

转换成整数的时候我们必须保证哈希函数是一样的，这样才能够保证我们在插入的时候映射到的是一个固定的位置，查找的时候映射的也是一个固定的位置。

哈希函数

一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计

除法散列法：

顾名思义，假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M

使用除法散列法时，需要避免M为某些值，比如：2的k次幂，10的k次幂
因为如果是2的k次幂的话，一个int取模2k，这样就会造成该int二进制形式中只有k个位被参与比较了。前面的位没有参与比较。

说明：为什么只有k个位的参与比较？
因为我取模，是2k的倍数都会被取模为0，只有小于2k的数字才会被保留

我们来举例一下：
{63,31}看起来没有关联的值，如果M是16，也就是24 ，那么计算出的哈希值都是15，因为63的二进制后8位是00111111，31的二进制后8位是00011111。如果是10x ，就更明显了，保留的都是10进值的后x位，如：{112,12312}，如果M是100，也就是 ，那么计算出的哈希值都是12
以上的情况就会造成哈希冲突。

我们这里可以来扩展学习一下：在Java中，其实M是2的倍数。
这样通过可以不用取模，就直接进行位运算，而且前面我们已经提到过，如果是使用2的倍数在负载因子大于等于0.7的时候其实是更好扩容的。因为大小乘一个二倍就行。
例如：此时M是216，int%M得到后16位，随后我们将int右移16位，然后再来取模，目的：是为了让int中的所有位都能够来参与运算

那么我们c++中是如何进行处理的呢？
如果我们来二倍扩，当前M是质数，就一定能够保证2*M是质数吗？肯定是不能的，所以库中直接实现了一个素数表：

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
	53,97,193,389,769,1543,3079,6151,12289, 24593,49157,98317,196613, 393241, 786433,1572869, 3145739, 
	6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291
	};//不可能到达最后一个素数，当到达最后一个数时，内存都崩了
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);//>=
	return pos == last ? *(last - 1) : *pos;
}

当到达最后一个数时，应该说不可能会到达最后一个素数，因为到达最后一个素数，内存都已经爆了，程序肯定崩溃。

lower_bound取得是>=的数值

乘法散列法（了解）

乘法散列法对哈希表大小M没有要求，他的大体思路第⼀步：用关键字K乘上常数A(0<A<1)，并抽取出kA的小数部分。第二步：后再用M乘以kA的小数部分，再向下取整

这里我们的A取得是黄金分割点：A = ( 根号5 -1)/2 = 0.6180339887…

举例：假设M为1024，key为1234A=0.6180339887,Akey=762.6539420558，取小数部分为0.6539420558,M×((A×key)%1.0)=0.65394205581024=669.6366651392，那么h(1234)=669。

全域散列法（了解）

因为我们是设定了一个散列函数来映射key，所以，如果有人知道了这个key，就能够设置一组值来构造哈希冲突，为了解决这种情况，就只能够使用全域散列法来映射key。

全域散列法的目的主要给我们的散列函数增加随机性。

P需要选⼀个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)种可能性的全域散列函数组：h (key) =((a × key + b)%P )%M

细节：在插入和查找的情况下，必须是同一个散列函数，否则映射关系会被修改，就可能导致找不到了
假设P=17，M=6，a=3，b=4,则h (8) =34((3 × 8 + 4)%17)%6 = 5

但是：我们一般还是倾向于使用除法散列法作为哈希函数。

处理哈希冲突（开放定址法）

我们前面提到，在现实生活中，肯定会出现哈希冲突。
在开放定址法中所有的元素都放到哈希表里，当⼀个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于的。这里的规则有三种：线性探测、二次探测、双重探测。

线性探测：

1：从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。
2：h(key) = hash0 = key % M,hash0位置冲突了，则线性探测公式为：
hc(key,i) = hashi = (hash0 + i) % M， i = {1, 2, 3, …, M − 1}，因为负载因子小于1，则最多探测M-1次，一定能找到一个存储key的位置

我们来画一个图演示一下：
在这里插入图片描述
其实线性探测仍有不足，比如，a占了b的位置，当数据需要放到b上时，b又占了c的位置，当数据需要放到c上时，c又占了d的位置，以此类推。这样大量的哈希冲突就会导致效率直线下降。
这种现象被叫做：群集/堆积

二次探测

二次探测可以改善群集/堆积的问题。

1：从发生冲突的位置开始，依次左右按⼆次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。
2：h(key) = hash0 = key % M,hash0位置冲突了，则⼆次探测公式为：
hc(key,i) = hashi = (hash0 ± i2 ) % M， i ={1, 2, 3, …, M/2}（其实就是给i加了一个偏移量的平方）
3：⼆次探测当hashi = (hash0 − i2 )%M时，当hashi<0时，需要hashi+=M，否则会造成越界访问

举例：
在这里插入图片描述

双重散列

上述线性探测，二次探测还是有迹可循，双重散列就是将数据分散的更散，更不会那么集中。

1：h1 (key) =hash0 = key % M，hash0位置冲突了，则双重探测公式为：
hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M， i ={1, 2, 3, …, M}，这里有两个哈希函数
2：要求h (key) <M且M和h2 (key)互为质数，这样不至于在几个位置中来回跳，即当哈希冲突时，所有位置都有可能来存放这个冲突的数据。

这里我们就不再举例了

结论：其实这三种方法都有不足，因为当哈希冲突的时候，我们都是去抢别人的位置，那么比尔呢该放这个位置的时候，又会去抢别人的位置，这样就会造成一种恶性循环。

下片文章我们会详细讲解下一种方案。

代码实现：

接下来我们来进行代码实现：

结构定义

enum State
{//设置状态是为了查找的时候
	EMPTY,
	EXIST,
	DELETE
}

template<class K,class V>
struct HashData
{
	pair<K,V> _kv;
	State _state = EMPTY;//标记一下状态
}

template<class K,class V,class Hash>//传递一个仿函数，来计算整形，包含本身是整形的或者是转为整形的
class HashTable
{
private:
	vector<HashData<K,V>> _tables;	
}

插入操作

插入，我们直接来插入一个pair，不用实现泛型。
插入思路：我们先需要对里面存储的数据进行去重，再来看负载因子的情况，看是否需要扩容，计算key的映射，是否造成哈希冲突，是，进行线性探测，不是，直接将数据进行插入即可。来看代码：

bool Insert(const pair<K,V>& kv)
{
	if(_tables.Find(kv.first)) return false;//进行去重操作
	
	if((double)n/(double)_tables.size()>=0.7)//进行扩容，使用提前已经准备好的素数表，也是成二倍的趋势的
	{
		HashTable<K,V,Hash> newht(__stl_next_prime(_tables.size()+1));
		for(int i=0;i<newht.size();i++)
		{
			if(_talbes[i]._state == EXIST)
			{
				newht.Insert(_table[i]._kv);//直接复用现有的Insert逻辑
			}
		}
		_tables.swap(newht._table);//类似于赋值重载的现代写法
		return true;
	}
	Hash hs;
	int hash0=hs(key)%_tables.size();
	int hashi=hash0;
	int i=1;
	//看是否需要进行线性探测，只要是空或者删除就能够进行数据覆盖
	while(_tables[hashi]._state == EXIST)
	{
		hashi+=i;
		i++;
		hash%=_tables.size();
	}
	//找到空的位置，建立映射关系
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	++_n;
}

总结：哈希表中的扩容的代价很大，因为扩容之后需要重新建立映射关系，所以所有存在的数据都需要进行重新映射。

查找和删除

细节：查找和删除使用的形参都是key，无论是kv型，还是k型

查找思路：需要先计算key的映射，如果造成了哈希冲突，执行线性探测，找到了，返回地址，反之nullptr

HashData<K,V>* Find(const K&key)
{
	Hash hs;
	int hash0=hs(key)%_tables.size();
	int hashi=hash0;
	int i=1;
	while(_table[hashi] !=EMPTY)//只要状态是空的话，才停止循环
	{
		if(_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
		{//因为删除的时候我只是修改一下状态，不是真的将数据给删除了。所以需要判断一下状态
			return &_tables[hashi];
		}
		hashi+=i;
		i++;
		hash%=_tables.size();
	}
	
	return nullptr;//没找到
}

删除思路：这里我们直接复用查找的思路即可：

bool Erase(const K& key)
{
	HashData<K,V>* ret = _tables.Find(key);
	if(ret)
	{
		ret->_state = DELETE;
		--_n;
		return true;
	}else{
		return false;
	}
}

仿函数转整形

在现实生活中，key大多数情况都是string，所以我们需要设置仿函数来进行对string的映射，一般的方法是对string中的所有字符ascll码进行相加即可。
来看代码：

struct StringHashFunc
{
	size_t operator()(string& s)
	{
		size_t hash = 0;
		for(auto& e:s)
		{
			hash += e;
		}
		return hash;
	}
}

如果说我们给的字符串是"abc"和"cba"，此时ascll码之和是一样，可以尝试如下解决方案。
我们根据顺序迭代器遍历的时候我们来乘一个131,这样就能够体现出顺序差别。

struct StringHashFunc
{
	size_t operator()(string& s)
	{
		size_t hash = 0;
		for(auto& e:s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
}

个人新得总结：

1：写仿函数这种东西，operator()中的this最好都添加上const修饰
2：哈希冲突，哈希探测越多，效率越低，让更多的bit为参数运算，能够降低哈希冲突的概率
3：二次，双重探测的目的都是将数据分散
4：%的时候一定是size（），因为size才是有效数据个数，因为后面需要使用到[],所以只有在size的长度中才能够使用[]，reverse操作的是capacity()。
5：有符号%无符号，有符号会被隐式类型转化为无符号
6：如果不能够取模，需要配对一个对应的仿函数，而且也要做到区别，可以进行每个元素*131来进行区别
7：在进行整形转换的运算时，我们一般会选取能够进行转整形操作的数据，例如：字符串或负数，其他结构体，例如Date是不支持的，库中也不支持。

结语

感谢大家阅读我的博客，不足之处欢迎指正，感谢大家的支持
逆水行舟，楫摧而志愈坚；破茧成蝶，翼湿而心更炽！！加油！！

在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布