首页 > 其他分享 >数据结构——哈希

数据结构——哈希

时间：2024-07-19 21:01:18浏览次数：11  
标签：tables 哈希 hashi kv key 数据结构 size

前言

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

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

一、概念

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

当向该结构中：

  • 插入元素：

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

  • 搜索元素：

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

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

例如：数据集合{1,7,6,4,5,9}；

哈希函数设置为：hash(key) = key % capacity；capacity为存储元素底层空间总的大小

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

二、哈希冲突

对于两个数据元素的关键字_i和_j（i != j），但有Hash(_i) = Hash(_j)，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该现象称为哈希冲突或哈希碰撞。

把具有不同关键码二具有相同哈希地址的数据元素称为“同义词”

三、哈希函数

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

哈希函数设计原则

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

常见哈希函数

  • 直接定址法

取关键字的某个线性函数为散列地址：Hash(key) = A * key + B

优点：简单、均匀

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

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

  • 除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p(p <= m)，将关键码转换成哈希地址

四、哈希冲突解决方法

4.1 闭散列

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

线性探测

        从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

【插入】

  • 通过哈希函数获取待插入元素在哈希表中的位置
  • 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

【删除】

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

线性探测的实现

namespace open_address
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _s;
	};

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

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}
			cout << key << ":" << hash << endl;
			return hash;
		}
	};

	template<class K,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			// 负载因子0.7就扩容
			if (_n * 10 / _tables.size() == 7)
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(newSize);
				// 遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			Hash hf;
			// 线性探测
			size_t hashi = hf(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIST)
			{
				hashi++;

				hashi %= _tables.size();
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hf;

			size_t hashi = hf(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				hashi++;
				hashi %= _tables.size();
			}

			return NULL;
		}

		// 伪删除法
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else
				{
					printf("[%d]->D\n", i);
				}
			}

			cout << endl;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0; // 存储的关键字的个数
	};
}

【优点】实现非常简单

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

二次探测

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

4.2 开散列

4.2.1 概念

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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

4.3.2 开散列实现

namespace hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		HashNode* _next;
		pair<K, V> _kv;

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

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

	template<class K, class V,class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			// 负载因子最大到1
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize);
				// 遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}

				_tables.swap(newHT._tables);
			}

			size_t hashi = kv.first % _tables.size();
			Node* newnode = new Node(kv);

			// 头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return true;
		}

		Node* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}
			return NULL;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 4,14,24,34,5,7,1,15,25,3 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(13, 13));
	}
}

标签：tables,哈希,hashi,kv,key,数据结构,size
From： https://blog.csdn.net/m0_73243771/article/details/140461550

相关文章

  • 字符串哈希
    #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefdoubledb;typedeflongdoubleldb;typedefpair<int,int>pii;typedefpair<ll,ll>PII;#definepbemplace_back//#defineint......
  • 数据结构—双向链表
    文章目录1.双向链表的概念和结构1.1双向链表的概念1.2双向链表与单链表的对比1.3双向链表的结构2.双向链表的接口实现2.1申请一个新结点2.2初始化2.3打印2.4尾插2.5头插2.6判断链表是否为空2.7尾删2.8头删2.9查找2.10在指定位置之后插入数据2.11在指定位......
  • 数据结构与算法 数组篇之长度最小的子数组
    问题描述：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl,numsl+1,...,numsr-1,numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。题目链接：.-力扣（LeetCode）解题思路：双指针，......
  • 算法刷题笔记 字符串哈希（C++实现）
    文章目录题目描述基本思路实现代码题目描述给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式第一行包含整数n和m，表示字符......
  • 基础数据结构——初级——链表
    链表的特点是一组位于任意位置的存储单元存储线性表的数据元素。一般分为单向链表和双向链表（如下图所示）。 使用链表时，可以用STL的list，也可以自己写链表。如果自己写代码实现链表，有两种编码实现方法：动态链表和静态链表。在算法竞赛中为加快编码速度，一般用静态链表或者STL的l......
  • 【数据结构】- 线段树
    前言线段树用于维护区间上的值，可以在$O(\logn)$的时间复杂度内实现单点，区间修改及查询。并且所有满足结合律的运算都可以用线段树进行加速。基本操作建树给你长度为$n$的正整数序列$A$，要你实现单点修改与区间查询。（加和）这就是线段树的基本题目。线段树，字面上来看就是把......
  • 哈希
    哈希 我认为的哈希：比较两个东西是否相同把一个东西提前映射成一个数，像map，但是O(1）比较  字符串哈希（进制哈希）   详解 https://www.luogu.com.cn/problem/P3370第1题   字符串哈希 查看测评数据信息如题，给定N个字符串（第i个字符串长度为Mi，字符串......
  • 基于Python语言的入门算法和数据结构（持续更新中，求关注一波）[链表 栈 队列 复杂度 操作]
    这篇文章主要是讲的Python语言的算法，本人还在不断记笔记中，文章也会持续更新，内容比较浅薄，请大家指教另外推荐一个比较好用的记笔记的软件Typora,自己已经使用很久了，感觉不错。。。虽然但是还是有欠缺。目录第一章算法概述1.1什么是数据结构？01数据结构都有哪些组成方式02......
  • Java中的并发数据结构与多线程优化技术
    Java中的并发数据结构与多线程优化技术大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！在多线程编程中，并发数据结构和优化技术是提高系统性能和可靠性的关键。Java提供了丰富的并发数据结构和多线程优化技术，本文将详细介绍常用的并发数据结构及其使用方法......
  • 【数据结构】队列：链表实现
    队列：链表实现结构描述:typedefintDataType;typedefstructQueueNode{DataTypeA;structQueueNode*Next;}Node;classQueueLinked{public://队头、队尾指针Node*Front;Node*Next;//队列操作//把元素X入队voidPush(Dat......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99