哈希概念 | 哈希函数 | 哈希冲突 | 哈希桶实现 | 哈希线性探测代码实现 | 闭散列 | 开散列 | 字符串哈希算法

文章目录

        • 1.哈希概念
        • 2.哈希冲突
        • 3.解决哈希冲突
          • 3.1.闭散列
          • 3.2.开散列
        • 4.字符串哈希算法

1.哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。如果一个顺序结构，有N个数据，数据之间没有顺序，暴力查找时间复杂度是O（N），但如果数据之间是有序的，就可以使用二分查找能快速的找到查找的值，但是，顺序结构保证有序来存储数据，插入和删除的代价太大！
在这里插入图片描述

对应平衡树来说，查找的时间复杂度O（log2(N)）很优秀！

在这里插入图片描述

但更理想（高效）的方法是：将存储的值和存储的位置一一对应，那么一次就能找到要查找的元素；哈希(散列)方法：通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系；构造出来的结构称为哈希表(Hash Table)(或者称散列表)

在这里插入图片描述

这样的哈希函数称为 除留余数法；常用的还有，直接定址法。

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B，在关键字分分布集中的情况的下使用比较好，但是，如果存储的key范围分散如：arr[] = {1,111,999}要存储这些数据就很麻烦！

我们来看一个直接地址法的例子：字符串中第一个只出现一次字符

题目描述：给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。如：输入: s = “leetcode” 输出: 0

题目提示：s 只包含小写字母，说明关键字集中。

class Solution {
public:
    int firstUniqChar(string s) 
    {
        int temp[256] = {0};

        for(char ch : s)
        {
            temp[ch]++;
        }
        for(int i = 0; i < s.size();i++)
        {
            if(temp[s[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }
};
2.哈希冲突

在这里插入图片描述

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

3.解决哈希冲突
3.1.闭散列

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

下面使用线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。解决哈希冲突的问题，当然还有 二次探测（H_i = (H_0 + i^2 )% m, 或者：H_i = (H_0 - i^2 )% m。其中：i =1,2,3…，H_0是通过散列函数Hash(x)对元素的关键码key 进行计算得到的位置m是表的大小。

在这里插入图片描述

这两种方法，在解决哈希冲突的时候对其他元素产生影响，如：现在要插入数据8，这个位置被14占了，就需要找下一个位置；当然这种方法，也会浪费大量的空间，但这就是用空间换时间的策略，后面开散列才是常用的解决哈希冲突的方法！

在这里插入图片描述

下面快速的使用闭散列的线性探测，实现基于闭散列的哈希表：

代码结构：

namespace order_table
{
	enum state
	{
		EXIST = 1,
		EMPTY,
		DELETE
	};
	template<class K, class V>
	struct HashData
	{
		std::pair<K, V> _kv;
		state _st = EMPTY;
	};
	template<class K,class V>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable(const size_t size = 5)
		{
			_table.resize(size);
		}
        ...
	private:
		std::vector<Data> _table;
		size_t _n = 0;				//  填入表中的元素个数
	};
}

插入操作：

  1. 通过哈希函数，计算出待插入的位置，如果没有哈希冲突（也就是说判断这个位置有没有插入的值了）直接插入，这里定义一个枚举类型来判断状态
  2. 如果哈希冲突，使用线性探测的方式，寻找下一个空位置！
  3. 在插入之前其实有一个重要的扩容问题，哈希表什么时候扩容呢？ 哈希表的载荷因子定义为：α = 填入表中的元素个数 / 哈希表的长度；α 越大说明，填入表中的元素个数越多，哈希冲突的概率就会越大，所以在开放定址法中α严格定义在0.7 - 0.8之间！
  4. 哈希表扩容是会重新遍历，所以在扩容的那一下会消耗大一些
bool insert(const std::pair<K, V>& kv)
{
    // 查找一下，不添加重复的元素
    if (find(kv.first))
    {
        return false;
    }
	// 扩容
	if ((double)_n / (double)_table.size() >= 0.7)
	{
		size_t newsize = _table.size() * 2;
		HashTable tb(newsize);

		for (int i = 0; i < _table.size(); i++)
		{
			if (_table[i]._st == EXIST)
			{
				tb.insert(_table[i]._kv);
			}
		}
		_table.swap(tb._table);
	}
	// 通过哈希函数，计算出待插入的位置，
	int hashi = kv.first % _table.size();

	// 线性探测，避免哈希冲突
	while (_table[hashi]._st == EXIST)
	{
		hashi++;
		hashi %= _table.size();
	}

	_table[hashi]._kv = kv;
	_table[hashi]._st = EXIST;
	_n++;

	return true;
}

查找操作

  1. 查找hash表中的元素，通过哈希函数计算初步计算出了查找的位置，EXIST存在但有可能不是查找的元素，如查找14，计算到了4这个位置，但是不是要找元素，另外，当找到状态为DELETE是不能停下来的！要找到下一个空（EMPTY）位置！

    在这里插入图片描述

  2. 如果找到下一个空（EMPTY）位置说明，哈希表中不存在该元素！

Data* find(const K& key)
{
	int hashi = key % _table.size();

	while (_table[hashi]._st != EMPTY)
	{
		if (_table[hashi]._st == EXIST && _table[hashi]._kv.first == key)
		{
			return &_table[hashi];
		}
		hashi++;
		hashi %= _table.size();
	}

	return nullptr;
}

删除操作

  1. 查找的逻辑，然后，将状态置成DELETE即可。
bool erase(const K& key)
{
	Data* data = find(key);
	if (data != nullptr)
	{
		data->_st = DELETE;
		_n--;
		return true;
	}
	return false;
}
3.2.开散列

开散列法又叫链地址法(开链法)，或称为哈希桶开辟一个指针数组，通过哈希函数计算关键字，出现哈希冲突时，将冲突的元素通过单链表的方式链接。

在这里插入图片描述

代码结构：

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

	template<class K,class V>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable(const size_t size = 5)
		{
			_table.resize(size, nullptr);
		}
		
		...
		
	private:
		std::vector<Node*> _table;
		size_t _n = 0;				//  填入表中的元素个数
	};
}

插入操作：

  1. 考虑扩容，由于使用哈希桶的方式解决哈希冲突的问题，是以链表的方式，对冲突元素进行链接，冲突不对影响其他元素，所以平衡因子 = 1时扩容

  2. 扩容使用现代方法，即重新开辟一个哈希表对象，将旧表元素插入新表中，然后旧表和新表交换！

  3. 哈希冲突时使用头插法

    在这里插入图片描述

bool insert(const std::pair<K,V> kv)
{
    // 避免插入重复元素
    if (find(kv.first))
    {
        return false;
    }

    if (_n / _table.size() >= 1)
    {
        size_t new_size = _table.size() * 2;
        HashTable<K, V> new_table(new_size);

        for (int i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            while (cur)
            {
                new_table.insert(cur->_kv  );
                cur = cur->_next;
            }
        }
        _table.swap(new_table._table);
    }

    int hashi = kv.first % _table.size();

    // 插入逻辑
    Node* new_node = new Node(kv);
    Node *cur = _table[hashi];
    _table[hashi] = new_node;
    new_node->_next = cur;
    _n++;

    return true;
}

查找操作

Node* find(const K& key)
{
	int hashi = key % _table.size();

	Node* cur = _table[hashi];

	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}

删除操作

  1. 如果为NULL不用删除，返回fasle；如果删除1，即_table[hashi]这个位置，置为NULL然后删除；如果删除4，那么4位置出为cur，prev = _table[hashi]；prev-> _next = cur-> _next，然后delete删除cur
    在这里插入图片描述
bool erase(const K& key)
{
	int hashi = 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;
			}
			delete(cur);
			_n--;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	return false;
}
4.字符串哈希算法

如果你完整的实现了上面的代码，那么使用哈希函数：int hashi = key % _table.size();时会发现，这个哈希函数只能对能整形进行计算！

如何能对浮点数和字符串进行哈希计算呢

template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<std::string>
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;
		for (char ch : key)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};

这样就支持了！关于哈希字符串函数算法：参考博客，完整的哈希桶的实现代码

namespace hash_backet
{	
	template<class K>
	struct DefaultHashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	template<>
	struct DefaultHashFunc<std::string>
	{
		size_t operator()(const std::string& key)
		{
			size_t hash = 0;
			for (char ch : key)
			{
				hash = hash * 131 + ch;
			}
			return hash;
		}
	};
	template<class K,class V>
	struct HashNode
	{
		std::pair<K, V> _kv;
		HashNode* _next;

		HashNode(const std::pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}

	};

	template<class K,class V>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable(const size_t size = 5)
		{
			_table.resize(size, nullptr);
		}

		bool insert(const std::pair<K,V> kv)
		{
			// 避免插入重复元素
			if (find(kv.first))
			{
				return false;
			}

			if (_n / _table.size() >= 1)
			{
				size_t new_size = _table.size() * 2;
				HashTable<K, V> new_table(new_size);

				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						new_table.insert(cur->_kv  );
						cur = cur->_next;
					}
				}
				_table.swap(new_table._table);
			}
			DefaultHashFunc<K> dtf;
			size_t hashi = dtf(kv.first )% _table.size();

			// 插入逻辑
			Node* new_node = new Node(kv);
			Node *cur = _table[hashi];
			_table[hashi] = new_node;
			new_node->_next = cur;
			_n++;
			
			return true;
		}
		bool erase(const K& key)
		{
			DefaultHashFunc<K> dtf;
			size_t hashi = dtf(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;
					}
					delete(cur);
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		Node* find(const K& key)
		{
			DefaultHashFunc<K> dtf;
			size_t hashi =  dtf(key) % _table.size();

			Node* cur = _table[hashi];

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		void print()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				printf("%d:", i);
				Node* data = _table[i];

				while (true)
				{
					if (data== nullptr)
					{
						std::cout << "NULL" << std::endl;
						break;
					}
					else
					{
						std::cout << data->_kv.second << "-->";
						data = data->_next;
					}
				}
			}
		}
	private:
		std::vector<Node*> _table;
		size_t _n = 0;				//  填入表中的元素个数，用于计算平衡因子
	};
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/354899.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

80.网游逆向分析与插件开发-背包的获取-自动化助手显示物品数据1

80.网游逆向分析与插件开发-背包的获取-自动化助手显示物品数据1

内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;升级Notice类获得背包基址-CSDN博客 码云地址&#xff08;ui显示角色数据 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号&#xff1a;3be017de38c50653b…
阅读更多...
BGP：04 fake-as

BGP：04 fake-as

使用 fake-as 可以将本地真实的 AS 编号隐藏&#xff0c;其他 AS 内的对等体在指定本端对等体所在的AS 编号时&#xff0c;应该设置成这个伪AS 编号。 这是实验拓扑&#xff0c;IBGP EBGP 邻居都使用物理接口来建立 基本配置&#xff1a; R1: sys sysname R1 int loo0 ip add…
阅读更多...
面了快手电商数据分析师岗(实习)，被问的汗流浃背。。。。

面了快手电商数据分析师岗(实习)，被问的汗流浃背。。。。

最近技术群的一位同学&#xff0c;分享了他面试快手数据分析师岗(实习)的经验。我看了一下面试题&#xff0c;说实话内容不难&#xff0c;他直言没有认真准备。 今天整理后分享给大家&#xff0c;如果你对这块面试感兴趣&#xff0c;可以文末加入我们的面试、技术群 内容 1&…
阅读更多...
时序预测 | Python基于Multihead-Attention-TCN-LSTM的时间序列预测

时序预测 | Python基于Multihead-Attention-TCN-LSTM的时间序列预测

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 时序预测 | Python基于Multihead-Attention-TCN-LSTM的时间序列预测 Multihead-Attention-TCN-LSTM&#xff08;多头注意力-TCN-LSTM&#xff09;是一种结合了多个注意力机制、时序卷积网络&#xff08;TCN&#xff0…
阅读更多...
解决方案｜构建生物医学科技桥梁：镭速客户案例分享

解决方案｜构建生物医学科技桥梁：镭速客户案例分享

随着生物科技在医学领域的快速发展&#xff0c;数据传输在实现医疗创新和科学研究中的重要性变得日益突出。数据不仅庞大&#xff0c;而且高度敏感&#xff0c;传统的数据传输方式已经无法满足医学行业对高效、快速的数据交流需求。 如今市场上备受关注的解决方案是基于UDP传输…
阅读更多...
计算机毕业设计 基于SpringBoot的校园闲置物品交易系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 基于SpringBoot的校园闲置物品交易系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
【gmsh源码阅读】OCC对象绑定tag及获取几何与网格映射关系

【gmsh源码阅读】OCC对象绑定tag及获取几何与网格映射关系

一、Tag是什么&#xff1f; gmsh中的几何模型相对于OCC的模型增加了id编号&#xff0c;也叫tag&#xff0c;在gmsh中可以显示出来。在gmsh中&#xff0c;点、线、面、体都有Tag&#xff0c;以方便对其查找定位查找。在OCC中TopoDS_Shape只有几何与拓扑结构&#xff0c;没有唯一…
阅读更多...
数据中心代理IP：最优性价比业务应用指南

数据中心代理IP：最优性价比业务应用指南

数据中心代理IP在应对高速高并发的业务时&#xff0c;以独特的高速传输&#xff0c;游刃有余地应对多任务处理&#xff0c;适合于特定业务场景的高效加速。理性选用数据中心代理IP&#xff0c;可以为业务将迎来更加稳健和迅速的发展。今天&#xff0c;我们将揭示数据中心代理IP…
阅读更多...
【Linux】分区向左扩容的方法

【Linux】分区向左扩容的方法

文章目录 为什么是向左扩容操作前的备份方法&#xff1a;启动盘试用Ubuntu后进行操作 为什么是向左扩容 Linux向右扩容非常简单&#xff0c;无论是系统自带的disks工具还是apt安装的gparted工具&#xff0c;都有图像化的界面可以操作。但是&#xff0c;都不支持向左扩容。笔者…
阅读更多...
MC3172 串口模块

MC3172 串口模块

MC3172 支持12个串口对应关系如下 串口模块初始化 第一个是uart0~11 inpin RX 脚 管脚号 outpin TX脚 管脚号 baud 波特率 read_ptr ,数据读取指针 void uart_init(u32 uart_num,u8 in_pin,u8 out_pin,u32 baud,u8* read_ptr) {INTDEV_SET_CLK_RST(uart_num,(INTDEV_RUN|…
阅读更多...
《动手学深度学习(PyTorch版)》笔记4.6

《动手学深度学习(PyTorch版)》笔记4.6

注&#xff1a;书中对代码的讲解并不详细&#xff0c;本文对很多细节做了详细注释。另外&#xff0c;书上的源代码是在Jupyter Notebook上运行的&#xff0c;较为分散&#xff0c;本文将代码集中起来&#xff0c;并加以完善&#xff0c;全部用vscode在python 3.9.18下测试通过。…
阅读更多...
MyBatis详解（3）-- 动态代理及映射器

MyBatis详解（3）-- 动态代理及映射器

MyBatis详解&#xff08;3&#xff09; mybatis 动态代理动态代理的规范selectOne和selectListnamespace mybatis映射器映射器的引入&#xff1a; 映射器的组成select 元素结构&#xff1a;单个参数传递多个参数传递 insert 元素结构主键回填&#xff1a;自定义主键生成规则 u …
阅读更多...
Linux中查看端口被哪个进程占用、进程调用的配置文件、目录等

Linux中查看端口被哪个进程占用、进程调用的配置文件、目录等

1.查看被占用的端口的进程&#xff0c;netstat/ss -antulp | grep :端口号 2.通过上面的命令就可以列出&#xff0c;这个端口被哪些应用程序所占用&#xff0c;然后找到对应的进程PID https://img-blog.csdnimg.cn/c375eb2bed754426b373907acaa7346e.png 3.根据PID查询进程。…
阅读更多...
Kafka-服务端-GroupCoordinator

Kafka-服务端-GroupCoordinator

在每一个Broker上都会实例化一个GroupCoordinator对象&#xff0c;Kafka按照Consumer Group的名称将其分配给对应的GroupCoordinator进行管理&#xff1b; 每个GroupCoordinator只负责管理Consumer Group的一个子集&#xff0c;而非集群中全部的Consumer Group。 请注意与Kaf…
阅读更多...
数据结构篇-03：堆实现优先级队列

数据结构篇-03：堆实现优先级队列

本文着重在于讲解用 “堆实现优先级队列” 以及优先级队列的应用&#xff0c;在本文所举的例子中&#xff0c;可能使用优先级队列来解并不是最优解法&#xff0c;但是正如我所说的&#xff1a;本文着重在于讲解“堆实现优先级队列” 堆实现优先级队列 堆的主要应用有两个&…
阅读更多...
OpenCV 2 - 矩阵的掩膜操作

OpenCV 2 - 矩阵的掩膜操作

1知识点 1-1 CV_Assert(myImage.depth() == CV_8U); 确保输入图像是无符号字符类型,若该函数括号内的表达式为false，则会抛出一个错误。 1-2 Mat.ptr(int i = 0); 获取像素矩阵的指针，索引 i 表示第几行，从0开始计行数。 1-3 const uchar* current = mylmage.ptr(row); 获得…
阅读更多...
React 组件生命周期-概述、生命周期钩子函数 - 挂载时、生命周期钩子函数 - 更新时、生命周期钩子函数 - 卸载时

React 组件生命周期-概述、生命周期钩子函数 - 挂载时、生命周期钩子函数 - 更新时、生命周期钩子函数 - 卸载时

React 组件生命周期-概述 学习目标&#xff1a; 能够说出组件的生命周期一共几个阶段 组件的生命周期是指组件从被创建到挂在到页面中运行&#xff0c;在到组件不用时卸载组件 注意&#xff1a;只有类组件才有生命周期&#xff0c;函数组件没有生命周期(类组件需要实例化&…
阅读更多...
uni-app 开发着突然忘记项目所在位置 教你快速通过HBuilder X定位到项目的位置

uni-app 开发着突然忘记项目所在位置 教你快速通过HBuilder X定位到项目的位置

我经常会开发着 开发着 就忘记项目在哪了 我们可以用编辑器打开项目 然后右键项目目录 然后选择这个 使用命令行窗口打开所在目录(U) 这样 他就会快速用 本地文件夹 帮你打开这个目录了 还可以 右键项目 选择 使用命令行窗口打开所在目录(U) 下面就会帮你打开这个目录的终端…
阅读更多...
腾讯云一键搭建幻兽帕鲁服务器教程

腾讯云一键搭建幻兽帕鲁服务器教程

幻兽帕鲁&#xff08;Palworld&#xff09;是一款多人在线游戏&#xff0c;为了获得更好的游戏体验&#xff0c;许多玩家选择自行搭建游戏联机服务器&#xff0c;但是如何搭建游戏联机服务器成为一个难题&#xff0c;腾讯云提供了游戏联机服务器一键部署方案&#xff0c;让大家…
阅读更多...
java8 映射方法（map，flatMap）

java8 映射方法（map，flatMap）

5.2　映射&#xff08;map&#xff0c;flatMap&#xff09; 一个非常常见的数据处理套路就是 从某些对象中选择信息。比如在SQL里&#xff0c;你可以从表中选择一列。Stream API也通过map和flatMap方法提供了类似的工具。 5.2.1　对流中每一个元素应用函数&#xff08;map&am…
阅读更多...
最新文章

Copyright @ 2022~2023