程序员经验分享-hwhale

【C++】哈希（unordered系列关联式容器）

2023-11-01

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

 目录

一、unordered系列的关联式容器

二、unordered系列容器

1、unordered_set

2、unordered_map

三、树形结构和哈希结构插入删除查找性能比较

四、哈希的底层结构

1、哈希结构

2、常见哈希函数

五、闭散列（开放定址法）

1、线性探测

1.1线性探测的插入、查找、删除

1.2线性探测的负载因子（70%-80%）及扩容方式

1.3如何将key值转整型

2、二次探测

六、开散列（拉链法、哈希桶）

1、开散列的概念

2、开散列的负载因子（100%）及扩容方式

七、闭散列和开散列整体代码

八、使用开散列对unordered_set和unordered_map就行封装

1、HashTable.h

2、Unordered_Set.h

3、Unorderer_Map.h

一、unordered系列的关联式容器

        在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到logN，最差情况下也仅需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，unordered系列容器并不是有序的。

        树状关联式容器对key的要求是比较大小，哈希对key的要求是转成整型，用于取模。它们都是通过仿函数来实现的。

二、unordered系列容器

1、unordered_set

        unordered_set并不像set那样支持反向迭代器，它的迭代器底层是一个单向迭代器。 其他功能与set类似。

        unordered_set的插入是无序的，不一定按照插入的顺序进行打印。自带去重功能。

2、unordered_map

单向迭代器+无序。其他功能与map类似。

三、树形结构和哈希结构插入删除查找性能比较

        红黑树的插入删除查找性能都是O(logN)而哈希表的插入删除查找性能理论上都是O(1)，他是相对于稳定的，最差情况下都是高效的。哈希表的插入删除操作的理论上时间复杂度是常数时间的，这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下，哈希表的插入和删除时间复杂度为O(n)。

四、哈希的底层结构

1、哈希结构

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

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

        如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。在哈希表中插入或查找的方法就叫做哈希函数。

2、常见哈希函数

1. 直接定址法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

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

使用场景：适合查找比较小且连续的情况（范围集中）

2. 除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，

按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

缺点：可能会存在哈希冲突（哈希碰撞）

哈希函数：1、闭散列(开放定址法)2、开散列(拉链法/哈希桶)

五、闭散列（开放定址法）

1、线性探测

1.1线性探测的插入、查找、删除

        18模10应将18放在数组下标为8的位置。8模10也应当将8放在数组下标为8的位置，但是这个坑位已经被18占了，此时发生哈希冲突，需要将8放在18的后面，8一直往后找，哪个位置没人就放在哪个位置。

        但是每一个坑位其实有三种状态：坑位为空、坑位不为空、坑位是一个被删除的数据。

        现在需要删除27，只需要找到27并将其状态标志位修改为删除状态即可，并不用真正的清除数据，但要注意的是，27的值还在，我们再次对27进行查找，需要先判断27的标志位，不然27明明删掉了，你还说找到了，那就离谱了。

1.2线性探测的负载因子（70%-80%）及扩容方式

        对于线性探测，是不会让这个数组处于充满的状态，需要控制负载因子保证数组长期处于相对恒定的充满率。

        负载因子=表中有效数据的个数/表的大小。负载因子越大，虽然空间利用率越高，但下一次插入时发生哈希冲突的概率越高！

        如何扩容：因为扩容后，表的大小变大，根据映射公式hashi=key%tablesize，整个数组的映射关系全部被改变，所以扩容时，需要将原有数据一个一个的重新映射进新数组。

1.3如何将key值转整型

size_t hashi = hf(kv.first) % _tables.size();

        哈希的核心就是取模，所以key需要能够被取模。一般来说，哈希的key都是整型或字符串，所以这里写了两个仿函数来将外部类型转换为size_t和string类型。

如果使用其他自定义类型充当key，需要自己仿函数，传入哈希。

template <class K, class V>
struct HashData//存储哈希的数据
{
	std::pair<K, V> _kv;//存储节点的数据
	State _state = EMPTY;//节点的状态
};
template <class K>
struct HashFunc//仿函数，控制hashi取模操作，把相近类型转为整型
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template <>//模板的特化 
struct HashFunc<string>
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;//通过格式计算string的值
		//for (auto& ch : key)//直接相加哈希冲突概率大
		//{
		//	hash += ch;
		//}
		for (auto& ch : key)
		{
			hash = hash * 31 + ch;//也可以乘31,131,1313,13131,131313
		}
		return hash;
	}
};

        对于string类型转整形，不能单纯的使用字符相加的方式进行转换，因为“abc”和“acb”依照字符串相加后的整型值是一样的，这就造成了哈希冲突。下面是一个大佬设计BKDR哈希算法，极大地降低了哈希冲突。

原文链接：各种字符串哈希函数

2、二次探测

        线性探测是start+i(加0，加1，加2，加3)，而二次探测就是start+i^2(加0，加1，加4，加9)

        当然二次探测同样没有从本质上解决问题，还是存在占别人坑位的情况。于是就提出了开散列（哈希桶）。

六、开散列（拉链法、哈希桶）

        unorder系统列的底层用的就是开散列。

1、开散列的概念

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

2、开散列的负载因子（100%）及扩容方式

        官方文档中规定开散列的负载因子是1，负载因子是1的意思是当哈希表的size等于节点数量时，就需要扩容了。

if(_tables.size()==_n)
{
    //HashTable<K, V> newHT;
    //newHT._tables.resize(_tables.size() * 2);
    //for (auto& cur : _tables)//遍历表，不为空说明有桶
    //{
    //	while (cur)
    //	{
    //		依次取出旧表的数据插入新表
    //		newHT.Insert(cur->_kv);
    //		cur = cur->_next;
    //	}
    //}
    //_tables.swap(newHT._tables);
    std::vector<Node*> newtables;
    newtables.resize(2 * _tables.size(), nullptr);//
    for (size_t i = 0; i < _tables.size(); ++i)
    {
        Node* cur = _tables[i];
        while (cur)
        {
            Node* next = cur->_next;
            size_t hashi = Hash()(cur->_kv.first) % newtables.size();
            cur->_next = newtables[hashi];
            newtables[hashi] = cur;
            cur = next;
        }
        _tables[i] = nullptr;//旧表置空。防止析构
    }
    _tables.swap(newtables);
}
~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;
    }
}

        这里是两种扩容写法，注释掉的那一种是把原表的节点拷贝一份插入到新的哈希表，全部元素映射完毕后再交换哈希表。未注释的那种写法是通过修改哈希桶中单链表的指针指向，直接摘取原表元素，同样映射完毕后交换哈希表，没有拷贝构造的过程。不过用的时候记得将原表中的指向置空，否则藕断丝连，原表被交换后会发生析构，因为指向关系没有断，造成刚插入的数据全部被清空。

        为啥闭散列不能必须老老实实的拷贝？因为闭散列中的哈希表存的是值，开散列中存的是节点，节点可以摘下来，值不能摘啊。

        扩容时不一定是两倍，为了一定程度上缓解哈希冲突，stl底层给了扩容的数组大小，均为素数且近似两倍。不过别人拿到你的扩容源码，可以专门设置一组连续冲突的数据来恶心你(比如力扣刷题你用unordered系列。。。)。

        当哈希桶的节点挂载过多时，查找效率逐渐变低，像Java会在哈希桶节点数大于8时，将哈希桶的底层由单链表切换为红黑树。

七、闭散列和开散列整体代码

#pragma once
#include <iostream>
#include <vector>
template <class K>
struct HashFunc//仿函数，控制hashi取模操作，把相近类型转为整型
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template <>//模板的特化 
struct HashFunc < std::string >
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;//通过格式计算string的值
		//for (auto& ch : key)//直接相加哈希冲突概率大
		//{
		//	hash += ch;
		//}
		for (auto& ch : key)
		{
			hash = hash * 31 + ch;//也可以乘31,131,1313,13131,131313
		}
		return hash;
	}
};
namespace closeHash
{
	enum State
	{
		EMPTY,
		EXIST,
		DELTE
	};
	template <class K, class V>
	struct HashData//存储哈希的数据
	{
		std::pair<K, V> _kv;//存储节点的数据
		State _state = EMPTY;//节点的状态
	};
	template <class K, class V, class Hash = HashFunc<K>>//Hash:把key转换为可以取模的整型
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable()
			:_n(10)
		{
			_tables.resize(10);
		}
		bool Insert(const std::pair<K, V>& kv)
		{
			if (Find(kv.first) != nullptr)
				return false;
			//大于标定的负载因子，就扩容
			if (_n * 10 >= 7 * _tables.size())
			{
				HashTable<K, V> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();//找到首先要插入的位置。如果kv.first是string呢？如何取模？
			while (_tables[hashi]._state == EXIST)   //先将string转化为整数，再进行取模操作？应该用仿函数
			{
				++hashi;//线性探测
				hashi %= _tables.size();

			}
			//走到这里就是删除或空
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		Data* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)/
			{
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)//存在且为key
					return &_tables[hashi];
				else
					++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Data* ret = Find(key);
			if (ret != nullptr)
			{
				ret->_state = DELTE;
				--_n;
				return true;
			}
			return false;
		}
	private:
		std::vector<Data> _tables;
		size_t _n = 0;//表中存储的有效数据的个数
	};
	void HashTest()
	{
		HashTable<int, int> ht;
		int a[] = { 18,8,7,27,57,3,38,18 };
		for (auto& e : a)
		{
			ht.Insert(std::make_pair(e, e));
		}
		ht.Insert(std::make_pair(17, 17));
		ht.Insert(std::make_pair(5, 5));

		std::cout << ht.Find(7) << std::endl;
		std::cout << ht.Find(8) << std::endl;
		ht.Erase(7);
		std::cout << ht.Find(7) << std::endl;
		std::cout << ht.Find(8) << std::endl;
	}
}
namespace buckets
{
	template<class K, class V>
	struct HashNode
	{
		std::pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const std::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(__stl_next_prime(0));
		}
		~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 std::pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//负载因子控制在1,超过就扩容
			if(_tables.size()==_n)
			{
				//HashTable<K, V> newHT;
				//newHT._tables.resize(_tables.size() * 2);
				//for (auto& cur : _tables)//遍历表，不为空说明有桶
				//{
				//	while (cur)
				//	{
				//		依次取出旧表的数据插入新表
				//		newHT.Insert(cur->_kv);
				//		cur = cur->_next;
				//	}
				//}
				//_tables.swap(newHT._tables);
				std::vector<Node*> newtables;
				//newtables.resize(2 * _tables.size(), nullptr);//不是2倍扩容
				newtables.resize(__stl_next_prime(_tables.size()), nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = Hash()(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;//旧表置空。防止析构
				}
				_tables.swap(newtables);
			}
			size_t hashi = Hash()(kv.first) % _tables.size();
			//找到插入位置就头插至桶中
			Node* newNode = new Node(kv);
			newNode->_next = _tables[hashi];//_tables[hashi]存的是第一个元素的地址
			_tables[hashi] = newNode;
			++_n;
			return true;
		}
		Node* Find(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first != key)
				{
					cur = cur->_next;
				}
				else
					return cur;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				
				Node* next = cur->_next;
				if (cur->_kv.first == key)
				{
					delete cur;
					if (prev == nullptr)
					{
						_tables[hashi] = next;
					}
					else
					{
						prev->_next = next;
					}
					--_n;
					return true;
				}
				prev = cur;
				cur = next;
			}
			return false;
		}
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (int i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return __stl_prime_list[__stl_num_primes - 1];//否则返回设定的最大值，够用了
		}
	private:
		std::vector<Node*> _tables;//需要写析构,释放单链表的节点
		size_t _n = 0;
	};
	void HashTest()
	{
		HashTable<int, int> ht;
		int a[] = { 18,8,7,27,57,3,38,18 ,17,88,38,28,48 };
		for (auto& e : a)
		{
			ht.Insert(std::make_pair(e, e));
		}
		ht.Insert(std::make_pair(5, 5));
		ht.Erase(5);
	}
}

八、使用开散列对unordered_set和unordered_map就行封装

1、HashTable.h

#pragma once
#include <iostream>
#include <vector>
template <class K>
struct HashFunc//仿函数，控制hashi取模操作，把相近类型转为整型
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template <>//模板的特化 
struct HashFunc < std::string >
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;//通过格式计算string的值
		//for (auto& ch : key)//直接相加哈希冲突概率大
		//{
		//	hash += ch;
		//}
		for (auto& ch : key)
		{
			hash = hash * 31 + ch;//也可以乘31,131,1313,13131,131313
		}
		return hash;
	}
};
namespace closeHash
{
	enum State
	{
		EMPTY,
		EXIST,
		DELTE
	};
	template <class K, class V>
	struct HashData//存储哈希的数据
	{
		std::pair<K, V> _kv;//存储节点的数据
		State _state = EMPTY;//节点的状态
	};
	template <class K, class V, class Hash = HashFunc<K>>//Hash:把key转换为可以取模的整型
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable()
			:_n(10)
		{
			_tables.resize(10);
		}
		bool Insert(const std::pair<K, V>& kv)
		{
			if (Find(kv.first) != nullptr)
				return false;
			//大于标定的负载因子，就扩容
			if (_n * 10 >= 7 * _tables.size())
			{
				HashTable<K, V> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();//找到首先要插入的位置。如果kv.first是string呢？如何取模？
			while (_tables[hashi]._state == EXIST)   //先将string转化为整数，再进行取模操作？应该用仿函数
			{
				++hashi;//线性探测
				hashi %= _tables.size();

			}
			//走到这里就是删除或空
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		Data* Find(const K& key)
		{
			Hash hf;
			//size_t hashi = hf(key) % _tables.size();
            size_t starti=hashi;
			while (_tables[hashi]._state != EMPTY)/
			{
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)//存在且为key
					return &_tables[hashi];
				else
					++hashi;
				hashi %= _tables.size();
                //极端场景下，没有空，全是存在或删除状态
                if(hashi==starti)
                {
                    break;
                }
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Data* ret = Find(key);
			if (ret != nullptr)
			{
				ret->_state = DELTE;
				--_n;
				return true;
			}
			return false;
		}
	private:
		std::vector<Data> _tables;
		size_t _n = 0;//表中存储的有效数据的个数
	};
	void HashTest()
	{
		HashTable<int, int> ht;
		int a[] = { 18,8,7,27,57,3,38,18 };
		for (auto& e : a)
		{
			ht.Insert(std::make_pair(e, e));
		}
		ht.Insert(std::make_pair(17, 17));
		ht.Insert(std::make_pair(5, 5));

		std::cout << ht.Find(7) << std::endl;
		std::cout << ht.Find(8) << std::endl;
		ht.Erase(7);
		std::cout << ht.Find(7) << std::endl;
		std::cout << ht.Find(8) << std::endl;
	}
}
namespace buckets
{
	template<class T>
	struct HashNode
	{
		//std::pair<K, V> _kv;
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
		
	};  
	//哈希表引用迭代器，迭代器引用哈希表的类型，相互引用，需要先前置声明
	template <class K, class T, class Hash, class KeyOfT>
	class HashTable;
	template <class K, class T, class Hash, class KeyOfT>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Hash,KeyOfT> Self;
		typedef HashTable<K, T, Hash, KeyOfT> HT;
		Node* _node;
		HT* _ht;
		__HTIterator(Node* node,HT* ht)
			:_node(node)
			,_ht(ht)
		{}
		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else//当前桶走完了，需要找下一个桶
			{
				KeyOfT kot;
				Hash hash;
				size_t hashi = hash(kot(_node->_data))%(_ht->_tables.size());//等价于Hash()(KeyOfT()(_node->_data))
				++hashi;//因为迭代器++是找下一个元素，这个桶走完了，跳过当前hashi
				while (hashi<_ht->_tables.size())//如果hashi没越界
				{
					if (_ht->_tables[hashi]) //哈希表不为空
					{
						_node = _ht->_tables[hashi];
						break;
					}
					++hashi;
				}
				//说明没有桶了，找完了找不到
				if (hashi == _ht->_tables.size())
					_node = nullptr;
			}
			return *this;
		}
		T& operator*()
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &(_node->_data);
		}
		bool operator!=(const Self& it)const
		{
			return _node != it._node;
		}
		
	};
	template <class K, class T, class Hash,class KeyOfT>
	class HashTable
	{
		template <class K, class T, class Hash, class KeyOfT>
		friend struct __HTIterator;
		typedef HashNode<T> Node;
	public:
		typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i] != nullptr)
					return iterator(_tables[i], this);
			}
			return iterator(nullptr, this);
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		HashTable()
			:_n(0)
		{
			_tables.resize(__stl_next_prime(0));
		}
		~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;
			}
		}
		std::pair<iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			iterator it = Find(kot(data));
			if (it!=end())//说明找到了相同元素。返回false
				return std::make_pair(it,false);
			//负载因子控制在1,超过就扩容
			if(_tables.size()==_n)
			{
				//HashTable<K, V> newHT;
				//newHT._tables.resize(_tables.size() * 2);
				//for (auto& cur : _tables)//遍历表，不为空说明有桶
				//{
				//	while (cur)
				//	{
				//		依次取出旧表的数据插入新表
				//		newHT.Insert(cur->_kv);
				//		cur = cur->_next;
				//	}
				//}
				//_tables.swap(newHT._tables);
				std::vector<Node*> newtables;
				//newtables.resize(2 * _tables.size(), nullptr);//不是2倍扩容
				newtables.resize(__stl_next_prime(_tables.size()), nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = Hash()(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;//旧表置空。防止析构
				}
				_tables.swap(newtables);
			}
			size_t hashi = Hash()(kot(data)) % _tables.size();
			//找到插入位置就头插至桶中
			Node* newNode = new Node(data);
			newNode->_next = _tables[hashi];//_tables[hashi]存的是第一个元素的地址
			_tables[hashi] = newNode;
			++_n;
			return std::make_pair(iterator(newNode,this),true);
		}
		iterator Find(const K& key)
		{
			KeyOfT kot;
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) != key)
				{
					cur = cur->_next;
				}
				else
					return iterator(cur,this);
			}
			return iterator(nullptr,this);
		}
		bool Erase(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				
				Node* next = cur->_next;
				if (cur->_kv.first == key)
				{
					delete cur;
					if (prev == nullptr)
					{
						_tables[hashi] = next;
					}
					else
					{
						prev->_next = next;
					}
					--_n;
					return true;
				}
				prev = cur;
				cur = next;
			}
			return false;
		}
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (int i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return __stl_prime_list[__stl_num_primes - 1];//否则返回设定的最大值，够用了
		}
	private:
		std::vector<Node*> _tables;//需要写析构,释放单链表的节点
		size_t _n = 0;
	};
	/*void HashTest()
	{
		HashTable<int, int> ht;
		int a[] = { 18,8,7,27,57,3,38,18 ,17,88,38,28,48 };
		for (auto& e : a)
		{
			ht.Insert(std::make_pair(e, e));
		}
		ht.Insert(std::make_pair(5, 5));
		ht.Erase(5);
	}*/
}

2、Unordered_Set.h

#pragma once
#include "HashTable.h"
namespace jly
{
	template <class K, class Hash= HashFunc<K>>//K:key;Hash:将key转为整型的仿函数
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename buckets::HashTable<K, K,Hash, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		iterator Find(const K& key)
		{
			return _ht.Find(key);
		}
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
		std::pair<iterator, bool> Insert(const K& data)
		{
			return _ht.Insert(data);
		}

	private:
		buckets::HashTable<K, K,Hash,SetKeyOfT> _ht;
	};
	void test_unordered_set()
	{
		unordered_set<int> us;
		us.Insert(3);
		us.Insert(13);
		us.Insert(23);
		us.Insert(5);
		us.Insert(5);
		us.Insert(6);
		us.Insert(106);
		us.Insert(53);

		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			std::cout << *it << " ";
			++it;
		}
		std::cout << std::endl;
		for (auto& e : us)
		{
			std::cout << e << " ";
		}
	}
}

3、Unorderer_Map.h

#pragma once
#include "HashTable.h"
namespace jly
{

	template <class K, class V,class Hash = HashFunc<K>>//Hash:将key转为整型的仿函数
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const std::pair<const K, V>& kv)
			{
				return kv.first;
			} 
		};
	public:
		typedef typename buckets::HashTable<K, std::pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
		std::pair<iterator,bool> Insert(const std::pair<K, V>& data)
		{
			return _ht.Insert(data);
		}
		V& operator[](const K& key)
		{
			std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));
			return  ret.first->second;

		}
		iterator Find(const K& key)
		{
			return _ht.Find(key);
		}
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
	private:
		buckets::HashTable<K, std::pair<const K,V>,Hash, MapKeyOfT> _ht;
	};
	void test_unordered_map()
	{
		std::string arr[] = { "牛奶", "水罐", "冰", "牛奶", "冰", "水罐", 
			"冰", "冰", "冰", "木头", "冰", "木头" };

		unordered_map<std::string, int> countMap;
		for (auto& e : arr)
		{
			countMap[e]++;
		}

		for (const auto& kv : countMap)
		{
			std::cout << kv.first << ":" << kv.second << std::endl;
		}
	}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

哈希算法

算法

散列表

【C++】哈希（unordered系列关联式容器） 的相关文章

  • 创建 DirectoryEntry 实例以供测试使用

    我正在尝试创建 DirectoryEntry 的实例 以便可以使用它来测试将传递 DirectoryEntry 的一些代码 然而 尽管进行了很多尝试 我还是找不到实例化 DE 并初始化它的 PropertyCollection 的方法 我有

  • Signalr 在生产服务器中总是陷入长轮询

    当我在服务器中托管应用程序时 它会检查服务器端事件并始终回退到长轮询 服务器托管环境为Windows Server 2012 R1和IIS 7 5 无论如何 我们是否可以解决这个问题 https cloud githubuserconten

  • Cygwin 下使用 CMake 编译库

    我一直在尝试使用 CMake 来编译 TinyXML 作为一种迷你项目 尝试学习 CMake 作为补充 我试图将其编译成动态库并自行安装 以便它可以工作 到目前为止 我已经设法编译和安装它 但它编译成 dll 和 dll a 让它工作的唯一

  • 如何在我的应用程序中使用 Windows Key

    Like Windows Key E Opens a new Explorer Window And Windows Key R Displays the Run command 如何在应用程序的 KeyDown 事件中使用 Windows

  • 跨多个控件共享事件处理程序

    在我用 C 编写的 Windows 窗体应用程序中 我有一堆按钮 当用户的鼠标悬停在按钮上时 我希望按钮的边框发生变化 目前我有以下多个实例 每个按钮一个副本 private void btnStopServer MouseEnter ob

  • 将字符串从非托管代码传递到托管

    我在将字符串从非托管代码传递到托管代码时遇到问题 在我的非托管类中 非托管类 cpp 我有一个来自托管代码的函数指针 TESTCALLBACK FUNCTION testCbFunc TESTCALLBACK FUNCTION 接受一个字符

  • c# Asp.NET MVC 使用FileStreamResult下载excel文件

    我需要构建一个方法 它将接收模型 从中构建excel 构建和接收部分完成没有问题 然后使用内存流导出 让用户下载它 不将其保存在服务器上 我是 ASP NET 和 MVC 的新手 所以我找到了指南并将其构建为教程项目 public File

  • Windows 窗体不会在调试模式下显示

    我最近升级到 VS 2012 我有一组在 VS 2010 中编码的 UI 测试 我试图在 VS 2012 中启动它们 我有一个 Windows 窗体 在开始时显示使用 AssemblyInitialize 属性运行测试 我使用此表单允许用户

  • 编译的表达式树会泄漏吗？

    根据我的理解 JIT 代码在程序运行时永远不会从内存中释放 这是否意味着重复调用 Compile 表达式树上会泄漏内存吗 这意味着仅在静态构造函数中编译表达式树或以其他方式缓存它们 这可能不那么简单 正确的 他们可能是GCed Lambda

  • 使用 LINQ 查找列表中特定类型的第一个元素

    使用 LINQ 和 C 在元素列表中查找特定类型的第一个项目的最短表示法是什么 var first yourCollection OfType

  • 是否有比 lex/flex 更好（更现代）的工具来生成 C++ 分词器？

    我最近将源文件解析添加到现有工具中 该工具从复杂的命令行参数生成输出文件 命令行参数变得如此复杂 以至于我们开始允许它们作为一个文件提供 该文件被解析为一个非常大的命令行 但语法仍然很尴尬 因此我添加了使用更合理的语法解析源文件的功能 我使

  • 初始化变量的不同方式

    在 C 中初始化变量有多种方法 int z 3 与 int 相同z 3 Is int z z 3 same as int z z 3 您可以使用 int z z 3 Or just int z 3 Or int z 3 Or int z i

  • Windows 10 中 Qt 桌面应用程序的缩放不当

    我正在为 Windows 10 编写一个简单的 Qt Widgets Gui 应用程序 我使用的是 Qt 5 6 0 beta 版本 我遇到的问题是它根本无法缩放到我的 Surfacebook 的屏幕上 这有点难以判断 因为 SO 缩放了图

  • 像“1$”这样的位置参数如何与 printf() 一起使用？

    By man I find printf d width num and printf 2 1 d width num 是等价的 但在我看来 第二种风格应该与以下相同 printf d num width 然而通过测试似乎man是对的 为什

  • 在 URL 中发送之前对特殊字符进行百分比编码

    我需要传递特殊字符 如 等 Facebook Twitter 和此类社交网站的 URL 为此 我将这些字符替换为 URL 转义码 return valToEncode Replace 21 Replace 23 Replace 24 Rep

  • 在Linux中使用C/C++获取机器序列号和CPU ID

    在Linux系统中如何获取机器序列号和CPU ID 示例代码受到高度赞赏 Here http lxr linux no linux v2 6 39 arch x86 include asm processor h L173Linux 内核似

  • 如何在 C# 中播放在线资源中的 .mp3 文件？

    我的问题与此非常相似question https stackoverflow com questions 7556672 mp3 play from stream on c sharp 我有音乐网址 网址如http site com aud

  • 如何将字符串“07:35”(HH:MM) 转换为 TimeSpan

    我想知道是否有办法将 24 小时时间格式的字符串转换为 TimeSpan 现在我有一种 旧时尚风格 string stringTime 07 35 string values stringTime Split TimeSpan ts new

  • 将 viewbag 从操作控制器传递到部分视图

    我有一个带有部分视图的 mvc 视图 控制器中有一个 ActionResult 方法 它将返回 PartialView 因此 我需要将 ViewBag 数据从 ActionResult 方法传递到 Partial View 这是我的控制器

  • 不同类型的指针可以互相分配吗？

    考虑到 T1 p1 T2 p2 我们可以将 p1 分配给 p2 或反之亦然吗 如果是这样 是否可以不使用强制转换来完成 或者我们必须使用强制转换 首先 让我们考虑不进行强制转换的分配 C 2018 6 5 16 1 1 列出了简单赋值的约束

随机推荐

热门标签