c++进阶——哈希

本节分为以下几个目标：

1. unordered系列关联式容器

2. 底层结构

3. 模拟实现

4.哈希的应用

5.海量数据处理面试题

一，unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2 N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好 的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是 其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，

测试效率：

int main()
{
	//哈希的效率比红黑稍微好一点。
	const size_t N = 100000;

	unordered_set<int> us;
	set<int> s;

	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N比较大时，重复值比较多
		//v.push_back(rand()+i); // 重复值相对少
		v.push_back(i); // 没有重复，有序
	}

	// 21:15
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;

	size_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;


	size_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << endl;

	size_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	size_t end4 = clock();
	cout << "unordered_set find:" << end4 - begin4 << endl << endl;

	cout << "插入数据个数：" << s.size() << endl;
	cout << "插入数据个数：" << us.size() << endl << endl;

	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;

	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;

	return 0;
}

1，unordered_map

1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与 其对应的value。 2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此 键关联。键和映射值的类型可能不同。

3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内 找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭 代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。 6. 它的迭代器至少是前向迭代器

2，unordered_map的接口说明

unordered_map的构造：

类似于unordered_map<string, string> dict，括号中传first和second值。

unordered_map的容量：

bool empty() const 检测unordered_map是否为空

size_t size() const 获取unordered_map的有效元素个数

.unordered_map的迭代器

begin 返回unordered_map第一个元素的迭代器

end 返回unordered_map最后一个元素下一个位置的迭代器

cbegin 返回unordered_map第一个元素的const迭代器

cend 返回unordered_map最后一个元素下一个位置的const迭代器

unordered_map的元素访问

operator[]?返回与key对应的value，没有一个默认值

?unordered_map的查询

iterator find(const K& key) 返回key在哈希桶中的位置

size_t count(const K& key) 返回哈希桶中关键码为key的键值对的个数

unordered_map的修改操作

insert 向容器中插入键值对

erase 删除容器中的键值对

void clear() 清空容器中有效元素个数

void swap(unordered_map&) 交换两个容器中的元素

unordered_map的桶操作

size_t bucket_count()const 返回哈希桶中桶的总个数

size_t bucket_size(size_t n)const 返回n号桶中有效元素的总个数

size_t bucket(const K& key) 返回元素key所在的桶号

二，底层结构

哈希 & 哈希表：

哈希和哈希表是两个不同概念，哈希是一种映射思想，但是哈希表是一种思想的实现结构

1，?哈希概念

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

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素

简而言之哈希是一种映射，原有的值映射到一张新的表，从而帮助查找。

2，哈希冲突/哈希碰撞

哈希函数设计原则：

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

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

问题：如果对跨度很大的数存储时进行取模存储，会存在摸的值相等的情况，这就是哈希碰撞/冲突。

3，哈希问题的解决

这里可以用闭散列的方式：

但是会存在另外一个问题：

这样存完后如何判断数组里有无值？我删除后如何判断？

解决方法：
定义一个枚举常量记录状态

扩容的代码实现：

bool Insert(const pair<K, V>& kv)
		{
			// 负载因子0.7就扩容
			if (_n*10 / _tables.size() == 7)//异地扩容，控制负载因子
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize);
				// 遍历旧表
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}

				_tables.swap(newHT._tables);
			}

			size_t hashi = kv.first % _tables.size();
			while (_tables[hashi]._s == EXIST)//状态设置
			{
				hashi++;

				hashi %= _tables.size();
			}

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

			return true;
		}

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

4，映射方法

1，直接定址法（关键字范围集中，量不大的情况下）

关键位置和存储位置是一对一的关系，不存在哈希冲突。

2，除留余数法（关键字可以很分散，量可以很大）

关键位置和存储位置是一对多的关系或者多对一

5，闭散列

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

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

6，闭散列哈希的模拟实现

#pragma once
#include<vector>

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

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

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

	// 11:46继续
	//HashFunc<string>
	template<>
	struct HashFunc<string>
	{
		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;
		}
	};

	//struct HashFuncString
	//{
	//	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 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)
				{
					//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<HashData<K, V>> _tables;
		size_t _n = 0; // 存储的关键字的个数
	};

	void TestHT1()
	{
		HashTable<int, int> 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<string, int, HashFuncString> ht;
		HashTable<string, int> ht;
		for (auto& e : arr)
		{
			//auto ret = ht.Find(e);
			HashData<string, int>* 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
{
	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, class V>
	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)
		{
			//....
			return NULL;
		}

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

	//template<class K, class V>
	//class HashTable
	//{
	//	typedef HashNode<K, V> Node;
	//private:
	//	//struct bucket
	//	//{
	//	//	forwad_list<pair<K, V>> _lt;
	//	//	set<pair<K, V>> _rbtree;
	//	//	size_t len = 0; // 超过8，放到红黑树
	//	//};
	//	//vector<bucket> _tables;
	//	//vector<forwad_list<pair<K, V>>> _tables;

	//	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));
	}
}

三，哈希桶

1，概念引入

哈希在线性存储的情况下，冲突是不可避免的，无论负载因子设置的多小，当数据量足够大时必然会造成冲突，那么线性无法解决问题，我们可以换个角度思考，用二维的方式彻底解决哈希冲突。

绝大多数情况下这样查找的时间复杂度是o(1),只有极其特殊或者极端情况下，当大部分元素在一个数组对应的链表中，才会达到o(n^2)，当然这很极端。

2，极端场景的解决措施

以java为例子，如果哈希桶真的出现上输极端情况，那么java的处理方法是：将挂的数字达到临界值的个数后，转化挂链表为挂红黑树。

这样就算极端场景下的时间复杂度也不过0(logn)。

3，字符串哈希

当存入哈希桶的是字符串的时候，哈希桶就没办法很好的存储字符变量，这里为了解决并且区分字符串和整形类型，我们通常使用仿函数的方式：

当哈希桶是整形时：

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)
        {
            // BKDR
            size_t hash = 0;
            for (auto e : key)
            {
                hash *= 31;
                hash += e;
            }

            cout << key << ":" << hash << endl;
            return hash;
        }
    };

但是这样存贮字符串会有一定的问题，举个栗子：

我要存贮"abc" 和 "acb"时，这两个字符串会识别成相同的值，这样会分不清这两个字符串。于是科学家经过大量研究，找出了一些不容易冲突的方式。

各路大佬都有着不同的解决方式，最后有人总结并且统计了各个方法的冲突数：

但是我们至此采用这种方式：

故我们可以得出，如果想要映射到哈希桶，我们尽可能的要将映射量标志成唯一的，如：要映射不同的人进入哈希桶：

我们确定唯一值的方法可以是姓名*班级*专业作为映射值，这样就不容易冲突

4，模拟实现开散列/哈希桶

namespace hash_buckdet
{
	template<class K, class V>
	struct Hash
	{ 

	};



	template<class K, class V>
	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;

			//扩容保证效率
			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];
			_table[hashi] = newnode;
			++_n;
		}

		Node* Find(const K& key)
		{

		}

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