C++ unordered_map和unordered_set的使用，哈希表的实现

文章目录

unordered_map，unorder_set和map ，set的差异
哈希表的实现
- 概念
- 直接定址法
- 哈希冲突
- - 哈希冲突举个例子
- 负载因子
- 将关键字转为整数
- 哈希函数
- - 除法散列法/除留余数法
- 哈希冲突的解决方法
- - 开放定址法
  - - 线性探测
    - 二次探测
- 开放定址法代码实现
哈希表的代码

unordered_map，unorder_set和map ，set的差异

unordered_map，unordered_set在功能方面和map，set基本一致
unordered_map和unordered_set底层是哈希表，遍历无序，查找删除修改的效率为O(1)
map和set底层是红黑树，遍历有序，查找删除修改的效率为O(logN)

功能：迭代器之间也有差异，set是双向迭代器，unordered_set是单向迭代器，set底层是红黑树，走中序是有序的，所以迭代器的遍历是有序+去重，unordered_set底层是哈希表，迭代器遍历是无序+去重
效率：unordered_set和set性能方面也有差异，set是O(logN),unordered_set是O(1)
使用要求：对key的要求不同，set要求key支持小于的比较，unordered_set要求key转为整形且要支持等于的比较
unordered_set,unordered_map和map,set要求基本一致
unordered_multimap和unordered_multiset支持键值冗余（key冗余）
效率上无序的比有序的总体上要好很多，但是在排有序的数的时候，有序的删除，插入比无序的效率高，但是查找效率还是无序的效率高

void set_test1()
{
    // 迭代器遍历
	set<int> s = { 3,1,6,7,8,2};
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	// 3 1 6 7 8 2
	cout << endl;
}

int main()
{
	set_test1();

	return 0;
}

哈希表的实现

概念

哈希表也叫散列表，散列有散乱排列的意思。通过关键字Key跟存储位置建立一个映射关系

直接定址法

适合关键字的范围比较集中的，直接定址法是非常高效的方法。比如给’a’ - 'z’的小写字母为范围，通过直接映射或相对映射，关键字的值就是存储位置的下标，下面也有一道题是这样的。只适合整形，字符串，浮点数都不行

字符串中的第一个唯一字符

class Solution 
{
public:
    int firstUniqChar(string s) 
    {
        int hash[26] = {0};

        for(auto ch : s)
        {
            hash[ch - 'a']++;
        }    

        for(int i = 0;i < s.size();i++)
        {
            if(hash[s[i] - 'a'] == 1)
            return i;
        }

        return -1;
    }
};

哈希冲突

直接定址法的缺点非常明显，当关键字比较分散时，会浪费空间甚至空间会不够用。当有N个值要映射到M个空间中（M >= N），就要借助哈希函数，关键字key要放到数组的h(key）的位置，h(key)计算的值要在[0,M)中。
哈希冲突也叫哈希碰撞，就是两个不同的key映射到同一个位置了，我们要设计一个哈希函数来减少哈希冲突，在实际问题中哈希冲突是不可避免的

哈希冲突举个例子

N == 100 M == 200,N个数要存到M个空间中
除法散列法：h(key) = key % M
哈希冲突：3 % 200 = 3，203 % 200 = 3

负载因子

哈希表中已经存了N个值，哈希表的大小为M,负载因子 = N/M,负载因子也叫装载因子/载荷因子，负载因子越大，哈希冲突越高，空间利用率越高，相反就越低。

将关键字转为整数

比如是浮点数转为整数或者有符号的整数（负数）要转为正数，字符串转为整数。

哈希函数

一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。

除法散列法/除留余数法

除法散列表是最常用的，哈希表的大小为M,通过key除以M的余数作为映射的下标，h(key) = key % M
使用这个方法时要注意M不要为2的幂，10的幂等。如果是2^X，那么key%2 ^ X,相当于保留key的后X位，那么key的后X位相同的值就哈希冲突了。
比如63,31，如果M是16，2 ^ 4,计算出的哈希值都是15，00111111为63，00011111为31，后4位都是1111，所以会哈希冲突。10进制的，比如123和345123，如果M = 10 ^ 3,保留后三位，都是123,也哈希冲突。
当使用除留余数法时，建议M取不太接近2的整数次幂的一个质数
%其实用到了除，除的效率比位运算的效率更低，所以Java中用了位运算

Java中用了2的整数次幂作为哈希表的大小M
在这里插入图片描述

哈希冲突的解决方法

开放定址法

开放定址法，哈希表是空的，把所有元素放到哈希表中，当关键字key用哈希函数找到了冲突位置，就按照某种规则去找一个没有存储数据的位置进行储存。这里有三种规则：线性探测，二次探测，双重探测

线性探测

现在给一组数据：
{19,30,5,36,13,20,21,12} 等这一组值映射到M=11的表中

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，
h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1
在这里插入图片描述
上面这组数据在8位置就冲突了

线性探测：从发生冲突的位置依次往后探测，直到找到一个没有存储数据的位置为止，如果走到哈希尾都没有找到，则回绕到哈希头继续往后找
h(key) = hash0 = key % M , hash0位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M， i = {1, 2, 3, …, M − 1}，因为负载因子必须小于1（因为要留一个位置不放数据，不然会出问题），则最多探测M-1次，一定能找到一个存储key的位置。
连续冲突：hash0位置连续冲突，（你占我的位置，我占你的位置）这种现象叫做群集/堆积，二次探测可以改善这样的问题

二次探测

二次探测和线性探测非常类似
如果往左走回绕到哈希表尾，用减，比如3-9，到5的位置停下，-6 + M,M == 11, -6 + M = 5
在这里插入图片描述

// 二次探测
int flag = 1;
while (_tables[hashi]._state == EXIST)
{
	// 存在进行二次探测,删除和空就退出
	hashi = (hash0 + i*i*flag) % _tables.size();
	if (hashi < 0)
		hashi += _tables.size();

	if (flag == 1)
	{
		flag = -1;
	}
	else
	{
		flag = 1;
		++i;
	}
}

开放定址法代码实现

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，
h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1
蓝色的四个位置连续冲突在这里插入图片描述
查找的原则：遇到删除，存在才继续找，遇到空就结束查找
状态标识：存在，空和删除，空和删除可以放值，空就线性探测
要注意给每个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。
如下图，我们删除30，会导致查找20失败，当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE} ，删除30就可以不用删除值，而是把状态改为 DELETE ，那么查找20时是遇到 EMPTY 才能停止，就可以找到20。

哈希表的代码

#pragma once

#include<vector>

// 枚举状态
enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K,class V>
class HashTable
{
public:
	// 构造
	HashTable()
		// 会取到53
		:_tables(__stl_next_prime(0)),// 11是数据个数()
		_n(0)
	{
	}

	// 为了解决M是质数的问题
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		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
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		// lower_bound取表中大于等于first的数
		return pos == last ? *(last - 1) : *pos;
	}

	// 插入
	bool Insert(const pair<K, V>& kv)
	{
		// 不支持冗余
		if (Find(kv.first))
		{
			return false;
		}

		// 负载因子大于等于0.7就扩容
		if (_n * 10 / _tables.size() >= 7)
		{
			// 扩容
			//vector<HashTable<K, V>> newtables(_tables.size()*2);
			//for (auto& data : _tables)
			//{
			//	// 把旧表的数据映射到新表
			//	// 不能直接拷贝,因为映射关系还是原来的(会乱)
			//	if (data._state == EMPTY)
			//	{
			//		size_t hash0 = data._kv.first % newtables.size();
			//		// ...
			//	}
			//}

			//_tables.swap(newtables);

			// 上面的方法代码过于冗余

			// 把新表和旧表交换
			HashTable<K, V> newht;
			// newht._tables.resize(_table.size() * 2);
			newht._tables.resize(__stl_next_prime(_table.size()));

			for (auto& data : _tables)
			{
				// 把旧表的数据映射到新表
				if (data._state == EMPTY)
				{
					// 相当于递归
					newht.Insert(data._kv);
				}
			}
			// 函数结束,newht销毁,数据交换给旧表
			_tables.swap(newht._tables);
		}

		// key / M , M哈希表的空间大小
		size_t hash0 = kv.first % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state == EXIST)
		{
			// 存在进行线性探测,删除和空就退出
			hashi = (hash0 + i) % _tables.size();
			++i;

		}

		// 二次探测
		//int flag = 1;
		//while (_tables[hashi]._state == EXIST)
		//{
		//	// 存在进行二次探测,删除和空就退出
		//	hashi = (hash0 + i*i*flag) % _tables.size();
		//	if (hashi < 0)
		//		hashi += _tables.size();

		//	if (flag == 1)
		//	{
		//		flag = -1;
		//	}
		//	else
		//	{
		//		flag = 1;
		//		++i;
		//	}
		//}

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

		return true;
	}

	// 查找
	HashData<K, V>* Find(const K& key)
	{
		size_t hash0 = key % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		// Find等于空就找不到了
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state == EXIST
				&& _tables[hashi]._kv.first == key)
			{
				return &_tables[hashi];
			}

			// 存在进行线性探测,删除和空就退出
			hashi = (hash0 + i) % _tables.size();
			++i;
		}

		return nullptr;
	}

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

private:
	vector<HashData<K, V>> _tables;
	size_t _n;// 记录哈希表中的数据个数
};

#include"HashTable.h"

int main()
{
	int a[] = { 19,30,5,36,13,20,21,12 };
	HashTable<int, int> ha;

	for (auto& e : a)
	{
		ha.Insert({ e,e });
	}

	ha.Erase(20);
	if (ha.Find(30))
	{
		cout << "找到了" << endl;
	}

	if (ha.Find(20))
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "没有找到" << endl;
	}

	return 0;
}