1.其他哈希问题
减少了空间的消耗；
1.1位图
位图判断在不在的时间复杂度是O(1)，速度特别快;
使用哈希函数直接定址法，1对1映射；
对于海量的数据判断在不在的问题，使用之前的一些结构已经无法满足，空间消耗过于严重，位图则可以较好的解决此问题；
对于bit位的改变除了位运算就是位段；
1.1.2位图结构的实现
小端机与我们看数据的顺序相反，几个数据连续存储从低地址到高地址，低位-高位，低位-高位。
namespace Bitset
{
template <size_t N>//无符号整数42亿9千万，需要每个整数用一个bit位来标识在不在，大约500兆
class BitSet
{
public:
// 用构造函数开空间
BitSet()
{
a_.resize(N / 32 + 1);
}
public:
// 将x映射的哪个标记映射成为1
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
a_[i] |= (1 << j); // 小端机，开头就是低位，所以直接左移j位
}
// 将x映射的哪个标记映射成为0
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
a_[i] &= (~(1 << j));
}
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return a_[i] & (1 << j);
// if (a_[i] & (1 << j))
// {
// std::cout << "存在" << std::endl;
// return true;
// }
// else
// {
// std::cout << "不存在" << std::endl;
// return false;
// }
}
private:
std::vector<int> a_;
};
}
1.1.3库里面对于位图结构的实现
1.1.4位图的扩展
1.100亿个整数，设计算法找到只出现一次的数，
思路1：使用两个比特位组合，来表示没有出现，出现一次和出现两次及以上；
思路2：使用2个位图，对应位置组合使用；
2.两个文件分别有100亿整数，1g内存找交集；
1.1.5位图的应用
1.快速查找某个数据是否在一个集合中
2.排序 + 去重
3.两个集合的交集、并集等
4.操作系统中磁盘块标记
1.2布隆过滤器
作用：过滤掉确定性的数据，降低数据库的查询负载压力；对于不确定的数据，降低误判率；
使用除留余数法，产生多对一，对于整型可以使用位图来实现，对于字符串是先对应一个整数，但是不可能无限扩容，会存在双重哈希冲突，对于存在可能误判，是不准确的，而对于不存在一定是准确的；
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
使用布隆过滤器可以减少误判率；一个值映射位图的多个位置，如果多个位置都为1，才能说明在；就像是现实生活中，信息越多描述就更准确；
1.2.1应用场景
1.不需要精确的场景，即使用降低误判的特性：比如快速判断昵称是否被使用过，将昵称存放到一个布隆过滤器里面，存在误判，但是可以接受，比如用户知道昵称不可用就会自动用其他昵称，不会产生巨大的问题；
2.需要精确的场景，即使用不存在是准确的特性，昵称不存在快速响应，昵称存在去数据库进行查找，可以起到过滤一部分确定数据的效果；
3.布隆过滤器不仅可以过滤字符串，也可以针对其他类型；
1.2.2布隆过滤器模拟实现
偶数用位运算表示，n&1==0，就是偶数；
使用不同的哈希算法得到不同的整数映射，多对一的映射减少了误判，同时也带来了空间上的消耗空间减少也会增加误判的机率；
一般不允许使用reset，否则会影响很多映射，即多对一使得关联度增加了，一个修改就会影响另一个，可以使用引用计数的方法，同时还需要多开空间存计数，这样就可以保护数据。
namespace Bloomfilter
{
struct BKDR
{
size_t operator()(const std::string &str)
{
size_t i = 0;
for (const auto &e : str)
{
i *= 131;
i += e;
}
return i;
}
};
struct AP
{
size_t operator()(const std::string &str)
{
size_t hash = 0;
for (size_t i = 0; i < str.size(); i++)
{
size_t ch = str[i];
if ((i & 1) == 0)
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
else
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
return hash;
}
};
struct DJB
{
size_t operator()(const std::string &str)
{
size_t hash = 5381;
for (auto ch : str)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template <size_t N, class K = std::string, class Hash1 = BKDR, class Hash2 = AP, class Hash3 = DJB> // 可以使用BKDR算法
class BloomFilter
{
public:
void set(const K &key)
{
size_t hash1 = BKDR()(key) % N;
bf_.set(hash1);
size_t hash2 = AP()(key) % N;
bf_.set(hash2);
size_t hash3 = DJB()(key) % N;
bf_.set(hash3);
}
bool test(const K &key)
{
size_t hash1 = BKDR()(key) % N;
if (bf_.test(hash1) == false)
{
return false;
}
size_t hash2 = AP()(key) % N;
if (bf_.test(hash2) == false)
{
return false;
}
size_t hash3 = DJB()(key) % N;
if (bf_.test(hash3) == false)
{
return false;
}
return true; // 存在误判
}
private:
// 私有成员
std::bitset<N> bf_;
};
}
1.2.3哈希函数个数和布隆过滤器长度的选择
k为哈希函数的个数，m为布隆过滤器的长度，n为插入元素的个数，这样可以使得误判率相对较低；
1.2.4布隆过滤器优缺点
优点：
1.增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 ；
2.哈希函数相互之间没有关系，方便硬件并行运算 ；
3.布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势；
4.在能够承受一定的误判时，布隆过滤器比其他数据结构有着很大的空间优势 ；
5.数据量很大时，布隆过滤器可以表示全集，其他数据结构不能 ；
6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算 ；
缺点：
1.有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据) ；
2.不能获取元素本身 ；
3.一般情况下不能从布隆过滤器中删除元素 ；
4.如果采用计数方式删除，可能会存在计数回绕问题 ；
8.2.5布隆过滤器的扩展
1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出
精确算法和近似算法 ；
2.如何扩展BloomFilter使得它支持删除元素的操作 ；
1.3哈希切割
问题：1.将大文件切割是因为在磁盘中查找太慢，应载入内存查找；2.平均切分要查询的key在每个小文件中都可能存在，都得查找一次；
而是用哈希切割，将大文件进行切割，切割成N份，用哈希算法将查询字符串映射成整数，然后%N，最后得到的映射值i就是被切割的第i个小文件；这样就可以根据编号进行查找，不用遍历所有的小文件；
原理是：存在哈希冲突映射了错误的值，但是正确的值一定在这个位置对应的小文件，使得范围大幅度减少；即过滤很大一批无效数据；
1.3.1哈希切割应用
1.哈希切割解决大文件找交集；
哈希切分后还可能某一个小文件过大；文件过大可能是1.大多数query冲突；2.大多数query相同，部分冲突；
对于小文件过大的解决方法：1.set去重，如果成功说明有大量相同数据，这样文件就小了，如果失败抛异常，则对此文件，使用其他哈希函数进行二次哈希切分，这样文件也小了；
2.最大/topk问题
哈希切割完，用map统计次数，然后用另一个值记录最大的值，清理map遍历其他小文件，更新最大值；
如果是topk就建立一个k个值的小堆，插入k个较大值然后不断更新；
补充：CPU的高速缓存与内存和磁盘间的局部性原理的预加载机制
CPU高速缓存是，内存会将一段数据先加载到cache中，CPU会向cache进行读取，存在缓存命中问题；
局部性原理的预加载机制是，内存磁盘读取都是按照一定的大小进行的，这样就可以一次性读到多个数据；