目录
前言
哈喽，小伙伴们大家好，今天我们来学习几个新的容器。这几个容器存储和查找数据效率是非常高的，能达到非常理想的O(1)，这主要因为它们采用了哈希的思想。那么事不宜迟，我们一起来看看吧。
一、unordered系列关联式容器
序列式容器和关联式容器：
c++中容器分为序列式容器和关联式容器。所谓序列容器，就是以线性排列来排列某种类型的数据，比如vect，list，dequene。序列式容器通常只是单纯的用来存储数据。在关联式容器中，加入了键值的概念，关联式容器中保存的都是一个一个的键值对，通过特殊的结构以及键值和目标值的对应关系可以达到快速检索数据，所以关联式容器可以用来存储数据加检索数据。
unordered系列的关联式容器:
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到logN，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，分别是unordered_map和unordered_set，unordered_multimap和unordered_multiset。这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。容器接口这里不做过多介绍，大家可以查阅相关文档，本文将着重介绍一下其底层结构的实现以及使用场景。
二、 底层结构
1、哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
该结构可以满足：
- 插入元素：根据插入元素的关键码，按特定函数计算出一个存储位置，并把元素插入到该位置中。
- 搜索元素：取出要查找元素的关键码，按同样的函数计算出对应的存储位置，既可直接找到该元素。
该方法叫做哈希（散列）方法，用于把关键码和存储位置转换的函数叫做哈希（散列）函数，构造出来的结构叫做哈希（散列）表。
2、哈希冲突
根据哈希搜索方法的要求，我们可以举一个例子。
例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
如图，数据会根据一个固定的函数公式计算映射到相应的位置。但是这样会存在一个问题 ，比如存入数据44，44%10=4，根据函数映射关系需要存储下标为4的位置，但是下标为4的地方早已经存放了别的数据，就会发生冲突。
当两个不同的数据（关键字）a，b，根据哈希函数计算映射到了相同的位置，这种现象称为哈希冲突。
3、哈希函数
引起哈希冲突的一个原因可能是哈希函数设置的不够合理。哈希函数要求计算出来的地址必须包含在哈希表中，并尽可能的均匀分布。
常见哈希函数：
（1）直接定址法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单
缺点：仅仅适用于整数，当数据范围过大时会浪费很多空间
使用场景：适合查找比较小且连续的情况，比如计数排序通常就是用的这种映射方法。
（2）除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
（3）平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
这里主要介绍一些出现频率比较高的，还有很多时候哈希函数是我们根据情况自定义出来的，这里就不一一介绍。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
4、哈希冲突的解决
解决哈希冲突两种常见的方法是：闭散列和开散列。
4.1闭散列
闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
实现方法：
（1）线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入：
- 通过哈希函数获得该元素在哈希表中的位置。
- 如果该位置没有元素则直接插入，如果在该位置发生冲突则使用线性探测向后寻找，找到空位置后再插入。
当空间不够时需要增容，但要注意，在原结构上进行简单的增容会造成数据错乱，比如空间大小由10增到20，拿映射关系也会发生变化。所以需要重新开辟一个哈希表，然后对原数据进行数据拷贝。
删除：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。我们可以创建一个枚举类型来代表元素状态。
//创建一个枚举表示哈希表中数据的三种状态
enum State
{
EMPTY,
EXIST,
DELETE
};插入代码如下：
template <class K, class V, class HashFunc = Hash<K>>
class HashTable
{
public:
bool insert(const pair<K, V>& kv)
{
//如果有了返回空
auto ret = find(kv.first);
if (ret)
{
return false;
}
if (_table.size() == 0)
{
_table.resize(10);
}
//负载因子大于0.7，增容
if ((double)_n / (double)_table.size() > 0.7)
{
HashTable<K,V> newtable;
newtable._table.resize(_table.size() * 2);
for (auto& e : _table)
{
if (e._state == EXIST)
{
newtable.insert(e._kv);
}
}
_table.swap(newtable._table);
}
HashFunc hc;
int start = hc(kv.first) % _table.size();
int index = start;
int i = 1;
while (_table[index]._state == EXIST)
{
index = start + i;
index %= _table.size();
i++;
}
_table[index]._kv = kv;
_table[index]._state = EXIST;
++_n;
return true;
}线性探测优缺点：
- 优点：实现起来很简单
- 缺点：某些连续位置出现冲突，会造成数据踩踏。使得寻找某关键码的位置需要许多次比较，导致搜索效率降低
（2）二次探测
二次探测并不是指探测两次，而是指移动位置的个数平方。线性探测每次探测的位置为冲突位置+i（i不断加1），二次探测每次探测的位置为冲突位置+i^2（i不断加1）。这样每次探测跳跃的距离变大，可以一定程度上避免踩踏。
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任
何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在
搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出
必须考虑增容。
因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
4.2开散列
概念：根据关键码和哈希函数，算出各元素对应的地址，有相同地址的元素组成一个集合，每个集合称为一个桶。把桶中的元素通过单链表连接起来，各链表的头节点存入哈希表中。
开散列中每个桶中存放的都是发生哈希冲突的元素。
开散列增容：
桶的个数是固定的，随着元素的插入，桶中的元素也会随之增多。在极端情况下，可能导致一个桶中的元素非常多，从而影响哈希表的性能。想要减少桶中元素的个数，最好的办法就是增加桶的数量，桶的数量增大发生冲突的概率就小，从而每个桶中的元素个数也会减少。
开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突。所以通常在元素个数等于桶的个数时发生增容。
4.3 开散列和闭散列比较
开散列中元素之间需要通过指针链接，表面上看似乎增加了存储开销。但和闭散列相比，实际上是节省了空间。因为闭散列由于要保证搜索效率，必须保证有大量空间剩余，比如要求载荷因子小于0.7，哈希表空闲部分浪费的空间要远远多于指针。
三、哈希的应用
哈希是一种映射思想，除了哈希表外，哈希还有很多其它用途。
1、位图
1.1 概念
位图通过每一位的值来表示一种状态，通常用来表示一个数据是否存在，适用于处理海量数据。
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
1.2 位图的实现
位图常用的有三个接口，我们模拟实现一下，代码如下：
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 32 + 1);
}
//把x映射的位置标志为1
void set(size_t x)
{
size_t i = x / 32;//计算在vector的第几个数中
size_t j = x % 32;//计算在第几位
_bits[i] |= (0x01 << j);
}
//把x映射的位置标志为0
void reset(size_t x)
{
size_t i = x / 32;//计算在vector的第几个数中
size_t j = x % 32;//计算在第几位
_bits[i] &= ~(0x01 << j);
}
//把x映射的位置标志取出来
bool test(size_t x)
{
size_t i = x / 32;//计算在vector的第几个数中
size_t j = x % 32;//计算在第几位
return _bits[i] &= (0x01 << j);
}
private:
vector<int> _bits;
};1.3 位图应用
（1）给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
答：可以设置A,B两个位图，分别映射标识两个文件中存在的整数，然后把两个位图相与，为1的位映射的数为两个文件交集。
（2）位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整
数
答：一个位图可以代表两种状态，两个位图组合就可以代表四种状态。可以设置A,B两个位图，相同位置的位组合，00代表0次，01代表1次，10代表两次，11代表两次以上，然后根据相应的逻辑关系更改位图的值即可。比如此时拿到了一个整型3，此时发现位图A的对应位置的值为0，位图B对应位置的值为1，代表3之前已经出现了一次，此时要再加一次，令位图A对应位置为1，位图B对应位置为0，即可表示。存储完后遍历两个位图即可找到不超过2次的所有整数。
2、布隆过滤器
2.1 概念
在我们注册游戏用户时，一般要起一个用户名，服务器会快速检索数据库中的大量数据，查看这个用户名有没有被人用过，这是怎么办到的呢？
对大量数据进行检索，通过上面的学习，我们的第一反应应该是使用位图。将每一个用户名当成一个字符串然后再通过某个函数转成整形映射到位图中进行标识，对位图进行检索即可判断该用户名是否有被使用过。这个方法看上去很好，但有一个致命的缺陷，那就是当数据量足够大时候，无论用什么函数转换用户名都会造成冲突（也就是不同的用户名经过转换后变成相同的整形），从而导致发生误判。为了改善这一情况，布隆过滤器被提出，布隆过滤器本质上是对位图的改造升级。
2.2 布隆过滤器实现
既然通过一个函数进行标识容易误判，那么我们只需要多用几个函数进行标识就可以减少误判概率。以字符串为例，我们用三个函数分别对一个字符串进行转换，得到三个整形，分别将位图中三个整形的映射位置标识置为1。当判断数据库中是否有该数据时，只需要看位图对应的三个位置是否都为1，如果都为1则判断为存在，如果有任何一个不为1，则判断不存在。
现在有一个位图：
向位图中插入baidu ：
向位图中插入tencnt， 可以发现，tencent有一个函数与baidu发生了冲突，但由于其它函数没有冲突，tencent依旧可以插入。
2.3 布隆过滤器的查找
分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器说一个数据在表中不存在那这个数据一定不存在，但布隆过滤器说一个数据在表中存在这个数据并不一定存在，因为三个哈希值处的标识可能之前全都被其它数据标识为1。所以使用布隆过滤器的前提是能容忍一定程度的误判。
2.4 布隆过滤器的删除
布隆过滤器一般是不支持删除的，因为布隆过滤器删除一个元素时，会影响到其它元素。
一种支持删除的方法：把布隆过滤器中的每个比特位扩展成一个计数器（比如char类型），每当数据插入时对应的k（k个哈希函数计算出来的k个哈希值，对应k个计数器）个计数器加一。删除数据时把k个计数器中的值减一，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：
- 无法确认元素是否真正在布隆过滤器中。
- 占用空间加大。
- 会造成计数回绕（溢出）。
3、哈希切割
哈希切割指的是当一个文件太大内存装不下时，可以把它切割成一个个小文件，分开处理。下面我们来看两道题：
（1） 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出精确算法。
从题目可以得知，数据量是非常大的，即便使用位图内存也不能满足要求。最简单的方法当然是一点一点的把两个文件中的数据加载到内存中进行比较，但这样做效率是非常低的，时间复杂度为O（N^2），所以这里我们可以采用一种新方法——哈希切割。
哈希切割是指把一个大文件分到多个小文件中去，具体分到多少个小文件中视情况而定。这里假设每个query占20个字节，那每个文件中的数据就有200个G，我们可以创建400个小文件，分别编号A0到A399，通过哈希函数将第一个文件中的数据对应的编号，计算i=Hash（query）%400，然后把这个数据写到i号文件去。同理创建B0到B399个小文件映射第二个文件中的数据。这时候我们找交集只需要比较A[i]和B[i]文件即可了，因为相同的数据对应的文件下标一定是相同的。我们可以把A[i]中的数据都存到map中，再依次取B[i]中的数据进行查找。
注意：哈希切割并不是平均切割，所以小文件的大小不一定满足要求，当某个小文件中存入的值太多导致文件过大时（比如超出1G或者500mb）需要再次切割。
（2）给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
由于需要计数，所以不能使用位图，按照哈希切割的方法，可以创建200个小文件，并把数据映射到对应文件，具体操作和上题类似。相同的值一定会被映射到同一个小文件中，这一点很重要。分别把每个小文件中的值加载到内存中，通过map计算出每个小文件中出现最多的值，并保存下来，然后加载下一个小文件，重复此操作，最后只要比较每个小文件中出现最多值的次数即可。
总结
今天的内容就到这里啦，本文主要简单介绍了哈希思想以及哈希的应用，希望能给大家带来帮助。江湖路远，来日方长，我们下次见~