首页 > 编程语言 >Hash表（C++）

Hash表（C++）

时间：2024-07-13 16:30:34浏览次数：16  
标签：tables hash cur C++ return key Hash size

        本篇将会开始介绍有关于 unordered_map 和 unordered_set 的底层原理，其中底层实现其实就是我们的 Hash 表，本篇将会讲解两种 Hash 表，其中一种为开放定址法，另一种为 hash 桶，在unordered_map 和 unordered_set 的底层实现中主要是使用的是 hash 桶。

        本篇分别介绍了 hash 表的两种实现方法，接着讲解 hash 冲突、扩容与 hash 函数的设计原则。最后使用代码实现 hash 表的数据结构。

目录

hash概念

1. 开放定址法

2. hash 桶

hash冲突与hash函数

1. hash冲突

2. hash 函数

3. hash 表的扩容

代码实现

1. 开放定址法

2. hash 桶

hash概念

        我们在顺序结构或者平衡树中，想要查找一个数必须经过关键码的多次比较，顺序查找的时间复杂度为O(n)，平衡树的查找时间复杂度为O(logn)。但是是否存在一种搜索方法，我们可以不经过任何比较，直接从表中找到我们想要的元素。

        我们构建的 hash 表就可以达到这样的效果：通过某种函数（hashfunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么我们在查找时通过该函数可以很快的找到该元素。

        构造出相应的结构：

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

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

        本篇一共构造两种结构：开放定址法、hash 桶。如下：

1. 开放定址法

        关于开放定址法，其中的主要思想为：构建一个存放数据的 hash 表，然后通过 hashfunc 计算出元素对应的关键码，然后将元素对应的放置在相应的 hash 表中的位置，如下：

        假设我们存放元素集合：{1，7，6，4，5，9}。

        当我们想要进行搜索元素的时候，我们就可以直接使用对应的 hash 函数搜索对应的元素。

2. hash 桶

        关于 hash 桶，其主要思想为：我们首先先建立一个 hash 表，在 hash 表中的每一个位置，我们都直接将使用哈希函数计算出元素对应的关键码存放到对应位置，如下：

        假设我们存放的元素集合为：{1，7，6，4，5，9，44}。

        当其中同一个位置存在多个元素的时候，我们只需要将多的元素链接到最后元素的后面即可。

hash冲突与hash函数

1. hash冲突

        在实现 hash 表，计算元素对应的关键码的时候，难免会遇到关键码相同的情况，也就是同一个位置将会存放两个元素，也就是 hash 冲突。对于开放定址法而言就会存在 hash 冲突，而 hash 桶则不用担心会出现 hash 冲突。

        关于 hash 冲突的解决方法：

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

        插入：首先通过哈希函数获取插入元素在哈希表中的位置，若该位置没有元素则直接插入新的元素，若该位置中有元素发生哈希冲突，我们则使用线性探测找到下一个空位置，然后在插入元素，如下：

        删除：关于使用线性探测法删除元素，我们不能直接删除元素，直接删除元素将会影响其他元素的搜索。比如删除元素4，如果直接将其删掉，44的查找将会受到影响，所以线性探测采用标记的伪删除法来删除一个元素。

enum State {EMPTY, EXIST, DELETE};
// EMPTY此位置为空
// EXIST此位置存在元素
// DELETE此位置元素已经删除

        二次探测：线性探测的缺陷是产生冲突的数据会堆积在一块，这与查找下一个空位置有关系，因为找空位置的方法就是挨着往后逐个去找，因此二次探索为了避免该问题，找到下一个空位置的方法为：Hi = (H0 + i ^ 2) % m 或者 Hi = (H0 - i ^ 2) % m，其中 H0 为通过散列函数计算出的关键码对应的位置，m 是表的大小。

2. hash 函数

        关于引起 hash 冲突的一个原因为：hash 函数的设计不合理。

        关于 hash 函数的设计原则有：

        1. hash 函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址的时候，其值域必须在 0 ~ m - 1之间。

        2. hash 函数计算出来的地址能均匀分布在整个空间中。

        3. hash 函数的设计应该比较简单。

        常见的 hash 函数：直接定址法、除留余数法、平方取中法、折叠法、随机数法……

        直接定址法：取关键字的某个线性函数为散列地址：hash(key) = A * key + B。直接定址法的优点为：简单且均匀；缺点为：需要事先知道关键字的分布情况。适合查找比较小且连续的情况。

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

        对于其他的 hash 函数不是很常用，便不在介绍。

3. hash 表的扩容

        虽然在使用 hash 表存储元素的时候，我们可以将元素不断的映射到 hash 表中来，但是我们的 hash 表也会存在存满的情况（使用开放定址法下的 hash 表），那么也就会存在一个 hash 表扩容的问题。

        hash 表的载荷因子定义为：α = 填入表中的元素个数 / hash 表的长度。

        关于 α 的取值，对于开放定址法而言，一般取值为0.7 ~ 0.8 以下。当表中的载荷因子大于 α 的时候，我们就需要对我们的 hash 表进行扩容。

代码实现

1. 开放定址法

        该代码的实现原理为开放定址法，如下：

#pragma once
#include <vector>
#include <string>

using namespace std;

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 = hash * 131 + e;
		return hash;
	}
};

// 开放定值法
namespace Open_Address {
	enum status { 
		EMPTY, DELETE, EXIST 
	};

	template <class K, class V>
	struct HashData {
		pair<K, V> _kv;
		status _status;

		HashData() = default;

		HashData(const pair<K,V>& data)
			: _kv(data)
		{}
	};

	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable {
		typedef HashData<K, V> Data;
	public:
		// 构造函数
		HashTable() 
			: _n(0)
		{
			// 先开十个空间
			_tables.resize(10);
		}

		bool insert(const pair<K, V>& data) {
			if (find(data.first))
				return false;
			Hash hf;
			if (10 * _n / _tables.size() >= 7) {
				// 扩容
				HashTable newTable;
				newTable._tables.resize(2 * _tables.size());
				for (size_t i = 0; i < _tables.size(); i++) {
					if (_tables[i]._status == EXIST)
						newTable.insert(_tables[i]._kv);
				}
				_tables.swap(newTable._tables);
			}
			size_t cur = hf(data.first);
			cur %= _tables.size();

			while (_tables[cur]._status == EXIST) {
				cur++;
				cur %= _tables.size();
			}
			_n++;
			_tables[cur] = Data(data);
			_tables[cur]._status = EXIST;
			return true;
		}

		HashData<K, V>* find(const K& key) {
			Hash hf;
			size_t cur = hf(key);
			cur %= _tables.size();
			while (_tables[cur]._status != EMPTY) {
				if (_tables[cur]._status != DELETE && _tables[cur]._kv.first == key)
					return &_tables[cur];
				cur++;
				cur %= _tables.size();
			}
			return nullptr;
		}

		//bool erase(const K& key) {
		//	Hash hf;
		//	size_t cur = hf(key);
		//	cur %= _tables.size();
		//	if (find(key) == false)
		//		return false;
		//	while (_tables[cur]._kv.first != key) {
		//		cur++;
		//		cur %= _tables.size();
		//	}
		//	_tables[cur] = Data();
		//	_tables[cur]._status = DELETE;
		//	_n--;
		//	return true;
		//}

		bool erase(const K& key) {
			Data* Fd = find(key);
			if (Fd) return false;
			*Fd = Data();
			Fd->_status = DELETE;
			_n--;
			return true;
		}
	private:
		vector<Data> _tables;
		size_t _n;
	};
}

        关于此代码的实现，我们首先先实现计算元素关键码的类，其中主要包括两种元素，一种为数字类元素，另一类为字符串元素（计算字符串元素的关键码存在多种方式，本篇实现的只是其中的一种）。我们只需要使用一个类模板就可以实现计算关键码的类，其中字符串元素类的计算为特化的类，如下：

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 = hash * 131 + e;
		return hash;
	}
};

        对于 hash 表的建立，我们还需要建立它的数据类型和状态类型（用来表征当前位置的状态），如下：

enum status { 
	EMPTY, DELETE, EXIST 
};

template <class K, class V>
struct HashData {
	pair<K, V> _kv;
	status _status;

	HashData() = default;

	HashData(const pair<K,V>& data)
		: _kv(data)
	{}
};

        接着是插入函数，其中插入函数主要的实现为判断当前是否需要扩容，以及计算出元素的关键码，然后将元素放入到对应的位置。如下：

bool insert(const pair<K, V>& data) {
	if (find(data.first))
		return false;
	Hash hf;
	// 判断是否需要扩容
	if (10 * _n / _tables.size() >= 7) {
		// 扩容
		HashTable newTable;
		newTable._tables.resize(2 * _tables.size());
		for (size_t i = 0; i < _tables.size(); i++) {
			if (_tables[i]._status == EXIST)
				newTable.insert(_tables[i]._kv);
		}
		_tables.swap(newTable._tables);
	}
	// 计算关键码
	size_t cur = hf(data.first);
	cur %= _tables.size();

	// 若当前位置存在元素，则放在下一个位置
	while (_tables[cur]._status == EXIST) {
		cur++;
		cur %= _tables.size();
	}
	_n++;
	_tables[cur] = Data(data);
	_tables[cur]._status = EXIST;
	return true;
}

        对于查找函数，我们需要计算出搜索元素的关键码，然后使用在表中不断的查找，若找到的位置为 EMPTY，则查找失败，若找到位置为 EXIST，则说明我们找到相应的元素了，如下：

HashData<K, V>* find(const K& key) {
	Hash hf;
	size_t cur = hf(key);
	cur %= _tables.size();
	while (_tables[cur]._status != EMPTY) {
		if (_tables[cur]._status != DELETE && _tables[cur]._kv.first == key)
			return &_tables[cur];
		cur++;
		cur %= _tables.size();
	}
	return nullptr;
}

        最后则是我们的删除元素，我们首先需要使用查找函数，查看是否能找到对应的元素，若找不到则直接返回 false（表示删除失败），若找到，直接将对应位置的状态设置为 DELETE，如下：

bool erase(const K& key) {
	Data* Fd = find(key);
	if (Fd) return false;
	*Fd = Data();
	Fd->_status = DELETE;
	_n--;
	return true;
}

2. hash 桶

        接下来的代码为实现 hash 桶的代码，如下：

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 = hash * 131 + e;
		return hash;
	}
};

// hash桶
namespace Hash_Bucket {
	template<class K, class V>
	struct HashNode {
		pair<K, V> _kv;
		HashNode* next = nullptr;

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

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

		// 拷贝构造函数
		HashTable(const HashTable<K, V>& ht) {
			_tables.resize(ht._tables.size());
			size_t size = ht._tables.size();
			for (size_t i = 0; i < size; i++) {
				Node* cur = ht._tables[i];
				while (cur) {
					Node* next = cur->next;
					// 插入元素
					insert(cur->_kv);
					cur = next;
				}
			}
		}


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

		bool insert(const pair<K, V>& kv) {
			if (find(kv.first))
				return false;
			// 扩容
			Hash hf;
			//if (_n == _tables.size()) {
			//	// 扩容的时候，只需要转换一整只即可
			//	HashTable newTable;
			//	newTable._tables.resize(2 * _tables.size());
			//	for (size_t i = 0; i < _tables.size(); i++) {
			//		if (_tables[i] != nullptr) {
			//			//Node* cur = _tables[i];
			//			//while (cur) {
			//			//	newTable.insert(cur->_kv);
			//			//	cur = cur->next;
			//			//}
			//			
			//			// 将所有节点取下来连接上去
			//			Node* cur = _tables[i];
			//			while (cur) {
			//				Node* next = cur->next;
			//				// 将节点取下来重新加到新表上
			//				size_t index = hf(cur->_kv.first) % newTable._tables.size();
			//				cur->next = newTable._tables[index];
			//				newTable._tables[index] = cur;
			//				cur = next;
			//			}
			//		}
			//	}
			//	_tables.swap(newTable._tables);
			//}

			if (_n == _tables.size()) {
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				size_t size = _tables.size();
				for (int i = 0; i < size; i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->next;
						// 将节点取下来放在新表上
						size_t index = hf(cur->_kv.first) % newTables.size();
						cur->next = newTables[index];
						newTables[index] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}

			size_t index = hf(kv.first);
			index %= _tables.size();
			Node* newNode = new Node(kv);
			newNode->next = _tables[index];
			_tables[index] = newNode;
			_n++;
			return true;
		}

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

		bool erase(const K& key) {
			if (find(key) == nullptr)
				return false;
			Hash hf;
			size_t index = hf(key);
			index %= _tables.size();
			Node* cur = _tables[index];
			Node* prev = _tables[index];
			if (cur->_kv.first == key) {
				_n--;
				_tables[index] = cur->next;
				delete prev;
				return true;
			}
			while (cur->_kv.first != key) {
				if (cur->_kv.first == key) {
					prev->next = cur->next;
					delete cur;
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->next;
			}
			return false;
		}

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

        对于计算关键码的类，我们仍然沿用开放定址法的计算方法。

        但是对于 hash 表中的元素，我们则是采用指针的方法存放对应的元素，并将其初始化为 nullptr，表示当前位置没有元素。所以对于插入元素的设计，我们则将其设计为结点，当插入元素时，只需要连接到对应位置即可。

template<class K, class V>
struct HashNode {
	pair<K, V> _kv;
	HashNode* next = nullptr;

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

        接下来是插入元素，对于需要插入的元素，我们仍然是需要先判断该 hash 表是否需要扩容（这里的扩容和开放定址法的扩容不一样，元素个数和容量一致的时候我们才扩容）。然后通过计算关键码找到需要插入的位置，如下：

bool insert(const pair<K, V>& kv) {
	if (find(kv.first))
		return false;
	// 扩容
	Hash hf;

	// 扩容
	if (_n == _tables.size()) {
		vector<Node*> newTables;
		newTables.resize(_tables.size() * 2, nullptr);
		size_t size = _tables.size();
		for (int i = 0; i < size; i++) {
			Node* cur = _tables[i];
			while (cur) {
				Node* next = cur->next;
				// 将节点取下来放在新表上
				size_t index = hf(cur->_kv.first) % newTables.size();
				cur->next = newTables[index];
				newTables[index] = cur;

				cur = next;
			}
			// 将原 hash 表对应位置设置为null
			_tables[i] = nullptr;
		}
		_tables.swap(newTables);
	}
	size_t index = hf(kv.first);
	index %= _tables.size();
	Node* newNode = new Node(kv);
	newNode->next = _tables[index];
	_tables[index] = newNode;
	_n++;
	return true;
}

        接下来是查找函数，此查找函数就较为简单，因为直接就可以通过计算关键码查询是否能找到该元素。如下：

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

        最后是删除元素函数，仍然是先查找元素是否在 hash 表中，查找到之后在进行删除，其中会分为删除元素的位置在当前 hash 表的最后链接位置和中间位置进行分别讨论，如下：

bool erase(const K& key) {
	if (find(key) == nullptr)
		return false;
	Hash hf;
	size_t index = hf(key);
	index %= _tables.size();
	Node* cur = _tables[index];
	Node* prev = _tables[index];
	if (cur->_kv.first == key) {
		_n--;
		_tables[index] = cur->next;
		delete prev;
		return true;
	}
	while (cur->_kv.first != key) {
		if (cur->_kv.first == key) {
			prev->next = cur->next;
			delete cur;
			_n--;
			return true;
		}
		prev = cur;
		cur = cur->next;
	}
	return false;
}

标签：tables,hash,cur,C++,return,key,Hash,size
From： https://blog.csdn.net/m0_74830524/article/details/140398627

相关文章

  • c++ 计算mp3时长
    #include<stdio.h>#include<iostream>#include<fstream>#include<string>usingnamespacestd;structID3V2{ chartag[3]; charversion; charsubVersion; charflag; charsize[4];};constintbitrateIndex[16][5]={ {......
  • 【C++编程】数组、函数、结构体、指针、类
    数组：存储一个固定大小的相同类型元素的顺序集合声明、初始化：typearrayName[size0][size1]...={{value00,value01,...},{value10,value11,...},...};intmy_array[2][3]={{1,2,3},{4,5,6}};访问数组元素：arrayName[index0][index1]...;intget_eleme......
  • 【洛谷】P5728 【深基5.例5】旗鼓相当的对手——C++
    本题感想：本题主要是应该避免重复比较，以a,b,c,d为例，我们假设先a不动，依次比较d,c,b或者b,c,d，然后假设b不动，依次比较c,d,最后假设c不动，比较d，这样这道题就差不多解决了#include<iostream>#include<cmath>usingnamespacestd;intmain(){inta[1010][3],s[1010]={0......
  • 全栈物联网项目：结合 C/C++、Python、Node.js 和 React 开发智能温控系统（附代码示例）
    1.项目概述本文详细介绍了一个基于STM32微控制器和AWSIoT云平台的智能温控器项目。该项目旨在实现远程温度监控和控制,具有以下主要特点:使用STM32F103微控制器作为主控芯片,负责数据采集、处理和控制逻辑采用DHT22数字温湿度传感器,精确采集环境温湿度数据通过ESP8266WiF......
  • HashCode方法
    HashCode方法总结publicinthashcode()提高具有哈希结构的容器的效率；两个引用，如果指向的是同一个对象，则哈希值肯定是一样的；两个引用，如果指向的是不同对象，则哈希值是不一样的；哈希值主要根据地址号来的，不能完全将哈希值等价于地址；例子：Aobj1=newA();Aobj2=newA()......
  • C++数组 字符串
    是什么：相同类型元素的集合写法：intexample[3]//数组在声明大小时必须为常数数组名example是个指针类型如int*ptr=example;数组索引的工作原理：example[3]//从首地址位置偏移数组类型大小（int是4字节）乘索引值（4*3）个字节//从当前字节位置往后读四个字节；可能出现的错误：ex......
  • 解决Microsoft Visual C++ runtime package找不到问题
    使用了Dism++进行电脑清理,不小心选择了下面两个内容:尤其是第二个packagecache绝对不能清空,否则不知道哪个软件就不能运行了,报MicrosoftvisualC++runtime问题.然后再安装各个版本MicrosoftvisualC++redis仍会报同样的问题,死循环了.网上有各种解决方案,有......
  • C++中的可见性 指针 笔记
    含义：谁能看到他们谁能调用？谁能使用？可见性的修饰符：private含义：只有其所在的类可以访问，被修饰的变量但是friend关键字可以让类或者函数成为朋友（友元）可以在别处访问私有成员protected含义：所在的类和层次结构中的所有子类可以访问这些符号例子：classprintable{prot......
  • 10-Hashtable底层结构和源码分析
    10-Hashtable底层结构和源码分析介绍汇总：Hashtable的基本介绍Hashtable底层机制说明Hashtable和HashMap对比1-Hashtable的基本介绍存放的元素是键值对：即K-VHashtable的键和值都不能为null，不然后抛出NullPointerException异常Hashtable使用方法基本上和Hash......
  • 【C++】内存分区模型 - 内存四区
    补充内容：c++编译过程：编译预处理、编译优化、汇编、链接①编译预处理：处理以“#”开头的指令，产生“.i”文件；【如头文件、define宏定义等】②编译优化：将源码".cpp"文件翻译成“.s”汇编代码；【如词法语法语义分析，代码优化等】③汇编：将汇编代码“.s”翻译成机器指令“.o”或".ob......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99