哈希表(底层结构剖析-- 上)

哈希表底层结构剖析

哈希概念

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

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

3:哈希表中插入,查找函数方法:
插入元素 : 根据待插入元素的关键码,以此函数计算该元素的存储位置并按照此位置进行存放.

搜索元素:
对元素的关键码进行同样的计算,把求得的函数值当作元素的存储位置,在此存储结构中按此位置取元素关键码比较,如果关键码相等,则查找成功.

综合以上说法: 其中哈希方法中使用的某种转换函数为哈希(散列)函数,构造出来的结构称为哈希表(又称为散列表)

例如;数据集合{ 1,7,6,4,5,9 };
哈希函数设置为: hash(key) = key % capacity. 其中capacity为存储元素底层的空间总的大小.
图示如下:

哈希冲突

哈希冲突即: 不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突. 把具有不同关键码而具有相同哈希地址的数据元素称为"同义词.

哈希函数

引起哈希冲突的一个原因可能是: 哈希函数的设计不够合理.
常见哈希函数:
1: 直接定址法(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

2:除留余数法(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址.(其中p等于容器大小):
图示如下:

但是,以上方法也容易引起哈希冲突.

哈希冲突解决办法

解决哈希冲突的两种常见方法为: 闭散列和开散列

.

闭散列( 线性探测 + 二次探测)

线性探测:从发生冲突的位置,依次向后探测,直到寻找到下一个空位置为止.

插入函数:
(1): 通过哈希函数获取待插入元素在哈希表中的位置.
(2): 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,则使用线性探测找到下一个空位置,插入新元素.
例如:
在下列数据集合 : { 1,4,5,6,7,44,9) 中,元素44与4的位置发生哈希冲突,那么便从4的位置后面依次寻找空的位置,直到位置8中.

线性探测缺点:
线性探测在某个位置冲突很多的情况下,数据之间会互相占用位置,从而导致冲突一片.
例如:
在以下数据集合中,11,21,31与1发生哈希冲突,只能在1的后续空位置中插入元素,但是11占用了2的位置,又导致11与2之间发生哈希冲突,而2又是占用了其他元素的位置,有可能引发别的元素之间的哈希冲突.

面对线性探测的缺点,有人提出了二次探测:
二次探测是由冲突位置开始,每次累加计算i^2(i>=0),这样就会将连续冲突互相占用位置的情况减弱,和线性探测相比,数据的位置有效分开了.

但是,如果当我们在2的后面添加上12,此时 hash = 12 % 10 = 2,
12经过线性探测后在下标为6的位置,hash +i = 2 + 4 = 6.
经过二次探测后在 hash + i^2 = 2 + 2^2 = 6,
所以此时12应该在下标为6的位置.

开散列

开散列又叫做链地址法(开链法),首先对关键码集合用散列函数计算散列地址,将具有相同地址的关键码归于同一 子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,并且将各链表的头结点存储在哈希表中.

哈希桶的产生正是为了有效解决闭散列的占用相互影响导致连续冲突的问题.

哈希表闭散列方法的模拟实现

基本框架

哈希表主要由2个内置成员:
1:存储有关哈希结点类的vector.
2: 记录哈希表中的有效元素个数_size;

//闭散列哈希表
template<class K, class V>
class HashTable
{
public:
	//...
private:
	vector<Data> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

vector _table中就有一个_size,为什么哈希表中还额外需要一个_size?

因为删除为伪删除,并非将数据真正删除了,所以vector中的_size还包括了删除过的数据,而哈希表中的size实际上才真正代表哈希表中存储的有效数据个数.

有关哈希数据的类

哈希表中存储的正式该数据类型,主要存储2个内置类型:
1: KV结构的键值对.
2: 标明状态的枚举类型 (状态标志位)

enum State
{
	EXIST,
	DELETE,
	EMPTY,
};
template <class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

为什么要额外添加标志位呢?

例如:
当我们删除3,再去寻找20时,通过线性探测由下标为2的位置开始寻找,
如果找的有数据但是 不是20,就从下一个位置继续寻找.
如果找到的位置为0,此时说明该位置为空,就说明找不到了,因为根据线性探测是根据哈希函数找到对应位置,如果哈希冲突,就从对应位置开始寻找到空位置插入的.

综合以上情况 : 当我们删除3,该位置数据就变成了0或者-1(删除一般为伪删除),此时寻找的时候根据哈希函数正好是从下标为2的位置开始寻找,此时便会直接返回空,进而导致3的后面明明有20,却找不到20的情况,我们也可以从开始全部找一遍,可是这也失去了哈希表的优势.

有了标志位,当我们将3删除的时候,就将元素3的位置状态标为DELETE,当我们要查找20的时候,从3的位置开始查找时碰到DELETE就不停下来,继续往后查找.并且再次插入22时还可以在3的位置插入.

标志位的意义:
EMPTY的标志标明查找时停止的标志,插入时可以在该位置处放值.
DELETE的标志标明查找时不停止,插入时可以在该位置处放值.
EXIST的标志标明查找时不停止,插入时不可以在该位置放值.

插入函数

插入函数主要分为3个步骤:
1: 复用find函数查找数据是否冗余,如果哈希表中有相同数据就不用插入了.

2:如果没有超过负载因子,查找空位置插入数据.

3: 扩容.

下面根据2,3两个个步骤主要展开描述:
2: 如果没有超过负载因子,查找空位置插入新数据.
不扩容插入新数据分为2个步骤:
1: 根据哈希函数计算对应位置,必须%_table.size(),不能除以_table.capacity(),因为在顺序表中[]中只能在size范围内访问,%size()能够保证hashi而在size范围之内.
如果%_table.capacity(),那么hashi的位置有可能在size范围之外,这样在之后的[操作中会导致assert断言错误.

2: 线性探测删除标志或者空标志的位置,为了如果从标志位开始找到哈希表的尾端都没找到,为了防止在size范围之外,我们可以将hashi % size(),让它能够归零寻找.
如果找到,则将数据插入,并将_size+1,状态改为存在.

template < class K, class V>
class HashTable
{
public:
	bool Insert(const pair<K, V>& kv)
	{
size_t start = kv.first % _table.size(); 

		while ( _table[hashi]._state == EXIST )   
		{
			++hashi;
			hashi %= _table.size();    
		}
		_table[hashi]._kv = kv;              //目标位置的存储对象的_kv就等于要插入kv的键值.
		_table[hashi]._state = EXIST;        //将目标位置存储对象的状态修改为EXIST.
		++_size;
		return true;

3: 扩容.

哈希表什么情况下扩容? 如何扩容?

负载因子: 散列表的荷载因子(负载因子)定义为: a = 填入表中的元素个数 / 散列表的长度.

其中,a代表散列表装满程度的标志因子,由于表长是定值.
a越大,表明填入表中的元素越多,产生哈希冲突的可能性就越大.
a越小,表明填入表中的元素越少,产生哈希冲突的可能性就越小.

对于开放定址法,负载因子是特别重要元素,应严格限制在0.7-0.8以下.
所以,在扩容时我们将负载因子定为0.7,一旦大于等于0.7就扩容.

扩容主要分为3个步骤:
1: 确定新表长度,创建新表.

2: 将旧表数据填入到新表当中.

3: 调用vector中的swap,将旧表与新表交换.(现代写法)

插入函数线性探测版:

bool Insert(const pair<K, V>& kv)
	{
		Hash hash;
		if ( Find(kv.first ))         
		{
			return true;
		}
		
		//如果分子为7,分母为10,结果却等于0,所以为了避免这种情况,我们可以让分子乘以10,结果再乘以10.
		if (_table.size() == 0 || 10 * _size / _table.size() >= 7) //1:		
		{

			size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
			HashTable<K, V> newTable;
			newTable._table.resize(newSize);
			for (auto& e : _table)        //遍历旧表,依次将旧表的数据放入到新表当中.  
			{
				if (e._state == EXIST)
				{
					newTable.Insert(e._kv);  
				}
			}
			_table.swap(newTable._table);  //现代写法.

		}
		size_t hashi = hash(kv.first) % _table.size(); 

		while ( _table[hashi]._state == EXIST )  
		{                    
			
			hashi++;

			hashi %= _table.size();          //此时不能超过size范围,需要将hashi回到起点重新开始寻找,直到找到空位置.
		}
		_table[hashi]._kv = kv;           
		_table[hashi]._state = EXIST;      
		++_size;
		return true;
	}

插入函数二次探测版:
针对于二次探测,我们要提前记录哈希映射位置,在探测时都是在这个位置的基础上+i*i的.

bool Insert(const pair<K, V>& kv)
	{
		Hash hash;
		if ( Find(kv.first ))         
		{
			return true;
		}
		
	
		if (_table.size() == 0 || 10 * _size / _table.size() >= 7) 
		{
			size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
			HashTable<K, V> newTable;
			newTable._table.resize(newSize);
			for (auto& e : _table)        
			{
				if (e._state == EXIST)
				{
					newTable.Insert(e._kv);   
				}
			}
			_table.swap(newTable._table);  //现代写法.

		}
		size_t start = hash(kv.first) % _table.size(); 

		size_t hashi = start;    //二次查找,记录哈希映射位置.

		size_t i = 0;


		while ( _table[hashi]._state == EXIST )  
		{
			++i;                                     
			
			hashi = start + i * i;     //每次都是从哈希映射位置处+i*i.

			hashi %= _table.size();          
		}
		_table[hashi]._kv = kv;              
		_table[hashi]._state = EXIST;        
		++_size;
		return true;
	}

注意:
1:负载因子超过0.7就扩容，这样就说明哈希表永远只能存储百分之70的位置,这样就不会在hashi归零时寻找一直找不到位置，防止造成死循环问题．
2: 如果最开始表的数据个数为0的,也要进行扩容,否则刚开始哈希表_size为0,防止发生除0错误.
3:将旧表数据填入新表时,我们可以调用Insert函数过程中,因为哈希表的容量已经开辟好了,肯定不会扩容.所以编译器只会执行if之后的语句,重新计算目标数据要插入的位置,这样就服用了insert部分代码.
如果重新创建_table,然后将旧表的数据放入到新表的化,因为新表的长度原来在旧表中冲突的数据在新表中就不冲突了,原来在旧表中不冲突的位置,在新表中反而冲突,
这样在每次将旧表数据放入新表中都要重新计算插入位置.

删除函数

哈希表中的删除实际上是伪删除,主要分为3个步骤:
1: 查找哈希表中是否有目标数据.

2: 将要删除的数据中的状态改为DELETE.

3: 如果删除成功就将哈希表的数据个数-1,返回true,如果失败返回false;

bool Erase(const K& key)                  
	{
		HashData<K,V>* ret = Find(key);   //查找哈希表中是否有删除数据.
		if (ret)
		{
			ret->_state = DELETE;
			--_size;                     
			return true;
		}
		return false;
	}

查找函数

哈希表中查找函数主要分为2个步骤:
1: 判断表是否为空,防止哈希函数计算时发生除零错误.

2: 通过哈希函数计算数据查找开始的位置,我们要查找的数据必须符合状态为EXIST并且存储数据等于目标数据条件,如果找到空位置就说明找不到了,就退出循环.

	HashData<K,V>* Find(const K& key)                  
	{
		if (_table.size() == 0)                //如果表为空,就会发发生除零错误,所以必须要先判断.
		{
			return nullptr;
		}
		size_t hashi = key % _table.size();   //左边是无符号整数,右边是有符号整数,相除时右边的类型会发生整型提升,提升为无符号整数,然后算出的这个位置自然就为4了.
		                           


		size_t start = hashi;

		while (_table[hashi]._state != EMPTY )  //哈希映射的那个位置不为空就继续查找.
		{
			if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)  //当映射的那个位置不为空并且状态也不能是删除，_kv.first等于那个值就找到了．
			{
				return &_table[hashi];
			}
			++hashi;                                 //哈希映射的那个位置不为空就继续查找.
			hashi %= _table.size();              //归零,防止越界.
			
			if (hashi == start)
			{
				break;
			}
		}
		return nullptr;
		
	}

注意:
1: 考虑到哈希表有可能经过多次删除插入,造成哈希表中没有空的位置,所以当查了一圈,还没有找到时,应该退出循环,表明找不到了.

增加仿函数将所有数据类型转换为整型

如果当我们向哈希表中插入如string数据类型时,插入函数使用哈希函数计算插入位置时string数据类型是不能取模的.并且凡是使用哈希函数的地方我们都要使用仿函数.
为此,为了哈希表支持更多数据类型,我们增加了仿函数.
1: 对于数据类型为K(指针,整数),我们把它转换为无符号整数.

2: 对于字符类型,我们将字符串中每个字母转换为ASCII码相加.得到这个字符串的ASCII码之和,此时字符串类型就转换成了无符号整数类型.

可是,如果当我们所传的字符串不同,但是字符串所组成的ASCII码却相同,此时也容易导致哈希冲突.

例如字符串 : “abcd” 和 “bcad”.

此时:
我们便可以采用BKDR算法,在val每次累加之前都乘以固定值131.

仿函数代码如下:

template < class K >                   //仿函数的默认值,如果不显示传就会默认调用.
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template< >                                 //1:对于常见类型,为了方便,我们可以对类模板进行特化.并且根据实参所传类型,优先走特化版本.
struct HashFunc <string>                 //2: 函数特化针对的是第一个类模板.,所以类模板名及其模板参数类型必须相同,只不过后面将模板参数显示写出来并使用了而已.
	                                     
{
	size_t operator()(const string& key)
	{
		size_t  val = 0;
		for ( auto& ch : key ) //遍历string,将一个个字母替换成ASCI码进行相加.
		{ 
		    val *= 131;        //相加之前,val每次乘以131.
			val += ch;
		}
		return val;
	}
};
//哈希表
template < class K, class V,class Hash = HashFunc<K> >  //1:仿函数实则是一个类调用operator()重载,实现函数的功能.
	                                      // 2:仿函数模板跟平常类模板一样,需要那个仿函数,使用时就将哪个仿函数带上模板参数类型传过去.

class HashTable
{
public:
	//...
private:
	vector<Data> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

注意:文章来源地址https://www.toymoban.com/news/detail-428146.html

哈希表开散列方法的模拟实现(增加仿函数版)

include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
enum State
{
	EXIST,
	DELETE,
	EMPTY,
};
template <class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template < class K >                   //仿函数的默认值,如果不显示传就会默认调用.
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template< >                                 //1:对于常见类型,为了方便,我们可以对类模板进行特化.
struct HashFunc <string>                    //并且根据实参所传类型,优先走特化版本.
	                                        //2: 函数特化针对的是第一个类模板.,所以类模板名及其模板参数类型必须相同,只不过后面将
	                                        //模板参数显示写出来并使用了而已.
	                                        
	                                       //2: 仿函数实则是一个类调用operator()重载,实现函数的功能.
	                                      // 仿函数模板跟平常类模板一样,需要那个仿函数,使用时就将哪个仿函数带上模板参数类型传过去.
	                                     
{
	size_t operator()(const string& key)
	{
		size_t  val = 0;
		for ( auto& ch : key ) //遍历string,将一个个字母替换成ASCI码进行相加.
		{ 
		    val *= 131;
			val += ch;
		}
		return val;
	}
};

template < class K, class V,class Hash = HashFunc<K> >
class HashTable
{
public:
	bool Insert(const pair<K, V>& kv)
	{
		Hash hash;
		if ( Find(kv.first ))         //防止数据冗余,如果哈希表中有数据已经存在的话就不需要再插入了.
		{
			return true;
		}
		
		//2:如果分子为7,分母为10,结果却等于0,所以为了避免这种情况,我们可以让分子乘以10,结果再乘以10.
		if (_table.size() == 0 || 10 * _size / _table.size() >= 7) //1:负载因子超过0.7就扩容，这样就说明哈希表永远只能存储百分之70的位置,这样就不会在hashi归零时一直找不到位置，防止造成死循环问题．
		//3:如果最开始表的数据个数为0的,也要进行扩容.
		{

			size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
			HashTable<K, V> newTable;
			newTable._table.resize(newSize);
			for (auto& e : _table)        //遍历旧表,依次将旧表的数据放入到新表当中.  
			{
				if (e._state == EXIST)
				{
					newTable.Insert(e._kv);   //1:调用Insert函数过程中,因为哈希表的容量已经开辟好了,肯定不会扩容.
										  //所以编译器只会执行if之后的语句,重新计算目标数据要插入的位置, 
										  //并采用线性探测方式寻找到新位置进行插入

										  //2:如果重新创建_table,然后将旧表的数据放入到新表的化,因为新表的长度
										 //不同,原来在旧表中冲突的数据在新表中就不冲突了,原来在旧表中不冲突的位置
										 //反而会在星表中冲突,这样每次将旧表数据放入到新表中都要重新计算对应位置,
										 //这样反而就会显得很麻烦.
				}
			}
			_table.swap(newTable._table);  //现代写法.

		}
		size_t start = hash(kv.first) % _table.size(); //必须%size(),因为在顺序表中[]只能在size范围内访问,如果%capacity,
												 //那么访问时则在capacity范围访问,这样有可能[]时大于size范围造成断言错误.

		size_t hashi = start;

		size_t i = 0;


		while ( _table[hashi]._state == EXIST )   //线性探测,如果这个位置存在,那么就需要继续从这个位置遍历. 如果这个位置                                         //为空或者删除状态,那么就可以将数据插入了.
		{
			++i;                              
			
			hashi = start + i * i;

			hashi %= _table.size();          //如果等于size的位置,就说明从这个位置开始找到后面还没有找到,此时不能超过size范围,需要
											  //将hashi回到起点重新开始寻找,直到找到空位置.
		}
		_table[hashi]._kv = kv;              //目标位置的存储对象的_kv就等于要插入kv的键值.
		_table[hashi]._state = EXIST;        //将目标位置存储对象的状态修改为EXIST.
		++_size;
		return true;
	}

	HashData<K,V>* Find(const K& key)                  
	{
		Hash hash;
		if (_table.size() == 0)                //如果表为空,就会发发生除零错误,所以必须要先判断.
		{
			return nullptr;
		}
		size_t hashi = hash(key) % _table.size();   //左边是无符号整数,右边是有符号整数,相除时右边的类型会发生整型提升,提升为无符号整数,然后算出的这个位置自然就为4了.
		                                       //所以就不需要关注负数了,因为它能存入这个表中.


		size_t start = hashi;

		while (_table[hashi]._state != EMPTY )  //哈希映射的那个位置不为空就继续查找.
		{
			if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)  //当映射的那个位置不为空并且状态也不能是删除，_kv.first等于那个值就找到了．
			{
				return &_table[hashi];
			}
			++hashi;                                 //哈希映射的那个位置不为空就继续查找.
			hashi %= _table.size();              //归零,防止越界.
			
			if (hashi == start)
			{
				break;
			}
		}
		return nullptr;
		
	}
	

bool Erase(const K& key)                  //删除一个值,直接改哈希表中存储对应key地Data对象中的状态就行了.
	{
		HashData<K,V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_size;
			return true;
		}
		return false;
	}
void Print()
{
	for (int i = 0; i < _table.size(); ++i)
	{
		if (_table[i]._state == EXIST)
		{
			cout <<_table[i]._kv.first << "->" << _table[i]._kv.second<<" ";
		}
		
	}
	
}
private:

	vector<HashData<K, V>> _table;
	size_t _size;    //记录有效数据个数
};

到了这里，关于哈希表(底层结构剖析-- 上)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！