【C++】哈希的概念与实现

1.哈希概念

通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，可以不经过任何比较，一次直接从表中得到要搜索的元素。

当向该结构中：

• 插入元素：

  根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

• 搜索元素：

  对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

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

  与其它搜索方法比较：

  顺序查找时间复杂度为O(N)；二分查找为O( l o g 2 N log_2 N log2​N)但须先排成一个有序序列会有一定性能损耗，同时在中间插入删除时间复杂度为O(N)；平衡树中时间复杂度即为树的高度为O( l o g 2 N log_2 N log2​N)

  2.哈希冲突

  不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

  例如6和66，%10都等于6，映射到的地址相同造成冲突。

  3.哈希函数

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

  哈希函数设计原则：

  哈希函数设计原则：

  1. 哈希函数应该尽可能简单
  2. 哈希函数的值域必须在哈希表格的范围之内
  3. 哈希函数的值域应该尽可能均匀分布，即取每个位置应该是等概率的

  常见哈希函数：

  1. 直接定址法–(常用)

     取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

     优点：简单、均匀

     缺点：需要事先知道关键字的分布情况

     使用场景：适合查找比较小且连续的情况

  2. 除留余数法–(常用)

     设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p EXIST, EMPTY, DELETE }; template pair private: vector //检查扩容,判断是否超出载荷因子 //if((double)_n/_table.size()=0.7)//强制类型转换情况 if (10 * _n / _table.size() >= 7)//都转化为int操作 { //遍历旧表，重新映射到新表 size_t newsize = _table.size() * 2; HashTable newht; newht._table.resize(newsize); //遍历旧表数据插入到新表 for (size_t i = 0; i

     仿函数部分：

     

     因为Insert的参数是const的_kv，无法进行修改，这时候就需要仿函数(哈希函数)的帮忙，自己控制比较修改方式，将const的键值转化为无符号整型进行取模运算。

     运用模板特化进行对string类型键值到整型的转换，采取了BKRD字符串哈希算法来进行转化减少哈希冲突，还有很多种方法可以查文献

     检查扩容部分：

     扩容后原来冲突的现在不一定冲突了，原来不冲突的现在可能冲突，因为槽位更多了向末尾查找比往前查找的概念更大了，所以冲突关系大概率发生变化。

     >采取创建新的哈希表对象来接受原对象的映射，在调用vector的swap函数交换回旧表，新表作为局部对象在扩容操作完后将自动销毁。

     为什么不是直接创建一个新的动态数组 vector _newtable来帮助完成扩容操作呢？

     因为哈希表对象能保证封装信和内部状态的一致性，因为哈希表内不止有动态数组，还有哈希函数，_n等，可以自动管理载荷因子维护性能。若直接创建动态数组需要重新手动实现哈希逻辑

     线性探测部分：

     通过HashFunc hf;定义仿函数对象，重载了operator()，可以像普通函数一样调用。

     进行取模运算，找空位的循环条件是状态为存在就更新hashi下标索引，循环内再进行取模运算，递增 hashi 时，可能会超出哈希表的大小。取模操作可以将索引“环绕”到哈希表的起始位置，继续从头查找。确保索引在有效范围内。

     找到空位后更新状态

     载荷因子：

     

     • 查找：

       HashData* 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*)&_table[hashi];
       		}
       		hashi++;
       		hashi %= _table.size();
       	}
       	return nullptr;
       }
       

       返回值key值不可修改，利用线性探测实现查找，当前槽位不是空的，就继续查找，然后检查当前槽位的状态是否为 EXIST，并且槽位中的键值 _kv.first 是否与目标键值 key 相等，匹配返回该槽位指针，否则返回空。

       注意返回值要强转指针类型

       • 删除：

         采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

         bool Erase(const K& key)
         {
         	HashData* ret = Find(key);
         	if (ret)
         	{
         		ret->_state = EMPTY;
         		_n--;
         		return true;
         	}
         	return false;
         }
         

         • 缺点

           一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。最大的缺陷就是空间利用率比较低

           二次探测

           线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： H i H_i Hi​ = ( H 0 H_0 H0​ + i 2 i^2 i2 )% m, 或者： H i H_i Hi​ = ( H 0 H_0 H0​ - i 2 i^2 i2 )% m。其中：i = 1,2,3…， H 0 H_0 H0​是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

           探测次数：

           元素1：探测1次

           元素2：探测2次

           元素3：探测3次

           元素n：探测n次

           故要将n个元素存入哈希表中，总共需要探测：1+2+3+…+n = n*(n+1)/2

           4.3开散列

           • 概念：

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

             每个哈希桶中放的都是发生哈希冲突的元素。

             哈希桶扩容时不适合复用insert涉及节点的开辟和销毁

             哈希桶的实现

             基本结构

             namespace hash_bucket
             {
             	template
             	struct HashNode
             	{
             		pair _kv;
             		HashNode* next;
             		HashNode(const pair& _kv)
             			:_kv(kv)
             			, newxt(nullptr)
             		{ }
             	};
             	template
             	class HashTable
             	{
             		typedef HashNode Node;
             	private:
             		vector _table;//指针数组
             		size_t _n = 0;
             	};
             

             1.定义在哈希桶命名空间内，方便调用区分

             2.节点的定义与哈希表相比不需要表明状态，替换成一个next指针，能直接完成插入，删除操作

             3。vector _table;定义指针数组，vector可自动扩容，每个槽位存储一个指向链表头节点的指针，每个链表存储多个具有相同哈希值的元素

             析构函数

             ~HashTable()
             {
             	for (size_t i = 0; i next;
             			delete cur;
             			cur = next;
             		}
             		_table[i] = nullptr;
             	}
             }
             

             vector _table中vector 是一个动态数组，当它超出作用域或被销毁时，其内部管理的内存空间会自动被释放。

             Node* 是指向堆上分配的 Node 对象的指针，是内置类型，不会自动调用析构函数，需要手动释放

             代码逻辑：

             1.创建cur来遍历每个槽位头节点所指向的链表，循环中要提前保存next指针，然后销毁cur中对象并释放内存，更新cur，将 _table[i] 指针置空，确保 _table[i] 不再指向已经被释放的内存

             插入

             bool Insert(const pair& kv)
             {
             	if (Find(kv.first))
             	{
             		return false;
             	}
             	HashFunc hf;
             	//检查扩容，载荷因子到1就扩容
             	if (_n == _table.size())
             	{
             		size_t newsize = _table.size() * 2;
             		vector newtable;
             		newtable.resize(newsize, nullptr);
             		//遍历旧表，将节点转移挂到新表
             		for (size_t i = 0; i _kv.first) % newsize;
             				Node* next = cur->_next;
             				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;
             }
             

             思路解析：

             1.首先判断要插入节点是否存在

             2.检查扩容：

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

             具体操作：

             a：与闭散列哈希表相比不需要建立一张新表来接收旧表，直接建立一个新动态数组即可，因为哈希桶中不需要维护状态，链表可以直接完成插入删除操作。

             b：计算新容量，先计算hashi索引，循环遍历旧表节点到新表，缓解原表哈希冲突，每遍历完一个哈希桶，原表当前槽位记得置空，方便后续与新表交换

             3.插入新节点：

             计算hashi索引，然后new一个新节点，进行头插操作，将新节点的_next指针指向当前槽位中链表头节点，然后将头节点赋值为新节点，完成。更新当前元素有效个数。

             查找

             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;
             }
             

             先计算hashi索引，在当前哈希桶中遍历链表寻找，找到返回当前节点，否则返回空。

             删除

             bool Erase(const K& key)
             {
             	HashFunc hf;
             	size_t hashi = hf(key) % _table.size();
             	Node* cur = _table[hashi];
             	Node* prev = nullptr;
             	while (cur)
             	{
             		if (cur->_kv.first == key)
             		{
             			//判断要删除节点为头节点情况
             			if (prev == nullptr)
             			{
             				_table[hashi] = cur->_next;
             			}
             			else
             			{
             				prev = cur->_next;
             			}
             			--_n;
             			delete cur;
             			return true;
             		}
             		//更新节点继续遍历
             		prev = cur;
             		cur = cur->_next;
             	}
             	return false;
             }
             

             1.提前保存删除节点的上一个节点prev，方便重新链接

             2.注意判断删除节点为头节点和链表中间节点的情况

             3.更新链接关系后删除释放当前cur