556-大数据查重-布隆过滤器

淡淡的烟草味﹌ 2022-09-11 07:24 166阅读 0赞

**在缓存服务器redis，在黑名单过滤，钓鱼网站过滤，URL过滤这些场景中，布隆过滤器很常见**  
布隆过滤器就是把哈希表方法和位图算法结合起来  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 布隆过滤器图解 ##

![在这里插入图片描述][76e005e651184e8a8b129e1ffc20a09f.png]

比如说，我们有3个哈希函数，位数组的长度是7个  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
我们通过第一个哈希函数，我们把这个key所要存储的数据不管是整数，还是字符串，还是IP地址，还是URL，作为输入参数，通过哈希函数得到的位置，就是位图数组范围内的一个下标。  
**假设一个输入参数通过第一个哈希函数得出的结果是0  
通过第二个哈希函数得出的结果是4  
通过第三个哈希函数得出的结果是6**  
![在这里插入图片描述][072d87c3f4b2434a8fa5dc3929d48e11.png]  
**也就是说，当第一个数据通过3个哈希函数分别进行计算，映射得到的结果是0,4，6，我们会把位数组的0号元素，4号元素和6号元素都置为1**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**0,4，6这3个位从0置成了1**  
**查询的时候我们只需要判断这3个位，如果这3个位都是1，则这个key存在，如果这3个位中有的位不是1，则表示这个key不存在。**

**同样的，我们处理第二个数据，分别通过3个哈希函数的值是2,4，5**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]  
我们需要把位数组的2号位置和4号位置和5号位置，这3个元素位置也置为1  
查询的时候我们只需要判断这3个位，如果这3个位都是1，则这个key存在，如果这3个位中有的位不是1，则表示这个key不存在  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**布隆过滤器增加一个元素的步骤：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
这个效率可是相当快的，因为这全部都是求一组哈希函数就OK了，都是O(1)的时间复杂度。  
我们现在不需要像位图算法（1,3，10000000）那样按照最大值来开辟空间。  
我们现在是把这些数据经过不同的哈希函数处理，让它的结果落在这7个位里面，得到0-6的序号，采用哈希的思想。我们可以把10000000映射到这7个位的某个位上。就避免了位图算法的缺陷。

## 问题1 ##

![在这里插入图片描述][7b8aee0807d14e71a587e692d8f8b44f.png]  
**答案是不能的**  
因为不同的key经过3组哈希函数得到的结果很有可能是相同的。因为只要有哈希函数， 肯定就会产生哈希冲突。也就是说，上图位图数组中4号位置的值是1，但是表示了2个key值的存在了，假如说要删除，经过k个哈希函数计算，得到原始的key在位图数组里都分别在哪几个位，然后把这几个位都置为0，但是很有可能多个key映射到相同的位上，如果删除就乱套了，不同key共用一个或者多个位。**如果布隆过滤器提供删除操作，会导致删除1个key，其他key也被删除了，也查询不到了**  
**所以布隆过滤器没有提供删除操作。**  
![在这里插入图片描述][b34fbce531934845871ffa7bf12f9837.png]

## 问题2 ##

![在这里插入图片描述][14315ded208a4995b9bb97ed97b4a799.png]  
如果此时我又判断第3个数据。  
![在这里插入图片描述][a8bca73977164c9aaad41a6676737c50.png]  
对于这个元素，从来没有向位图数组中添加过，但是经过既定的K个哈希函数处理后，分别得出0,2,4，把位图数组上的0,2,4置为1  
但是我们之前添加的2个元素后，位图数组上的 0,4,6,2,4,5 位置上都置为1了， 现在导致在查询这个key的时候，看成1个假象了：  
0,2,4一看，都是1，就认为这个key存在了，可是实际上，在插入这个key之前，0,2,4上的元素值已经为1了  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
我们要选择合适的哈希函数，跟这个位图数组的大小，可以降低误判的概率  
实际上，在数学公式上，有专门对布隆过滤器的误判进行数学公式的推导，怎么选择哈希函数，怎么定义位图的长度，可以有效的降低误判概率  
**但是它的效率是非常高，综合了哈希表，增删查快，而且用的是位图数组，省内存，而且不存在位图数组的缺陷，因为采用的是哈希的概念，把位图数组当做哈希表了**  
**位图数组是判断不存在，判断存在的话可能存在误判**

## 布隆过滤器总结 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]

## 运用场景1 ##

![在这里插入图片描述][b3d9214fbd424f3cb1ac746a16cfe239.png]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]

## 运用场景2 ##

我们有一个客户端请求到后端服务，提交一个注册或者登录按钮。  
后端服务器有一个I/O模块，就是网络层，专门接收用户的请求。  
那么I/O层会把这个请求分发到相应的一些工作线程，到服务service层处理业务，涉及到数据的增删改查，它要进行查询数据的时候，查询数据的请求比修改数据的请求多很多，查数据的时候，首先从redis缓存层查，如果缓存层可用查到，就不用去后面的数据库查，缓存层如果能查到，就直接把数据从redis取出来，redis是nosql的数据库，存储的是key-value，和map表一样，然后返回到I/O层，然后返回到客户端。如果说在redis找不到，才去后面的数据库DB（mysql）查找，查询以后，为了下一次查比较快，会把这个数据缓存在redis上 ，然后返回给用户，下一次查这个数据的时候就可以从redis缓存查了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
**mysql是磁盘I/O，性能的瓶颈很快到达。**  
service层在redis查询是用的key，key就是ID号之类的唯一的值。通过用户ID查询到一些用户关心的数据，如果在redis查不到key，就去mysql查询。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]

![在这里插入图片描述][6096e8b47c8c4bbe8590c946934f529a.png]

## stringhash.h ##

#pragma once
    
    
    /// @brief BKDR Hash Function  
    /// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。  
    template<class T>
    size_t BKDRHash(const T* str)
    {
        
        register size_t hash = 0;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..  
            // 有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;  
            // 但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，  
            // 我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；  
            // 在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：  
            // 当乘数8-31位都为1或0时，需要1个时钟周期  
            // 当乘数16-31位都为1或0时，需要2个时钟周期  
            // 当乘数24-31位都为1或0时，需要3个时钟周期  
            // 否则，需要4个时钟周期  
            // 因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大          
        }
        return hash;
    }
    /// @brief SDBM Hash Function  
    /// @detail 本算法是由于在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。  
    template<class T>
    size_t SDBMHash(const T* str)
    {
        
        register size_t hash = 0;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = 65599 * hash + ch;
            //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
        }
        return hash;
    }
    /// @brief RS Hash Function  
    /// @detail 因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。  
    template<class T>
    size_t RSHash(const T* str)
    {
        
        register size_t hash = 0;
        size_t magic = 63689;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
    /// @brief AP Hash Function  
    /// @detail 由Arash Partow发明的一种hash算法。  
    template<class T>
    size_t APHash(const T* str)
    {
        
        register size_t hash = 0;
        size_t ch;
        for (long i = 0; ch = (size_t)*str++; i++)
        {
        
            if ((i & 1) == 0)
            {
        
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
        
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
    /// @brief JS Hash Function  
    /// 由Justin Sobel发明的一种hash算法。  
    template<class T>
    size_t JSHash(const T* str)
    {
        
        if (!*str)        // 这是由本人添加，以保证空字符串返回哈希值0  
            return 0;
        register size_t hash = 1315423911;
        while (size_t ch = (size_t)*str++)
        {
        
            hash ^= ((hash << 5) + ch + (hash >> 2));
        }
        return hash;
    }
    /// @brief DEK Function  
    /// @detail 本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。  
    template<class T>
    size_t DEKHash(const T* str)
    {
        
        if (!*str)        // 这是由本人添加，以保证空字符串返回哈希值0  
            return 0;
        register size_t hash = 1315423911;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
        }
        return hash;
    }
    /// @brief FNV Hash Function  
    /// @detail Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。  
    template<class T>
    size_t FNVHash(const T* str)
    {
        
        if (!*str)   // 这是由本人添加，以保证空字符串返回哈希值0  
            return 0;
        register size_t hash = 2166136261;
        while (size_t ch = (size_t)*str++)
        {
        
            hash *= 16777619;
            hash ^= ch;
        }
        return hash;
    }
    /// @brief DJB Hash Function  
    /// @detail 由Daniel J. Bernstein教授发明的一种hash算法。  
    template<class T>
    size_t DJBHash(const T* str)
    {
        
        if (!*str)   // 这是由本人添加，以保证空字符串返回哈希值0  
            return 0;
        register size_t hash = 5381;
        while (size_t ch = (size_t)*str++)
        {
        
            hash += (hash << 5) + ch;
        }
        return hash;
    }
    /// @brief DJB Hash Function 2  
    /// @detail 由Daniel J. Bernstein 发明的另一种hash算法。  
    template<class T>
    size_t DJB2Hash(const T* str)
    {
        
        if (!*str)   // 这是由本人添加，以保证空字符串返回哈希值0  
            return 0;
        register size_t hash = 5381;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = hash * 33 ^ ch;
        }
        return hash;
    }
    /// @brief PJW Hash Function  
    /// @detail 本算法是基于AT&T贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。  
    template<class T>
    size_t PJWHash(const T* str)
    {
        
        static const size_t TotalBits = sizeof(size_t) * 8;
        static const size_t ThreeQuarters = (TotalBits * 3) / 4;
        static const size_t OneEighth = TotalBits / 8;
        static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth);
    
        register size_t hash = 0;
        size_t magic = 0;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = (hash << OneEighth) + ch;
            if ((magic = hash & HighBits) != 0)
            {
        
                hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));
            }
        }
        return hash;
    }
    /// @brief ELF Hash Function  
    /// @detail 由于在Unix的Extended Library Function被附带而得名的一种hash算法，它其实就是PJW Hash的变形。  
    template<class T>
    size_t ELFHash(const T* str)
    {
        
        static const size_t TotalBits = sizeof(size_t) * 8;
        static const size_t ThreeQuarters = (TotalBits * 3) / 4;
        static const size_t OneEighth = TotalBits / 8;
        static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth);
        register size_t hash = 0;
        size_t magic = 0;
        while (size_t ch = (size_t)*str++)
        {
        
            hash = (hash << OneEighth) + ch;
            if ((magic = hash & HighBits) != 0)
            {
        
                hash ^= (magic >> ThreeQuarters);
                hash &= ~magic;
            }
        }
        return hash;
    }

## 布隆过滤器代码应用 ##

#include <iostream>
    #include <vector>
    #include "stringhash.h"
    #include <string>
    using namespace std;
    
    //布隆过滤器实现
    class BloomFilter
    {
        
    public:
        BloomFilter(int bitSize = 1471)//构造函数 
            : bitSize_(bitSize)
        {
        
            bitMap_.resize(bitSize_ / 32 + 1);//int类型数组的大小 
        }
        
    public: 
        //添加元素 O(1)
        void setBit(const char* str)
        {
        
            //计算k组哈希函数的值
            int idx1 = BKDRHash(str) % bitSize_;
            int idx2 = RSHash(str) % bitSize_;
            int idx3 = APHash(str) % bitSize_;
    
            //把相应的idx1 idx2 idx3这几个位全部置1
            int index = 0;
            int offset = 0;
    
            index = idx1 / 32;
            offset = idx1 % 32;
            bitMap_[index] |= (1 << offset);
    
            index = idx2 / 32;
            offset = idx2 % 32;
            bitMap_[index] |= (1 << offset);
    
            index = idx3 / 32;
            offset = idx3 % 32;
            bitMap_[index] |= (1 << offset);
        }
    
        //查询元素 O(1)
        bool getBit(const char* str)
        {
        
            //计算k组哈希函数的值
            int idx1 = BKDRHash(str) % bitSize_;
            int idx2 = RSHash(str) % bitSize_;
            int idx3 = APHash(str) % bitSize_;
    
            int index = 0;
            int offset = 0;
    
            index = idx1 / 32;
            offset = idx1 % 32;
            if (0 == (bitMap_[index] & (1 << offset)))
            {
        
                return false;
            }
    
            index = idx2 / 32;
            offset = idx2 % 32;
            if (0 == (bitMap_[index] & (1 << offset)))
            {
        
                return false;
            }
    
            index = idx3 / 32;
            offset = idx3 % 32;
            if (0 == (bitMap_[index] & (1 << offset)))
            {
        
                return false;
            }
    
            return true;
        }
    
    private:
        int bitSize_;//位图的长度
        vector<int> bitMap_;//位图数组
    };
    
    //URL黑名单
    class BlackList
    {
        
    public:
        void add(string url)//添加 
        {
        
            blockList_.setBit(url.c_str());
        }
        bool query(string url)//查询 
        {
        
            return blockList_.getBit(url.c_str());
        }
    private:
        BloomFilter blockList_;
    };
    
    int main() 
    {
        
        BlackList list;
        list.add("http://www.baidu.com");
        list.add("http://www.360buy.com");
        list.add("http://www.tmall.com");
        list.add("http://www.tencent.com");
    
        string url = "http://www.alibaba.com";
        cout << list.query(url) << endl;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1ec04433a0ee44f9be17375246c86f82.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/3df46a4d361b45f2bef22d9c84d8b35e.png
[76e005e651184e8a8b129e1ffc20a09f.png]: /images/20220828/7d9b11c650c84301bd208e7d33fb51d3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/83913f5050b74376a2849e8312e9f9d1.png
[072d87c3f4b2434a8fa5dc3929d48e11.png]: /images/20220828/668c3d1295644dd8a900b9e03f059f44.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/cc718065eefc4547b195a49494fb3c80.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8b985bab57de4c0d880fedd9d5e1a730.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/ed8f4c3010f54870b5d9ca4c7e67be1f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/acd41b13260646d1999cf39a72a88e33.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/0bb812a40c0945628fae5c2917aa7b5a.png
[7b8aee0807d14e71a587e692d8f8b44f.png]: /images/20220828/100fecdec5c24d01963be45590a69d2e.png
[b34fbce531934845871ffa7bf12f9837.png]: /images/20220828/348edc409b874adba3a890bbb59a6a2d.png
[14315ded208a4995b9bb97ed97b4a799.png]: /images/20220828/768196af20024cf999025a495f4436cc.png
[a8bca73977164c9aaad41a6676737c50.png]: /images/20220828/7f2000d59c024a8db457ec946883d529.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/7f101eadc410406f8fa2be5722c62150.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/424b88a6368d4ea1945731a57536d764.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/ca7c415e763b4784a6a745f3535a325a.png
[b3d9214fbd424f3cb1ac746a16cfe239.png]: /images/20220828/868cc79445a74987836b4cf930dae733.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/abe02920425c49faae85f97fc5b32cb8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/46147fd37dc1451dbd04b30aed0b1815.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/4c08c3b4d70742069ad099507f6a5c1b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/ba7081ca0a234aadad871c4d5f2de3b0.png
[6096e8b47c8c4bbe8590c946934f529a.png]: /images/20220828/9bd36c824f584c798e060d4a651db696.png