【C++】 哈希

文章目录

• • 1. 哈希概念
  • 2. 哈希表
  • • 直接定址法(常用)
    • 除留余数法(常用)
    • 解决哈希冲突方法1 ——闭散列
    • 解决哈希冲突方法2 ——开散列
  • 3. 闭散列的实现
  • • 如何处理删除数据？
    • 定义数据结构
    • insert
    • • len为 _tables.size() 还是 _tables.capacity()？
      • 线性探测
      • 负载因子
      • 扩容
    • Find
    • Erase
    • 完整代码
  • 4. 开散列的实现
  • • 定义数据结构结构
    • insert
    • • 扩容
    • Find
    • Erase
    • 针对传入string的情况
    • 使用特化避免传入仿函数
    • 完整代码

1. 哈希概念

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

为哈希表(Hash Table)(或者称散列表)

2. 哈希表

key跟存储位置建立映射(关联)关系

直接定址法(常用)

每一个值都有一个唯一位置

特点：适用于范围比较集中的数据

除留余数法(常用)

特点：范围不集中，分布分散

当前数据非常分散，虽然最大值已经达到1000，但是空间使用效率太低，所以不应该开1000个空间储存

所以想要把分散的数据，映射到固定的空间中

key值跟存储位置的关系，是模出来的

如55与15取模后的值都为5

解决哈希冲突方法1 ——闭散列

闭散列又称 开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明哈希表中必然还有空位置，则可以把key存放到冲突位置中的下一个位置去

如何寻找下一个位置？

线性探测

若有两个取模相同的值，则将先进来的占住当前取模位置，后进来的向后探测，若有空位置则放入

因为是先将2取模，所以2占住了映射2的位置，而当将102取模时，由于位置被2占住，所以向后寻找空位置，即在映射4的位置

hashi=key%len

i从0开始，不断增加直到找到一个没有占住的位置，超过该表的长度

解决哈希冲突方法2 ——开散列

开散列法又称为链地址法，对关键码集合用散列函数计算散列地址，具有相同地址码归于同一个子集合

每一个子集称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头节点存储在哈希表中

相比于闭散列，哈希冲突减少了

3. 闭散列的实现

当使用除留余数法解决问题时

不同的值映射在相同的位置，即哈希冲突/哈希碰撞

使用线性探测处理，依次找后面位置存储 hashi + i (1，2，3，4)

如何处理删除数据？

假设要删除33，因为33取余后为3，所以先去位置为3的地方去找，没有找到，则继续向后寻找

寻找到空才结束

假设把33直接删除，当再次查找13时，由于提前遇到空，则直接结束

设置三种状态： 空、存在、删除

定义数据结构

需要使用枚举来表示三种状态 删除 存在 空

表示状态的state 也应该默认设为空，不然有可能造成 映射位置 没有数据但是 状态为存在的情况

insert

hashi=key%len

若当前位置已经被占住，hashi+i (i>=0)

len为 _tables.size() 还是 _tables.capacity()？

假设将hashi的大小设为capacity

在vector中 operator[] 会做越界检查，下标是否小于size

无法访问10后面的数据的，会造成越界

len为_tables.size()

线性探测

若从3位置开始，则+7时，绕过去导致达到0位置处，所以需要将index%size，从而达到0位置处

若当前位置存在，则继续向后走，若遇到空或者删除状态，则停下来填入数据，并将其设置为存在状态，存储的数据个数+1

负载因子

哈希表冲突越多，效率越低

若表中位置都满了，就需要扩容 ，提出负载因子的概念

负载因子 = 填入表的元素个数 / 表的长度

表示 表储存数量的百分比

填入表的元素个数 越大，表示冲突的可能性越大，

所以在开放定址法时，应该控制在0.7-0.8以下，超过就会扩容

扩容

需要注意的是 整形 除以整形 不存在小数

可以选择将其分子扩大10倍，则除出来的结果 为整数

表为空没有处理，无法扩容

但是增加的capacity的空间是不能被访问到的

size刚开始时为10，通过扩容size变为20

说明当前扩容方法是不可以的

开辟一块新的空间，将原来空间内的数据都重新计算在新空间的映射位置

原来不冲突的值可能冲突了

创建newht，将其中的_tables的size进行扩容

交换旧表与newht的_tables ，以达到更新数据的目的

Find

若当前位置的状态为存在或者删除，则继续找， 遇见空 就结束

若在循环中找到了，则返回对应位置的地址，若没找到则返回nullptr

虽然把要删除的数据的状态改为DELETE，但是数据本身还是在的

所以Find还是可以找到的

所以只有当前位置的数据状态为EXIST时并且当前位置的数据等于key值，才返回

Erase

通过Find寻找要删除的数据，若找到了，则将其状态改为DELETE 将其数据个数减1 并返回true ，若没有找到，则返回false

完整代码

#pragma once

#include
#include
using namespace std;
enum State //表示三种状态
{
	EMPTY, //空
	EXIST,//存在
	DELETE//删除

};

template
struct HashData
{
	pair_kv;//对应的KV 数据
	State _state=EMPTY;//表示状态
};

template
class HashTable
{
public:
	bool insert(const pair& kv) //插入
	{
		//若数据已经有了，就不要插入了
		if (Find(kv.first))
		{
			return false;
		}
		
		//负载因子超过0.7就扩容
		if (_tables.size()==0 || _n * 10 / _tables.size() >= 7)
		{
			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;	
			
			HashTable newht;
			newht._tables.resize(newsize); //将newht中的_tables 进行扩容
			//遍历旧表，重新映射到新表
			for (auto & data : _tables)
			{
				newht.insert(data._kv);//将旧表数据进行插入newht中
			}

			//将_tables 更新为newht中的数据
			_tables.swap(newht._tables);
		}

		 
		//key值%当前表的长度
		size_t hashi = kv.first % _tables.size();
		
		//线性探测
		size_t i = 1;
		size_t index = hashi;
		while (_tables[index]._state == EXIST)//若当前位置值存在，则继续往后走
		{
			//加i是因为有可能后面的位置被占用，则需要找到一个没有被占用的位置
			index = hashi + i;

			//为了针对绕过去的情况
			index %= _tables.size();
			i++;//i的值从1开始 依次递增
		}
		_tables[index]._kv = kv;//填入数据
		_tables[index]._state = EXIST;//设置为存在状态
		_n++;
		return true;
	}

	HashData* Find(const K& key)//查找
	{

		if (_tables.size() == 0)
		{
			return false;
		}

		size_t hashi = key % _tables.size();

		//线性探测
		size_t i = 1;
		size_t index = hashi;
		while (_tables[index]._state != EMPTY)
		{
			if (_tables[index]._state==EXIST&&_tables[index]._kv.first == key)//找到
			{
				return   &_tables[index];
			}

			//加i是因为有可能后面的位置被占用，则需要找到一个没有被占用的位置
			index = hashi + i;

			index %= _tables.size();
			i++;//i的值从1开始 依次递增
			
			//表里全是删除/存在状态的数据
			if (index == hashi)
			{
				break;
			}
		}
		return nullptr;	
	}
	 
	bool Erase(const K& key)
	{
		HashData* ret = Find(key);
		if (ret)
		{
			ret->_state == DELETE;
			--_n;
			return true;
		}
		else
		{
			return false;
		}
	}
	 
private:
	vector<HashData> _tables;
	size_t _n = 0; // 存储的数据个数
		
}; 

void hashtest()
{
	int a[] = { 3,33,2,13,5,12,1002 };
	HashTablev;
	for (auto e : a)
	{
		v.insert(make_pair(e, e));
	}
}

4. 开散列的实现

定义数据结构结构

整体实现都是放入 命名空间 哈希桶HashBucket中的

指向下一个节点的next，以及用于记录数据的kv

insert

在同一个桶中并没有谁先谁后的问题

创建一个新节点newnode，使newnode的next连接到当前映射位置

再让newnode成为头节点

扩容

负载因子越大，冲突的概率越高，查找效率越低，空间利用率越高

负载因子越小，冲突的概率越低，查找效率越高，空间利用率越低

原表的节点重新计算位置，移动到新表中

所以 取模 来到对应2位置 处，与2形成链式结构

遍历旧表中的数据，若数据为空，就往后遍历

若数据不为空，则将其移动到新表中 ，需要进行头插

Find

使用cur记录当前映射位置，遍历当前位置的单链表 ，查询是否有key值的存在，

若有则返回cur，若没有则返回空

Erase

要删除单链表，还需要有它的前一个节点

但是若删除的节点作为头节点，没有前一个节点

假设要删除3，则 需让表的位置指向要删除节点的下一个

假设 要删除12，则需找到删除节点的前一个节点，使其指向要删除节点达到后一个节点

针对传入string的情况

若为string类型，则使用insert无法计算对应的hashi值

所以需要添加 仿函数

加入 模板参数 hash

仿函数的缺省值是默认使用整形转化的，

使用Hashstr，传过去作为Hash 即可调用string

但是这中比较字符串转化整形的方法，是有一定的缺陷的

两个字符串是不同的，只不过ASCII值相加是相同的，会导致在相同的位置造成冲突

两个不同的字符串 ，对应输出的值是不同的，就不会造成位置冲突了

使用特化避免传入仿函数

在unordered_map 中并没有使用仿函数，是因为默认支持string作为key，对仿函数的类进行特化

若为普通类型 (int) 就进入 HashFunc

若为string类型，则调用对HashFunc的特化

再次使用 HashTable时不用传入仿函数也能调用string 类型

完整代码

#include
#include
using namespace std;
namespace HashBucket
{
	template
	struct HashNode
	{
		HashNode* _next;
		pair _kv;
		HashNode(const pair& kv)//构造
			:_next(nullptr)
			, _kv(kv)
		{
		}
	};

	template
	struct HashFunc //仿函数
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	//特化
	template
	struct HashFunc //仿函数
	{
		//将字符串转化为整形
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
				hash *= 31;//用上次的结果乘以31
			}
			return hash;
		}

	};

	//给一个默认缺省值  使整形可以直接被调用
	template<class K, class V, class Hash = HashFunc>
	class HashTable
	{
		typedef HashNode Node;
	public:

		~HashTable()//析构
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				cur = nullptr;
			}

		}

		Node* Find(const K& key)//查找
		{
			Hash hash;
			//若表刚开始为空
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}


		bool Erase(const K& key)//删除
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;//用于记录前一个节点
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)//要删除节点为头节点时
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
		bool insert(const pair& kv)//插入
		{

			Hash  hash;
			//负载因子==1时扩容
			if (_n == _tables.size())
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vectornewtables(newsize, nullptr);//创建 newsize个数据，每个数据都为空

				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;//保存下一个旧表节点
						size_t hashi = hash(cur->_kv.first) % newtables.size();
						//将旧表节点头插到新表节点中
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
				}
				_tables.swap(newtables);
			}


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

			//头插
			Node* newnode = new Node(kv);//新建节点
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}



	private:
		vector _tables;  //指针数组
		size_t _n;//存储数据有效个数

	};
	


	void Hashtest2()
	{
		HashTable v;
		v.insert(make_pair("sort", "排序"));
		v.insert(make_pair("left", "左边"));
		v.insert(make_pair("right", "右边"));
	}



}