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映射的哪个标记映射成为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_;
    };
}