从零开始的C++（二十）

哈希：

用于unorder_map和unorder_set，其本身是一种思想，即通过一个值利用某种算法去映射到另一个值上。利用哈希思想具体实现的是哈希表。

哈希通常函数：插入和查找

1.插入：用某种算法算出插入值对应的插入下标。

2.查找：利用插入的算法找出待查找的值可能出现的下标。

哈希冲突：

概念：不同的数通过算法计算出的插入下标相同，此时发生哈希冲突。

一般来说数的个数越多越容易发生冲突，有点类似雀巢原理？

解决哈希冲突：

法一：开散列

相同下标的元素放在同一个链表中，此时该链表中所有元素共同为一个桶，每个桶中所有元素彼此哈希冲突。

法二：闭散列

发生哈希冲突时，后插入的元素依次往下标+1、+2...的空闲位置放（线性探测），也也可以往下标+1、下标+4、下标+9...的空闲位置差（二次探测）

哈希扩容：

当插入元素很多时，哈希冲突的概率会越来愈大，为了减少哈希冲突概率，需要扩容。对于开散列，一般在原本链表数组基础上扩容，然后直接将链表上所有元素重新插入。对于闭散列，一般开一份新空间，其长度是原本数组二倍，然后复用插入函数将原数组上的元素拷贝一份放到新空间，后释放原数组，指向新数组。

位图：

一种基于哈希思想的应用，用于海量整形数据的查找、判断是否存在。

原理：每一个数用一个比特位表示是否存在，极大程度减少所占空间。插入时通过一个函数。将整形数据映射到对应比特位上。查找时只需根据函数判断对应比特位是否为1即可。

缺陷：位图只能用于全是整形数据，例如字符串之类的不能使用。

针对位图的缺陷，有了布隆过滤器。

布隆过滤器：

对于字符串，会先通过一个算法转换成对应的一个整形数据，在通过哈希函数找出对应下标（比特位）。

缺陷：虽然可以适用于字符串等非整形类型，但是仍然会有哈希冲突的存在，如不同字符串对应的下标相同。因此只能正确判断字符串不在，无法百分百判断字符串是不是在。（存在误判），因此在查找一个字符串时可以过滤掉不在的数，不能过滤掉可能在的数，因此是过滤器。

布隆过滤器一般无法进行删除，因为不同字符串可能对应同一个下标，若删除可能导致错误。若想要实现删除，需要额外增加一个计数位置，记录当前有几个字符串在此下标，但这样又会额外开辟大量空间。