位图和布隆过滤器

目录

引入

例子

位图

介绍

模拟实现

思路

底层bit顺序

位运算

test

代码

代码示例

应用场景 

应用题

布隆过滤器 

引入

介绍

模拟实现

思路

set过程

reset

test过程

代码

降低布隆过滤器的误判率

应用场景

示例说明

其他应用场景

应用题

哈希切割

哈希切割应用题

---

引入

哈希固然好用,一旦遇到非常大量的数据的时候,也得歇菜

例子

比如,要处理某文件中40亿个数据,里面存放的都是整型值,需要和外部匹配,判断该值是否存在

• 我们可以先算一下1G可以放多少字节:
• 1G=1024MB=1024*1024KB=1024*1024*1024B(也就是字节),大概10亿字节
• 而40亿个整型,按照4字节计算,就得要160亿字节,也就是16G
• 夸了个大张,这时候不管用我们学过的啥数据结构都妥妥爆内存,内存哪来的16G给你
• 所以我们得考虑其他的方法
• 其实我们在linux就遇到过这种方法,使用位图标记文件系统中一些资源的使用情况
• 
• 所以,这里也是一样的,本质上思路和哈希大差不差,都是把位置和数据绑定在一起,只不过位置的大小变成了1bit

位图

介绍

位图（Bitmap）用于表示一组元素的二进制状态或布尔值

每个元素通常对应于位图中的一个位（0或1），表示某种状态或属性的有无

模拟实现

思路

底层bit顺序

按照我们的方法,可以将第几位bit和数字直接关联起来

一个整型是32bit,第一个整型就可以表示0-31区间的数字是否存在,如下图:

其实到这里就可以去实现位图了,但素,我们还是再了解了解计算机底层到底是怎么排bit顺序的吧

还记得我们计算机字节排列顺序的存储方式分为小端和大端吗?

• 我们一般使用的电脑应该都是小端吧,小端是反向存储的
• 就比如1(1就可以用来验证本机电脑是小端还是大端)
• 1的二进制是:00 00 00 01(1个数字代表了4位bit)
• 但小端是低位存低地址,在内存中就变成了:01 00 00 00 
• 注意:它是以字节为单位反向存的(一个字节的内部还是从高位到低位的)
• 所以,实际上int内部的bit顺序应该是:
• 

位运算

set要置1

• 可以考虑将数字1左移对应位数,让该int 按位或一下,这样那个1就可以被int拿到
• 也可以先取出要置位的位,然后和1按位或,然后再将该数左移,和int按位或

reset置0

• 和第一个方法类似,只不过要将1左移后的数字按位取反(这样对应位就是0,其他位是1),这样按位与一下,可以保证其他位不变,只有那个位被置为0

test

就是取出对应位(也就是右移然后和1按位与)返回就行

代码

#include 
#include 
#include 
using namespace std;
 
namespace my_bitset
{
    template <size_t N> // 位图中只用传入容量即可(也就是最大数值是多少)
    class bitSet
    {
    public:
        bitSet()
        {
            _a.resize(N / 32 + 1); // 如果该数不是32的整数倍,就得多给一个int
        }
        void set(size_t x) // 置1
        {
            size_t i = x / 32; // 找到应该在第几个int
            size_t j = x % 32; // 找到int中的第几位
            //_a[i] |= (((_a[i] >> j) | 1) << j); //两种方法都行
            _a[i] |= (1 << j);
        }
        void reset(size_t x) // 置0
        {
            size_t i = x / 32; // 找到应该在第几个int
            size_t j = x % 32; // 找到int中的第几位
            _a[i] &= (~(1 << j)); //这样除了第j位是0,其他位都是1
        }
        bool test(size_t x)
        {
            size_t i = x / 32; // 找到应该在第几个int
            size_t j = x % 32; // 找到int中的第几位
            return (_a[i] >> j) & 1;
        }
 
    private:
        vector<int> _a;
    };
}

代码示例

void test1()
{
    my_bitset::bitSet<10> b;
    b.set(2);
    b.set(4);
    b.set(5);
    cout << b.test(2) << " " << b.test(4) << " " << b.test(5) << endl;
    b.reset(2);
    cout << b.test(2) << " "<< b.test(4) << " " << b.test(5) << endl;
}

注意看图,因为我们把2,4,5三个数字要置为1,那么对应的_a[i]中的对应位就要置为1(黑字为位数):

ret也是类似的操作,只不过是置为0

应用场景 

• 快速查找某个数据是否在一个集合中
• 排序 + 去重
• 求两个集合的交集、并集等
• 操作系统中磁盘块的标记

应用题

给定100亿个整数，设计算法找到只出现一次的整数

• 因为要找出现一次的整数,也就是说,我们不能只标记存不存在了,而是需要计数
• 但只有1位bit时,无法满足计数的要求
• 那么要扩展到几位呢?
• 因为不需要详细的计数,实际上只需要两位bit即可,两位最大可以表示3,足够我们使用了

• 所以,当出现一次时,将第一位设为1
• 一旦出现第二次,就将第二位设为1,第一位设为0
• 如果有更多次,也不需要再变了,我们不需要知道到底出现多少次
• 所以,找的时候,只需要找第一位为1,第二位为0就行

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集

• 注意,交集是集合,集合中不能有重复元素,所以两个文件如果有重复出现的相同数字,交集中只能出现一次
• 所以我们不需要计数,只需要标记在不在
• 而我们有两个文件,所以相应的就设置两个位图
• 只要两个位图中该位都为1,就说明是交集

1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

• 和第一个问题类似,都是需要扩展位数
• 这里用2位bit也足够了,最大可以表示3
• 最后只要两个位不都为1,就属于不超过两次

布隆过滤器 

引入

位图可以帮助我们快速查找某个整数是否存在,那么其他数据结构呢?

• 比如,我们以字符串为例
• 首先我们要知道,字符串的查找是很普遍的,比如查找某网址/某条信息是否存在
• 计算机发展到现在,处理大规模数据集的需求非常多
• 在信息检索、数据库查询、网络路由、拦截垃圾邮件等领域，需要快速地判断一个元素是否存在于庞大的数据集中，以提高效率
• 所以,布隆将哈希和位图结合在一起,设计出了这个过滤器,用于快速检查一个元素是否存在于一个大集合中

介绍

  是一种紧凑型的、巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”

• 它是用多个哈希函数，将一个数据映射到位图结构中 
• 所以底层还是位图,只不过确定[该值对应哪一位]的时候用的是哈希值
• 因为哈希函数不能保证一对一,所以哈希冲突是无法避免的,但可以通过使用多个哈希函数,映射到多个位上,来降低冲突的概率:
• 
• 只有当三个位都匹配的时候,才说这个字符串存在
• 当然,这样也无法保证不会冲突,只能通过增加哈希函数的个数/扩容来降低冲突的概率
• 但是!!!不存在是可以保证正确的!
• 存在 -- 是因为有哈希冲突,所以不能确定[存在的就是你给的字符串]
• 而一旦不存在,就是真的不存在

模拟实现

思路

set过程

• 用哈希函数将string转换为整型值,再%容量,就是哈希值了
• 用哈希值作为位图中set的参数,这样哈希值对应位就被置为1

reset

• 虽然位图中有这个操作,但是我们不能照搬到过滤器中
• 上面有说过,布隆过滤器找存在是有哈希冲突的,所以我们不能简单的直接置0,这样会影响其他字符串的匹配
• 那为什么位图可以reset呢?因为位图是一对一的,其中一位被reset是不会影响其他数据的
• 所以,布隆过滤器是不支持reset的!!!

test过程

• 可以将传入参数拿到三个哈希值,然后调用位图的test
• 只有三位都是true的情况下,才能说这个参数是存在的
• 而只要有一位是false,就说明,肯定肯定肯定是不存在的,直接返回就行

代码

#pragma once
#include 
#include 
using namespace std;
 
namespace my_BloomFilter
{
    struct BKDRHash
    {
        size_t operator()(const string &str)
        {
            size_t hash = 0;
            for (auto ch : str)
            {
                hash = hash * 131 + ch;
            }
            return hash;
        }
    };
 
    struct APHash
    {
        size_t operator()(const 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 DJBHash
    {
        size_t operator()(const string &str)
        {
            size_t hash = 5381;
            for (auto ch : str)
            {
                hash += (hash << 5) + ch;
            }
            return hash;
        }
    };
 
    template <size_t N, class K = string,
              class Hash1 = BKDRHash, // 这里选择三种哈希函数
              class Hash2 = APHash,
              class Hash3 = DJBHash>
    class BloomFilter
    {
    public:
        BloomFilter() : _b(N)
        {
        }
        void set(const K &data)
        {
            // 先将字符串通过哈希函数转换为整型值
            size_t hashi1 = h1(data) % N;
            size_t hashi2 = h2(data) % N;
            size_t hashi3 = h3(data) % N;
            _b.set(hashi1);
            _b.set(hashi2);
            _b.set(hashi3);
        }
        bool test(const K &data)
        {
            // size_t hashi1 = h1(data)%N;
            // size_t hashi2 = h2(data)%N;
            // size_t hashi3 = h3(data)%N;
            // if (_b.test(hashi1) && _b.test(hashi2) && _b.test(hashi3))
            // {
            //     return true;
            // }
            // else
            // {
            //     return false;
            // }
            // 其实没有必要固定比对三次,只要其中一次比对不成功,就说明data不存在
            size_t hashi1 = h1(data) % N;
            if (_b.test(hashi1) == false)
            {
                return false;
            }
            size_t hashi2 = h2(data) % N;
            if (_b.test(hashi2) == false)
            {
                return false;
            }
            size_t hashi3 = h3(data) % N;
            if (_b.test(hashi3) == false)
            {
                return false;
            }
 
            return true;
        }
 
    private:
        bitset _b;
        Hash1 h1;
        Hash2 h2;
        Hash3 h3;
    };
}

降低布隆过滤器的误判率

详解布隆过滤器的原理，使用场景和注意事项 - 知乎

可以看出来,哈希函数越多,布隆过滤器的容量越大,误判率越小

所以它是一个只要你肯花空间,误判率可以变得非常小的方法

应用场景

在找不存在的时候,非常高速准确,所以被称为"过滤器"

示例说明

比如说:昵称匹配

• 很多软件/游戏可能都会要求昵称不能重复,所以需要快速找到用户的昵称是否存在
• 如果每次都从数据库中找的话,效率很慢,而且如果有多个用户同时访问数据库,还可能会进一步导致效率降低
• 所以我们可以利用布隆过滤器的特性,如果该昵称不存在,就直接返回
• 如果昵称存在,再去数据库中查找是否真的存在(因为存在哈希冲突)\
• 

其他应用场景

• 缓存：布隆过滤器可以用来确定某个请求的结果是否已经被缓存，以避免不必要的数据库或磁盘访问。这可以显著提高缓存的效率

• 数据库查询优化：在数据库查询中，可以使用布隆过滤器来快速排除不可能包含结果的表，从而减少不必要的查询开销

• 网络爬虫去重：网络爬虫可以使用布隆过滤器来避免重复抓取同一个URL，从而提高爬虫的效率

• 拦截垃圾邮件：邮件服务器可以使用布隆过滤器来快速检查邮件的发件人地址是否已知的垃圾邮件发送者，从而减少垃圾邮件的传递

• 黑名单过滤：网络安全应用中，布隆过滤器可以用来存储已知的恶意IP地址或域名，以快速拦截恶意流量

• 单词拼写检查：布隆过滤器可以用于拼写检查，以快速确定一个单词是否在字典中，从而提高拼写检查的速度

• 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

应用题

如何扩展BloomFilter使得它支持删除元素的操作

• 首先,为什么它不支持删除来着?
• 是因为存在哈希冲突,如果删除某个元素可能会影响其他元素的匹配
• 所以,我们可以参考共享内存的方法,使用引用计数来记录该位的使用情况
• 如果该位已经没有元素"指向"它了(参考前面画的那个图),就可以将它删除了(也就是将该位置为0)
• 如果要引入"引用计数",可以参考前面题目中,使用多个bit位来计数

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

(quary:"query" 是一个通用术语，用于描述请求信息或执行数据检索操作的动作或请求,也就是字符串 )

近似算法

• 因为有100亿个字符串,所以这里肯定要用布隆过滤器了
• 也就是需要100亿位bit=10亿字节=1G(差不多是够了)
• 接下来就是将其中一个文件存入布隆过滤器,另一个进行匹配
• 当然,其中会存在哈希冲突,所以只能被称为"近似算法"

精确算法

• 如果要求精确,那肯定就不能只用布隆过滤器了,该怎么办呢?
• 因为是数据量挡住了我们,所以考虑将大文件切割为小文件来处理
• 也就是"哈希切割"

哈希切割

• 通过使用哈希函数，可以将数据均匀地分布到不同的分区中，从而实现负载均衡，有助于避免某些分区负载过重，而其他分区负载较轻，确保查询性能的稳定性

• 哈希切割使得通过数据的键或标识符进行查询时，可以直接定位到正确的分区，从而提高查询性能

所以,我们可以通过哈希切割,将那两个大文件分别分成几百个小文件 :

这样,如果B中有和Ai相同的,必然会进入对应的Bi这个文件,所以只需要Ai和Bi进行比对即可

但是这样就没问题了吗?

• 我们来想想,得到的这么多文件,里面的数据都是通过哈希函数分配的
• 所以,里面要么是相同数据,要么就是产生了哈希冲突的数据
• 而且也不能保证文件是平均分配的(如果平均分配的话,每个文件大概百来M,但哈希分配不能保证会不会有些文件格外的大,因为它是按照数据分的)
• 所以,如果有个文件是几G的大小,依然不能开始找交集
• 而且,交集里面是不能有重复元素的
• 所以,我们可以考虑进行去重(也就是使用set),如果大部分都是重复数据,set是可以存下的
• 那如果大部分都是因为哈希冲突进来的数据呢?
  • 那set就会抛出异常,只要我们能捕捉到,就说明里面大部分都是冲突数据,可以进行进一步的切割

接下来就是两个文件找交集的逻辑了:

• 既然我们都已经使用set了,那就用set解决吧
• set找交集很简单,Ai中的数据插入到set中,对应的Bi中的数据进行判断,在就是交集,并且删掉该数据(防止Bi中有重复数据,使交集中有重复数据)

哈希切割应用题

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

• 还是一样的,为了准确性,我们需要进行哈希切割,而不能用布隆过滤器
• 切割后,可以使用map进行计数
• 如果map没有异常当然最好,如果有的话,就进行二次切割
• 最后比较每个文件中的最大值,更新即可

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

(这个不太会,去搜了搜)

grep -oE "\b([0-9]{1,3}\.){3}[0-9]{1,3}\b" yourlogfile.log | sort | uniq -c | sort -nr | head -n 10

1. grep -oE "\b([0-9]{1,3}\.){3}[0-9]{1,3}\b"：使用正则表达式从日志文件中提取IP地址
2. sort：将提取的IP地址进行排序，以便它们可以被uniq命令正确地计数
3. uniq -c：计算每个唯一的IP地址出现的次数。
4. sort -nr：按出现次数倒序排序IP地址，使出现次数最多的IP地址排在前面。
5. head -n 10：显示前面的10个IP地址，这些IP地址出现次数最多。

如果想要优化性能，可以考虑使用更高级的工具，如awk或者将日志文件拆分成更小的块进行并行处理

如果日志文件很大，可能需要分割文件或使用更高级的工具和技术来处理，例如分布式计算框架（如Hadoop）或专门用于日志分析的工具（如ELK堆栈或Splunk)