当前位置： 首页 > article >正文

[c++高阶]哈希的深度解析

article 2024/11/8 19:22:11

1.前言

终于来到学到哈希了，尽管有一些小伙伴没有用过哈希表，但是应该听过在做题过程中时，这道题无脑用哈希把！！！

本章重点：

着重讲解哈希是什么，哈希冲突，解决哈希冲突的方法以及哈希表和哈希桶的模拟实现

2.什么是哈希

  哈希（Hash）是一个广泛的概念，其中包括哈希表、哈希冲突、哈希函数等，核心为 元素（键值） 与 存储位置（哈希值） 之间的映射关系，哈希值 可以通过各种哈希函数进行计算，需要尽量确保 “唯一性”，避免冲突。

例：

 上述例子可以发现，不同的key值通过哈希函数，映射到了不同的位置

2.1 哈希的由来

 在学习过【数据结构】后我们都知道，数组 和 链表 都有它们各自的特点：

  • 数组特点：访问(寻址)速度较快的、但插入、删除操作较慢；
  • 链表特点：访问(寻址)速度较慢的、但插入、删除操作很快； 

所以，有些大牛就想着能不能结合这数组、链表的优点，造出一个 访问(寻址)速度较快的、插入、删除操作也很快 的数据结构，后面就造出来一个 【哈希表】。 能想出这个的确实是个大神，不得不服。

2.2 哈希思想

其实哈希思想就是一个映射思想， 通过哈希函数把不同的key值映射到不同的位置上。当查找的时候也是通过找出映射在哪个位置，来找到该值。

下面给出官方说法：

哈希（Hash） 是一种 映射 思想，规定存在一个唯一的 哈希值 与 键值 之前建立 映射 关系，由这种思想而构成的数据结构称为 哈希表（散列表）  

 

举例说明： 

通过哈希函数建立的映射关系，可以把数据集放在不同的位置，从而使其查找和删除时间复杂度是O（1）。

但是这样映射也会出现问题，如果插入66的话应该怎么办呢？此时下标6所在的位置已经有值了，如果在把66放过去，那么就会出现问题。--这就是著名的哈希冲突

 2.3 哈希表的概述

 在顺序表和二叉树中，如果你想找一个值，那么时间复杂度是O（N）和O（logN）。这是因为在搜索的过程中经过了很多次数的比较。

 那么最理想的搜索方式就是：可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为 O(1)。

如果构造一种存储结构，能通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一种映射的关系，那么在查找时通过该函数先找到映射值，然后通过映射值可以很快找到该元素。 

 该方式即为哈希（散列）方法， 哈希方法中使用的 转换函数 称为 哈希（散列）函数，构造出来的结构称为 哈希表（散列表）。 

3.哈希冲突

不同关键字 key通过相同 哈希函数 计算出 相同的哈希地址，该种现象称为 哈希冲突 或 哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素称为 同义词。 

如果此时再将元素 66 插入到上面的哈希表，因为元素 66 通过该哈希函数计算得到的哈希地址与元素 6 相同，都是下标为 6 的位置，那么就会产生哈希冲突。

4.哈希函数

引起哈希冲突的原因之一可能就是因为哈希函数设计的不够合理，导致发生了冲突。

 因此，下面给出官方的哈希函数的设计准则：

  • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
  • 哈希函数计算出来的地址能均匀分布在整个空间中。
  • 哈希函数应该比较简单。

常见的哈希函数

直接定址法（不推荐）

函数原型：HashI = A * key + B 

  • 优点：简单、均匀
  • 缺点：需要提前知道键值的分布情况
  • 适用场景：范围比较集中，每个数据分配一个唯一位置

除留余数法（推荐使用）

假设 哈希表 的大小为 m 

函数原型：HashI = key % p (p < m) 一般p会选择容量的大小

  • 优点：简单易用，性能均衡
  • 缺点：容易出现哈希冲突，需要借助特定方法解决
  • 适用场景：范围不集中，分布分散的数据

平方取中法（了解）

函数原型：HashI = mid(key * key) 

  • 适用场景：不知道键值的分布，而位数又不是很大的情况

假设键值为 1234，对其进行平方后得到 1522756，取其中间的三位数 227 作为 哈希值

 5.哈希冲突的解决办法

其实，不管你哈希函数怎么设计，哪怕你是天才中的天才，设计出了一个很吊的函数，你都无法避免的出现哈希冲突。因此为了解决这个问题，提出了两种方法解决：闭散列法和开散列法

5.1 闭散列法（开放定址法）

闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的 下一个 空位置中去。

 那么问题就演变成了如何寻找下一个空位置了。如线性探测(一个一个往后找)、二次探测（以2^i次方往后找）。

这里就只介绍线性探测了

44插入之后， 发现应该被映射的位置已经有值了，那么就一直线性的遍历往后找，依次找到空位置为止。

但是我们会发现在插入44的时候，遇见了四次哈希冲突，这也表明了，随着数据的增多，哈希冲突的次数也可能会变多。

我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。因此，哈希表当中引入了负载因子（载荷因子）： 

  • 散列表的载荷因子定义为：α＝填入表中的元素个数／散列表的长度
  • 负载因子越大，产出冲突的概率越高，增删查改的效率越低。
  • 负载因子越小，产出冲突的概率越低，增删查改的效率越高。

 假设我们现在将哈希表的大小改为 20，再把上面的数据重新插入，虽然44依然发生了哈希冲突，但是如果我们的值改成了插入34呢？ 34在哈希表的大小为10的时候是会发生四次哈希冲突的，而34在哈希表为20的时候，就不会发生哈希冲突了

需要明确的一点是，你利用负载因子来进行扩容，并不是完全解决了哈希冲突的问题，只是让哈希冲突的概率变小。

 比如当你容量为20的时候，你只插入三个值，那么你发生哈希冲突的概率就大大的减下了，但是这样对于空间的利用率又不高了。又有点浪费空间的意思，所以对于开放定址法来讲：

荷载因子是特别重要因素，应严格限制在 0.7~0.8 以下。超过 0.8 时，查表时的 CPU 缓存不命中（cache missing）按照指数曲线上升。

哈希表线性探测的删除操作：

哈希表中的元素如果只是原生数据类型,那么我们将4删除后,再去查找4肯定是找
不到的,但是此时去查找44也会找不到,因为44本来应该映射到4位置,但是由于哈希
冲突跑到了8位置,并且我们并不知道它在哪个位置,所以查找时会找不到!

解决方案：

存储数据不单单存储原生类型，再给每一个位置加上一个状态枚举，分别代表此位置是空,被删除还是有数（如果是空，就表示这个位置没有数，如果是被删除的状态，就表示这个位置之前有值，但是被删掉了）

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State {EMPTY, EXIST, DELETE};

总结：

  • 线性探测优点：实现非常简单，
  • 线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据 堆积，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
  • 并且闭散列的空间利用率也很低

5.2 哈希表的模拟实现 

先写一个框架：

//哈希表
enum State
{
	EXSIT,
	DELETE,
	EMPTY,
};

template <class K,class V>
struct HashData
{
	State _state;
	pair<K, V> _kv;
	HashData(const pair<K,V>& kv=make_pair(0,0))
		:_kv(kv)
		,_state(EMPTY)
	{}
};

template <class K,class V>
class HashTable
{
	typedef HashData<K,V> HD;
public:
private:
	vector<HD> _table;//数组中存储HashData封装的数据
	size_t _size = 0;//记录有效的数据
};

 然后再进行插入删除查找函数的实现

bool Insert(const pair<K, V>& kv)
{
	if (_table.capacity() == 0 || 10 * _size / _table.capacity() >= 7)
	{
		size_t newcapacity = _table.capacity() == 0 ? 10 : 2 * _table.capacity();
		HashTable<K, V> newHT;
		newHT._table.resize(newcapacity);//新扩容的全部填充0
		for (auto e : _table)
		{
			newHT.Insert(e._kv);
		}
		_table = newHT._table;
	}
	//到这里开始插入
	int index = kv.first % _table.capacity();
	int start = index;
	//线性探测
	while (_table[index]._state == EXSIT)
	{
		index++;
		index %= _table.capacity();//过大会重新回到起点
		if (index == start)
			return false;//里面都没有空间了--虽然这种情况不可能发生，但是还是讨论一下
	}
	_table[index]._kv = kv;
	_table[index]._state = EXSIT;
	_size++;
	return true;
}
bool Erase(const K& key)
{
	HashData<K, V>* pos = Find(key);
	if (pos)
	{
		pos->_state = DELETE;
		--_size;
		return true;
	}
	return false;
}
HD* Find(const K& key)
{
	if (_size == 0) return nullptr;
	int index = key % _table.capacity();
	int start = index;
	while (_table[start]._state != EMPTY)
	{
		if (_table[start]._kv.first == key && _table[start]._state != DELETE)
			return &_table[start];
		start++;
		start %= _table.capacity();
		if (start == index)//走了一圈都没找到
			break;
	}
	return nullptr;
}
  1.  这里查找返回指针的意义是为了告诉外界我找到了，如果没找到的话那么就是返回的是空值。
  2. 上述扩容在负载因子部分已经详细进行了解释

5.2 开散列 （链地址法）

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

 举个例子：

现在有这样一组数据集合 {40, 5, 10, 21, 66, 55, 50, 18, 27} 我们用除留余数法将它们插入到表长为 10 的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：

 

  • 【闭散列】解决哈希冲突，采用的是一种报复的方式，“我的位置被占用了我就去占用其他位置”。而【开散列】解决哈希冲突，采用的是一种乐观的方式，“虽然我的位置被占用了，但是没关系，我可以挂在这个位置下面”。 

与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。 

  • 闭散列的开放定址法，负载因子不能超过 1，一般建议控制在 0.0 ~ 0.7 之间。
  • 开散列的哈希桶，负载因子可以超过 1，但是最好不要超过1，一般建议控制在 0.0 ~ 1.0 之间。

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点： 

  • 哈希桶的负载因子可以更大，空间利用率高。
  • 哈希桶在极端情况下还有可用的解决方案。

哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成 O ( N ) 

 

那这个时候我们就可以不采用挂单链表了，而采用的是挂红黑树，把红黑树的根节点存储在哈希桶中。

  • 在这种情况下，就算有十亿个元素全部冲突到一个哈希桶中，我们也只需要在这个哈希桶中查找 30 次左右，这就是所谓的 桶里种树 。

 当然尽量还是不要出现这种情况，全部挂接在一个桶里面。因此当插入的数据过多时，那么就需要重新进行扩容，一旦进行了扩容，在同一个桶里面的值就可能会被映射到其他的地方去，可以避免出现这种极端情况。

5.4 哈希桶的模拟实现

框架：

template <class K,class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;
	HashNode(const pair<K, V>& kv = { 0,0 })
		:_kv(kv)
		, _next(nullptr)
	{}
};

template <class K,class V>
class Hashtable1
{
	typedef HashNode<K, V> Node;
private:
	vector<Node*> _table;
	size_t _size = 0;
};

由于哈希桶里面存储 的是单链表，所以在vector里面放的应该是节点的指针。

 插入删除查找等函数的实现

	bool Insert(const pair<K, V>& kv)
	{
		if (_table.capacity() == 0 || 10 * _size / _table.capacity() == 1)
		{
			//扩容
			size_t newcapacity = _table.capacity() == 0 ? 10 : 2 * _table.capacity();
			Hashtable1<K,V> newHt;
			newHt._table.resize(newcapacity, nullptr);
			//把原来的值头插进新的容器
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					//判断他应该放在新表的那个位置
					size_t hashi = cur->_kv.first % newcapacity;
					cur->_next = newHt._table[hashi];
					newHt._table[hashi] = cur;
					cur = next;
				}
			}
			_table = newHt._table;
		}
		//开始插入新的
		size_t hashi = kv.first % _table.capacity();
		HashNode<K, V>* newnode = new Node(kv);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		++_size;
		return true;
	}
	Node* Find(const K& key)
	{
		if (_table.capacity() == 0)
			return nullptr;
		size_t hashi = key % _table.capacity();
		Node* cur = _table[hashi];
		while (cur)//走到空还没有就是没用此数据
		{
			if (cur->_kv.first == key)
				return cur;
			cur = cur->_next;
		}
		return nullptr;
	}
	bool Erase(const pair<K, V>& kv)
	{
		//先找一下，看看能不能找到
		Node* ret = Find(kv.first);
		if (ret == nullptr) return false;
		size_t hashi = kv.first % _table.capacity();
		Node* cur = _table[hashi];
		if (cur->_kv.first == kv.first)
		{
			//表示删除的是第一个结点
			_table[hashi] = cur->_next;
			delete cur;
			cur = nullptr;
			_size--;
			return true;
		}
		else
		{
			//删除的是其他节点，那么需要kv在的那个节点的前一个位置和后一个位置
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first != kv.first)
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			//到这找到了
			prev->_next = cur->_next;
			delete cur;
			cur = nullptr;
			_size--;
			return true;
		}
	}

对代码的关键解释都是注释中，有疑问的可以后台tt我。

 6.总结与拓展

 哈希表总结：

哈希表的学习关键就是抓住：哈希表，哈希函数，哈希冲突三个概念。

哈希表：简单理解，就是在一个表中，key值通过哈希函数映射了一个value值在表里面，通过映射值来找key值

哈希函数：将哈希表中元素的key映射为元素存储位置的函数。 

哈希冲突：就是一个映射值可能会对应多个key值，这就导致存储的冲突了。

常用的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。本文只介绍了前三种方法

 常用的哈希冲突的解决方法有两种：开放地址法 和 链地址法。 

 拓展：

我们会发现一个问题,不管是哈希表还是哈希桶,都用到了cur.first模上一个数,但是如果cur.first不是整型不能取模怎么办?(如字符串)

为了解决上述问题：

这时需要在哈希类中再传入一个模板参数,此模板参数为仿函数,只需将写好
的仿函数传入即可进行取模,比如string仿函数可以这样写:

template<>
struct HashFunc<string>
{
	//BKDR算法:将字符串转换为整数
	size_t operator()(const string& str)
	{
		size_t sum = 0;
		for (auto ch : str)
		{
			sum *= 131;
			sum += (size_t)ch;
		}

		return sum;//将字符的asc码全部加起来再返回
	}
};

 更多的字符串哈希算法可以参考以下文章：

经典字符串hash函数介绍及性能比较_hash的性能比较-CSDN博客


http://www.kler.cn/a/384789.html

相关文章：

  • qt QErrorMessage详解
  • Rust闭包（能够捕获周围作用域变量的匿名函数，广泛应用于迭代、过滤和映射）闭包变量三种捕获方式：通过引用（不可变引用）、通过可变引用和通过值（取得所有权）
  • SpringBoot监控
  • JAVA笔记 | ResponseBodyEmitter等异步流式接口快速学习
  • vscode翻译插件
  • Python 中的字符串匹配算法
  • Adaptive AUTOSAR ——Cryptography （在自适应AUTOSAR中的应用：概念、功能与实现）
  • 管理 Elasticsearch 变得更容易了，非常容易！
  • 第二十六章 Vue之在当前组件范围内获取dom元素和组件实例
  • vue3 css的样式如果background没有,如何覆盖有background的样式
  • 青少年编程与数学 02-003 Go语言网络编程 08课题、Session
  • SpringMVC课时2
  • PHP网络爬虫常见的反爬策略
  • App渠道来源追踪方案全面分析（iOS/Android/鸿蒙）
  • 『Django』APIView基于类的用法
  • 创建线程时传递参数给线程
  • 基于51单片机超声波测距
  • Flutter 鸿蒙next 中使用 MobX 进行状态管理
  • vue3学习---案例实现学习
  • Ubuntu 22.04.5 LTS配置 bond
  • 删除 git submodule
  • 力扣 -- 滑动窗口
  • Pytorch训练时报nan
  • laravel chunkById 分块查询 使用时的问题
  • Spring Cloud Bus快速入门Demo
  • 第九周预习报告