【C++进阶】哈希的应用 --- 布隆过滤器

在这里插入图片描述

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：C++航路
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎评论💬 点赞👍🏻 收藏 📂 加关注✨

一、问题引入

随着玩王者荣耀的用户越来越多，想要取一个心悦的名字是非常难的。当名字重复的时候，系统非常快的提示“名字已被使用”，那么它是如何做到快速查找名字是否被使用了呢？

在这里插入图片描述

在如此大的数据下，首先可以想到使用位图：

但由于位图的数据必须是size_t的，那么需要先将名字（字符串）映射成整型，然后再存入位图中。然而，我们对位图开空间是根据数据范围的，但字符串的长度是可变的，使用位图来表示长度不固定的数据会带来很大的挑战。比如，开少了可能引发冲突，那么就会导致误判。比如说李白和百里都占同一个比特位并且都标记成1，当有人将修改了百里这一名称，那么其实就是reset操作，那么，李白也同样会被reset，那么就会有第二个人可以取李白这个名字。
并且字符串在计算机中是以字符集编码的方式存储的，一个字符可能由一个或多个字节组成。而位图一般用于表示集合中元素的存在与否，对于字符集编码来说，字符的种类和编码范围非常广泛，使用位图来表示所有可能的字符将需要非常大的存储空间，并且不实际。

这时候就需要我们本文中的主角： 布隆过滤器Bloomfilter

二、布隆过滤器的概念

布隆过滤器是由布隆在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询。可以用来告诉你 “某样东西一定不存在或者可能存在”

布隆过滤器是如何做到的呢？

这里举一个小故事：假设布隆有一天要去线下见网友，前提是他不知道网友的任何特征，那怎么办？只能发一个消息问对方今天的穿搭，而网友说今天带了一个黑色的帽子，然而布隆一眼望去，今天穿戴黑色帽子的人也特别的多，于是再次向网友询问更多的特征来过滤掉更多穿搭相识的人。

于是布隆过滤器就是 使用多个哈希函数，将一个数据映射到位图结构中，也就是 一个数据映射位图的多个位置（哈希与位图结合，即布隆过滤器)。只有当映射的比特位全为1，则说明字符串存在。

在这里插入图片描述

三、布隆过滤器的实现

3.1 基本结构

既然需要多个哈希函数，这里我只模板中添加三个哈希函数的模板参数，以及待存储的数据类型，不过布隆过滤器最常见存储的类型是字符串，所以可以给一个缺省值。

在这里插入图片描述

显然，这三个 哈希函数 的选择是十分重要的，我们在这里提供三种较为优秀的哈希函数（字符串哈希算法），分别是 BKDRHash、APHash 以及 DJBHash

在这里插入图片描述

struct BKDRHash
{
    size_t operator()(const string& str)
    {
        register size_t hash = 0;
        for  (auto& ch : str)
        {
            hash = hash * 131 + (size_t)ch;    
        }
        return hash;
    }
};

struct APHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (auto e : str)
        {
            if (((size_t)e & 1) == 0)
            {
                hash ^= ((hash << 7) ^ (size_t)e ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ (size_t)e ^ (hash >> 5)));
            }
        }

        return hash;
    }
};

struct DJBHash
{
    size_t operator()(const string& str)
    {
        if (str.empty())
            return 0;

        size_t hash = 5381;
        for (auto e : str)
        {
            hash += (hash << 5) + (size_t)e;
        }

        return hash;
    }
};

template<size_t N
	, class K = string
	, class Hashfunc1 = BKDRHash
	, class Hashfunc2 = APHash
	, class Hashfunc3 = DJBHash>
class bloomfilter
{
public:

private:
	bitset<N> _bt;
};