STL容器之哈希的补充——其他哈希问题

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映射的哪个标记映射成为1void set(size_t x){size_t i = x / 32;size_t j = x % 32;a_[i] |= (1 << j); // 小端机，开头就是低位，所以直接左移j位}// 将x映射的哪个标记映射成为0void 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));elsehash ^= (~((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_;};
}