【C++哈希（一）】哈希&哈希冲突

分类:热门推荐日期:2024-05-28浏览:1评论:0

目录

前言：

一、哈希概念

1.哈希思想

2.哈希函数

二、哈希冲突

1.产生原因

2.解决方法

        2.1闭散列（开放定址法）解决

2.2开散列解决

三、完整代码

前言：

        我们知道在C++98中，STL提供了底层为红黑树结构的一系列关联容器，在查询时效率可以log2(n)，即最差情况下需要比较红黑树的高度次，但是当树中节点多的时候，查询效率也不理想。最好的查询是，进行很少的比较次数就能将元素找到，所以在C++11中，又加入了4个unordered系列的容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，unordered系列的容器使用了哈希结构为底层。

        以红黑树结构为底层的容器查询的平均时间复杂度为O(logn)，而以哈希结构为底层的容器查询的平均时间复杂度则是O(1)，那么为什么以哈希结构为底层的容器查询效率如此之高呢？哈希结构是一种什么结构？接下来我会为同学们讲解。

一、哈希概念

        我们知道在数据结构中，比如平衡树或红黑树，元素key和它在数据结构中存储的位置之间没有对应的关系，因此在查找一个元素时，必须要经过多次比较。如果按顺序查找的话，那么时间复杂度就是O(n)，平衡树中则为树的高度。所以，搜索的效率取决于搜索过程中元素的比较次数。

        那么有没有一个不用比较，直接就能从数据结构中找到要搜索的元素呢？这就是我们今天要讲的哈希。

        哈希（Hash）是一种通过算法将任意长度的数据转换为固定长度的字符串或数字的过程。这个固定长度的输出通常称为哈希值（hash value）、哈希码（hash code）或摘要（digest）。哈希函数（hash function）是实现这一过程的核心算法。  

        今天我们要讲的是哈希在数据结构中的应用。      

1.哈希思想

        在数据结构中，哈希思想主要用于哈希表（Hash Table）。哈希表是一种可以提供非常快速的插入、删除和查找操作的数据结构。其核心思想是利用哈希函数将数据的键值映射到哈希表中的一个位置（或桶），从而实现高效的数据存取。

        在哈希表中，向表中插入数据，需要根据待插入元素的关键码，以哈希函数计算出该元素的存储位置并按此位置进行存放；在表中搜索元素，对元素的关键码进行同样计算，把求得的函数值当作元素的存储位置，在结构中按此位置取元素比较，若关键码相同，则搜索成功。

        

那么哈希函数是什么呢？哈希函数是如何根据键值产生哈希值的呢？

2.哈希函数

        哈希函数是将任意大小的数据输入转换成固定大小的值（通常是一个整数）的函数。这个固定大小的值称为哈希值（Hash Value）或哈希码（Hash Code）。在C++中，哈希函数在unordered_map、unordered_set等哈希表容器中起着关键作用

      哈希函数的特性

  1. 确定性：对于相同的输入，总是产生相同的输出。
  2. 高效性：计算哈希值的时间复杂度应该是常数时间，即�(1)O(1)。
  3. 均匀性：应尽量将输入数据均匀地分布在哈希表的各个桶中，减少冲突。
  4. 抗碰撞：尽量减少不同输入产生相同哈希值的概率（即碰撞）

        设计哈希函数的原则

  1. 输入范围广：能够处理各种类型的输入数据。
  2. 分布均匀：生成的哈希值应均匀分布在可能的输出范围内。
  3. 敏感性：输入数据的微小变化应导致哈希值的显著变化。

         一些常见的哈希函数的构造方法

  1. 直接定址法

    其哈希函数为一次函数，即以下两种形式：

    H（key）= key 或者 H（key）= a * key + b

    其中 H（key）表示关键字为 key 对应的哈希地址，a 和 b 都为常数。

  2. 数字分析法

    如果关键字由多位字符或者数字组成，就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。

  3. 平方取中法

    平方取中法是对关键字做平方操作，取中间得几位作为哈希地址。此方法也是比较常用的构造哈希函数的方法

    例如关键字序列为{421，423，436}，对各个关键字进行平方后的结果为{177241，178929，190096}，则可以取中间的两位{72，89，00}作为其哈希地址。

  4. 折叠法

    折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。

  5. 除留余数法

    若已知整个哈希表的最大长度 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余运算，即：H（key）= key % p。

    在此方法中，对于 p 的取值非常重要，由经验得知 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数。

  6. 随机数法

    是取关键字的一个随机函数值作为它的哈希地址，即：H（key）=random（key），此方法适用于关键字长度不等的情况。

    注意：这里的随机函数其实是伪随机函数，随机函数是即使每次给定的 key 相同，但是 H（key）都是不同；而伪随机函数正好相反，每个 key 都对应的是固定的 H（key）

二、哈希冲突

1.产生原因

         哈希冲突指的是两个或多个不同的键被映射到了哈希表中的同一个位置，即它们具有相同的哈希值。哈希冲突在哈希表中是常见的情况，因为哈希函数将无限的输入域映射到了有限的输出域，导致多个键可能映射到同一个位置。

        产生哈希冲突的根本原因是哈希函数设计的不合理，那么如何解决呢？

2.解决方法

        解决哈希冲突的常见方法有链地址法、开放寻址法、再哈希、公共溢出区等。而开放寻址法又有线性探测、二次探测、双重哈希的方法。今天我们主要讲的是开放寻址法的线性探测方法。

        2.1闭散列（开放定址法）解决

           线性探测是一种开放寻址的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，线性探测用于解决此时产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。

        线性探测插入过程

　　新加入一个元素e1，key为5，hash函数计算出应该存到位置5，因为5%8=5，然后看位置5有没有被占用，发现没有被占用，则将e1存入位置5：

　　

　　又加入一个新元素e2，key为13，hash函数计算出也应该存到位置5，因为13%8=5，但是发现位置5已经被占用了，此时就位置6有没有被占用，此时发现位置6没有被占用，则e2就存到位置6了

　　

　　此时又来一个e3，key为21，发现还要存到位置5，但是位置5已经被占了，往后看位置6，发现位置6也被占了，再看位置7，位置7空着，所以e3就存到位置7了。

        线性探测查找过程 

        我们规定：当哈希表中存储的数据量与哈希表的容量的比值（负载因子）过大时，扩大哈希表的容量，并重新进行映射。

        所以因为有负载因子的存在，所以哈希表一定有剩余空间，当发生哈希冲突时，从冲突位置向后探测，知道找到可用位置为止。

        现在要查询key为5的元素，通过计算，对应的位置为5，查看位置5的key，发现位置5的key与要查找的key相等，则查找成功，返回e1；

　　如果要查询一个key为13的元素，通过计算key为13，对应位置5，但是位置5的key为5，与13不匹配，此时往后看位置6，发现位置6的key为13，与要查找的key相等，此时查找成功，返回e2即可；

　　如果要查询key为37的元素，通过计算对应位置5，但是位置5的key为5，与13不匹配，往后看位置6的key为13也和37不匹配，一直到位置0，发现e4的key为29，仍旧不匹配要找的37，接着看位置1，发现位置1没有元素，证明数组中没有存key为37的元素，查找失败。

        线性探测删除过程 

        此时要删除一个元素key为13，此时，通过hash计算出位置应该在位置5，因为13%8=5，发现位置5的key为5，不等于要删除的13；

　　往后看位置6，发现位置6的key为13，和要删除的key相同，测试将位置6的元素删除：

        

        下面我用代码来实现

template>class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		bool Insert(const pair& kv)
		{
			if (Find(kv.first))
				return false;
			// 负载因子0.7就扩容
			if (_n * 10 / _tables.size() == 7)
			{
				size_t newSize = _tables.size() * 2;
				HashTable 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* 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;
		}
		// 伪删除法
	private:
		vector> _tables;
		size_t _n = 0; // 存储的关键字的个数
	};

2.2开散列解决

        开散列（Open Hashing），也称为链地址法（Chaining），是解决哈希冲突的一种常见方法。在这种方法中，每个哈希表的桶（或槽）不再只存储一个单独的元素，而是存储一个链表或其他形式的集合，用于存放多个具有相同哈希值的元素。这样，当哈希冲突发生时，冲突的元素可以直接添加到链表的末尾。

实现开散列的方法

  1. 初始化哈希表：

    • 创建一个包含若干个桶的哈希表，每个桶初始化为空链表。

  2. 插入操作：

    • 计算元素的哈希值，确定该元素应当放置的桶。
    • 将该元素插入到对应桶的链表中。

  3. 查找操作：

    • 计算查找元素的哈希值，找到对应的桶。
    • 遍历桶中的链表，查找目标元素。

  4. 删除操作：

    • 计算删除元素的哈希值，找到对应的桶。
    • 遍历桶中的链表，找到并删除目标元素。

开散列的优缺点

优点：

  1. 简单易实现：实现开散列相对简单，代码维护性强。
  2. 动态扩展性：链表可以动态扩展，不受哈希表初始大小的限制。
  3. 避免聚集：开散列避免了线性探测和二次探测中可能出现的聚集现象，降低了查找时间的波动。

缺点：

  1. 额外内存开销：每个桶需要额外的内存来存储链表指针，增大了内存使用。
  2. 性能波动：如果某个桶中的元素过多（链表过长），查找性能会下降。
  3. 局部性差：链表存储的元素可能分散在内存的不同位置，降低了缓存命中率。

 代码实现

templateclass HashTable
	{
		typedef HashNode 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& kv)
		{
			if (Find(kv.first))
				return false;
			// 负载因子最大到1
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() * 2;
				HashTable 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)
		{
			//....
			return NULL;
		}
	private:
		vector _tables;
		size_t _n = 0;
	};

三、完整代码

HashTable.h

#pragma once
#includenamespace open_address
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE
	};
	templatestruct HashData
	{
		pair _kv;
		Status _s;          //状态
	};
	templatestruct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	template<>struct HashFunc{
		size_t operator()(const string& key)
		{
			// BKDR
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}
			cout << key << ":" << hash << endl;
			return hash;
		}
	};
	template>class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		bool Insert(const pair& kv)
		{
			if (Find(kv.first))
				return false;
			// 负载因子0.7就扩容
			if (_n*10 / _tables.size() == 7)
			{
				size_t newSize = _tables.size() * 2;
				HashTable 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* 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* 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)
				{
					//printf("[%d]->%d\n", i, _tables[i]._kv.first);
					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> _tables;
		size_t _n = 0; // 存储的关键字的个数
	};
	void TestHT1()
	{
		HashTable ht;
		int a[] = { 4,14,24,34,5,7,1 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Insert(make_pair(3, 3));
		ht.Insert(make_pair(3, 3));
		ht.Insert(make_pair(-3, -3));
		ht.Print();
		ht.Erase(3);
		ht.Print();
		if (ht.Find(3))
		{
			cout << "3存在" << endl;
		}
		else
		{
			cout << "3不存在" << endl;
		}
		ht.Insert(make_pair(3, 3));
		ht.Insert(make_pair(23, 3));
		ht.Print();
	}
	void TestHT2()
	{
		string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		//HashTable ht;
		HashTable ht;
		for (auto& e : arr)
		{
			//auto ret = ht.Find(e);
			HashData* ret = ht.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				ht.Insert(make_pair(e, 1));
			}
		}
		ht.Print();
		ht.Insert(make_pair("apple", 1));
		ht.Insert(make_pair("sort", 1));
		ht.Insert(make_pair("abc", 1));
		ht.Insert(make_pair("acb", 1));
		ht.Insert(make_pair("aad", 1));
		ht.Print();
	}
}
namespace hash_bucket
{
	templatestruct HashNode
	{
		HashNode* _next;
		pair _kv;
		HashNode(const pair& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	templateclass HashTable
	{
		typedef HashNode 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& kv)
		{
			if (Find(kv.first))
				return false;
			// 负载因子最大到1
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() * 2;
				HashTable 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)
		{
			//....
			return NULL;
		}
	private:
		vector _tables;
		size_t _n = 0;
	};
	void TestHT1()
	{
		HashTable 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));
	}
}

这就是我们对哈希的初理解以及对哈希冲突的解决啦，喜欢的点个赞谢谢~

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号