1. AI技术聚合首页
  2. IT

C++位图和布隆过滤器（含哈希切割）

xiaoxingxing • • IT • 阅读 24

文章目录

  • C++位图和布隆过滤器（含哈希切割）
    • 1、位图（Bitmap）
      • 1.1、位图的概念
      • 1.2、位图的使用
      • 1.3、位图的模拟实现
      • 1.4、位图相关面试题
    • 2、布隆过滤器（Bloom Filter）
      • 2.1、布隆过滤器的概念
      • 2.2、布隆过滤器的插入
      • 2.3、布隆过滤器的模拟实现
      • 2.4、布隆过滤器相关面试题
    • 3、哈希切分（哈希切割）
    • 4、海量数据处理

img

C++位图和布隆过滤器（含哈希切割）

位图和布隆过滤器都是哈希思想的应用

1、位图（Bitmap）

1.1、位图的概念

位图是一种用于表示集合的数据结构，它通常用一个比特位序列来表示一组元素的存在与否。在 C++ 中，位图通常使用一个二进制数组来实现。每个元素对应位图中的一个比特位，如果该元素存在于集合中，则对应的比特位被设置为1，否则为0。

应用场景：存储大量的布尔值信息，节省内存空间。还可以快速判断一个元素是否存在于集合中，时间复杂度为 O(1)。

优点：空间效率高，占用内存少。查询效率高，时间复杂度低。

缺点：不能存储重复元素（使用两个及以上的位图可以解决）。对于范围较大的数据，可能会占用较多的内存空间。

1.2、位图的使用

void test_bs1() {
    bitset<1000> bs;
    int a[] = {1, 5, 7, 8, 999, 44, 22, 44, 0, 3, 5, 65, 78, 95};
    for (auto e: a) {
        bs.set(e);
    }

    for (auto e: a) {
        cout << e << "->" << bs.test(e) << endl;
    }
    cout << "==================" << endl;
    bs.reset(1);
    bs.reset(5);

    for (auto e: a) {
        cout << e << "->" << bs.test(e) << endl;
    }
    // a中没有的值
    cout << "a中没有的值:" << 10 << "->" << bs.test(10) << endl;

}

1.3、位图的模拟实现

这里我们用的int作为一个区间大小（32），所以是mod 32。如果是char就mod 8。

#include <vector>

// 位图
// 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
namespace xp {
    template<size_t N>
    class bitset {
    public:
        bitset() {
            _bs.resize(N / 32 + 1, 0); // 当N很大时，位图的长度范围是1～2^32
        }

        void set(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            _bs[i] |= (1 << j);// 将该位置置1
        }

        void reset(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            _bs[i] &= ~(1 << j);// 将该位置置0
        }

        bool test(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            if (_bs[i] & (1 << j))
                return true;// 这个值存在
            else
                return false;// 这个值不存在
        }

    private:
        vector<int> _bs;
    };

1.4、位图相关面试题

  1. 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】

    答：使用位图，位图的大小取决于无符号整数的区间，无符号整数的范围是0～2^32-1即0～4294967295（大约43亿）。在32位平台下就可以将这40亿个整数映射到位图中。映射完后，判断一个数是否在这40亿个数中只需要调用test函数判断该数映射的bit位是否为1，为1就在，为0就不在。

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

    答：使用两个位图，位图1存其中的100亿整数，位图2存其中的另100亿整数，其中位图占用的内存大小 = 2^32bit = 512MB，两个位图就是1GB。之后再一一对比两个位图中相同位置的bit位上都为1的整数就是交集。

  3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

    答：有两个方案：

    方案一：使用一个位图，让每两个比特位映射一个整数，这样就需要2^33个比特位（必须在64位平台下），也就是1GB的内存。两个比特位表示为：00，01，10，11。当一个整数第一次映射的时候，位图的映射位置的这两个比特位中第二个比特位设置为1，第二次映射的时候，位图的映射位置的这两个比特位中第一个比特位设置为1，第二个比特位设置为0。以此类推。其中不超过两次的整数就是映射后比特位为00和01的。

    方案二：使用两个位图，一个整数映射到两个位图的同一个位置，一个位图的这个位置的比特位作为第一个比特位，一个位图的这个位置的比特位作为第二个比特位，其实和方案一差不多，就是两个比特位记录出现的次数。这里两个位图占用的内存大小就是2*512MB=1GB。当一个整数第一次映射的时候，第二个位图的映射位置的比特位设置为1，第二次映射的时候，第一个位图的映射位置的比特位设置为1，第二个位图的映射位置的比特位设置为0。以此类推。其中不超过两次的整数就是映射后比特位为00和01的。

这里仅贴使用两个位图的代码：

template<size_t N>
    class two_bitset {
    public:
        void set(size_t x) {
            if (_bs1.test(x) == false && _bs2.test(x) == false) {
                // 00 -> 01
                _bs2.set(x);
            } else if (_bs1.test(x) == false && _bs2.test(x) == true) {
                // 01 -> 10
                _bs1.set(x);
                _bs2.reset(x);
            } else {

                _bs1.set(x);
                _bs2.set(x);
            }
        }

        size_t test(size_t x) {
            if (_bs1.test(x) == false && _bs2.test(x) == false) {
                return 0;
            } else if (_bs1.test(x) == false && _bs2.test(x) == true) {
                // 01 -> 10
                return 1;
            } else {
                return 2;// 大于等于2次
            }
        }

    private:
        bitset<N> _bs1;
        bitset<N> _bs2;
    };

2、布隆过滤器（Bloom Filter）

2.1、布隆过滤器的概念

布隆过滤器是一种空间效率很高的概率型数据结构，用于判断一个元素是否属于一个集合。它通过一系列哈希函数将元素映射到一个位数组中（即将一个元素映射到多个位置），并根据位数组中的值来判断元素是否存在。

特点：布隆过滤器可以用来快速判断一个元素不在集合中，但是无法确定一个元素是否一定在集合中。它的查询操作是常数时间复杂度，但存在一定的误判率。

应用场景：

  • 在缓存系统中判断一个数据是否存在于缓存中，从而减少缓存不命中率。
  • 在网络爬虫中过滤已经访问过的 URL，避免重复访问。
  • 在分布式系统中进行快速的数据定位。

优点：空间效率高，比哈希表占用更少的内存。查询效率高，时间复杂度低。

缺点：存在一定的误判率，即可能将不在集合中的元素误认为在集合中。不能删除元素，除非重新构建布隆过滤器。

2.2、布隆过滤器的插入

布隆过滤器的的映射规则：将一个元素映射到多个位置。下面我们模拟实现的时候，使用三个哈希函数来映射三个位置。

布隆过滤器也是使用位图来实现的，只不过它的位图的长度要更长，以防止映射位置太少而导致误判率太高。

而哈希函数个数和布隆过滤器长度的选择是有个最佳比例的（有大佬证明了）布隆过滤器

这个比例就是

其中

我们假设k为3，m/n就约等于4.34。

哈希函数：这里默认的插入对象是string，如果插入的数据是自定义类型，可以自己写仿函数传入。

struct HashFuncBKDR {
    size_t operator()(const string &str) {
        unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
        unsigned int hash = 0;

        for (auto &e: str) {
            hash = hash * seed + e;
        }
        return hash;
    }
};

struct HashFuncAP {
    size_t operator()(const string &str) {
        unsigned int hash = 0;
        int i;
        for (i = 0; i < str.size(); i++) {
            if ((i & 1) == 0) {
                hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));
            } else {
                hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));
            }
        }
        return hash;
    }

};

struct HashFuncDJB {
    size_t operator()(const string &str) {
        unsigned int hash = 5381;

        for (auto &e: str) {
            hash += (hash << 5) + e;
        }
        return hash;
    }

};

插入代码：

namespace xp {
    template<size_t N>
    class bitset {
    public:
        bitset() {
            _bs.resize(N / 32 + 1, 0); // 当N很大时，位图的长度范围是1～2^32
        }

        void set(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            _bs[i] |= (1 << j);// 将该位置置1
        }

        void reset(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            _bs[i] &= ~(1 << j);// 将该位置置0
        }

        bool test(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            if (_bs[i] & (1 << j))
                return true;// 这个值存在
            else
                return false;// 这个值不存在
        }

    private:
        vector<int> _bs;
    };
}

struct HashFuncBKDR {
    size_t operator()(const string &str) {
        unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
        unsigned int hash = 0;

        for (auto &e: str) {
            hash = hash * seed + e;
        }
        return hash;
    }
};

struct HashFuncAP {
    size_t operator()(const string &str) {
        unsigned int hash = 0;
        int i;
        for (i = 0; i < str.size(); i++) {
            if ((i & 1) == 0) {
                hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));
            } else {
                hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));
            }
        }
        return hash;
    }

};

struct HashFuncDJB {
    size_t operator()(const string &str) {
        unsigned int hash = 5381;

        for (auto &e: str) {
            hash += (hash << 5) + e;
        }
        return hash;
    }

};

template<size_t N,
        class K=string,
        class Hash1 = HashFuncBKDR,
        class Hash2 = HashFuncAP,
        class Hash3 = HashFuncDJB
>
class BloomFilter {
public:
    void set(const K &s) {
        int hash1 = Hash1()(s) % M;
        int hash2 = Hash2()(s) % M;
        int hash3 = Hash3()(s) % M;

        // 映射三个位置
        _bs.set(hash1);
        _bs.set(hash2);
        _bs.set(hash3);

    }


private:
    static const size_t M = 8*N;
    xp::bitset<M> _bs;
};

2.3、布隆过滤器的模拟实现

判断一个元素在不在这个位图中，可以看其映射的位置是否存在比特位为0的，为0一定不存在。其中一个位为1不一定存在，全部位（这里是3个位）位1才存在（也可能误判）。

因此整体代码为:

namespace xp {
    template<size_t N>
    class bitset {
    public:
        bitset() {
            _bs.resize(N / 32 + 1, 0); // 当N很大时，位图的长度范围是1～2^32
        }

        void set(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            _bs[i] |= (1 << j);// 将该位置置1
        }

        void reset(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            _bs[i] &= ~(1 << j);// 将该位置置0
        }

        bool test(size_t x) {
            assert(x <= N);
            size_t i = x / 32; // 找到第几个int（32位）
            size_t j = x % 32;

            if (_bs[i] & (1 << j))
                return true;// 这个值存在
            else
                return false;// 这个值不存在
        }

    private:
        vector<int> _bs;
    };
}

struct HashFuncBKDR {
    size_t operator()(const string &str) {
        unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
        unsigned int hash = 0;

        for (auto &e: str) {
            hash = hash * seed + e;
        }
        return hash;
    }
};

struct HashFuncAP {
    size_t operator()(const string &str) {
        unsigned int hash = 0;
        int i;
        for (i = 0; i < str.size(); i++) {
            if ((i & 1) == 0) {
                hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));
            } else {
                hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));
            }
        }
        return hash;
    }

};

struct HashFuncDJB {
    size_t operator()(const string &str) {
        unsigned int hash = 5381;

        for (auto &e: str) {
            hash += (hash << 5) + e;
        }
        return hash;
    }

};

template<size_t N,
        class K=string,
        class Hash1 = HashFuncBKDR,
        class Hash2 = HashFuncAP,
        class Hash3 = HashFuncDJB
>
class BloomFilter {
public:
    void set(const K &s) {
        int hash1 = Hash1()(s) % M;
        int hash2 = Hash2()(s) % M;
        int hash3 = Hash3()(s) % M;

        // 映射三个位置
        _bs.set(hash1);
        _bs.set(hash2);
        _bs.set(hash3);

    }

    bool test(const K &s) {
        int hash1 = Hash1()(s) % M;
        int hash2 = Hash2()(s) % M;
        int hash3 = Hash3()(s) % M;

        if (_bs.test(hash1) == false)
            return false;
        if (_bs.test(hash2) == false)
            return false;
        if (_bs.test(hash3) == false)
            return false;

        return true;// 也可能误判

    }

private:
    static const size_t M = 8*N;
    xp::bitset<M> _bs;
//    std::bitset<M> *_bs = new bitset<M>;// 也可以用库里面的
};

2.4、布隆过滤器相关面试题

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

    答：精确算法使用哈希分割（哈希切分，下面讲）。近似算法使用布隆过滤器。

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

    答：使用多个位图进行对该位进行计数，但是会使得占用的内存变大。

3、哈希切分（哈希切割）

看这个问题：给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出精确算法。

我们假设一个请求（query）是50字节，那么100亿个请求，就是500亿字节，约等于50GB，一般来说50GB的文件内存是放不下的。

那么怎么处理呢？

我们可以讲这个50GB的文件使用哈希函数切分为文件大小不同的1000份小文件（初始是没有数据，只是创建了空文件，等待后续哈希函数映射进行插入数据），平均下来每个文件大小就是500MB。为什么是1000份？假设是切分为500小文件，那如果使用哈希函数时，有占用1GB以上的query放到一个小文件中，就会导致放不进内存。这种情况的概率是很大的。切分为1000份，这种情况的概率就会变小，但不保证0概率，就算某个小文件的大小大于1GB，也是可以解决的（再次切分，下面会讲）。

文字解释太生硬，下面直接看图：

问题：给一个超过100G大小的log 文件, log中存着IP地址, 设计算法找到出现次数最多的IP地址？如何找到top K的IP？

答：采用哈希切分，将这个100GB大小的文件切分大小不一为100个小文件（初始是没有数据，只是创建了空文件，等待后续哈希函数映射进行插入数据），对每个小文件使用map<string,int>（这里如果文件太大，map插入IP可能会出现异常，那么就换哈希函数进行二次切分），得到该文件出现次数最多的IP，再对比其他小文件文件的出现次数最多的IP，进行比较，得到整体出现次数最多的IP。找top K的IP只需要创建一个存K个元素的小堆，再依次对比插入。

4、海量数据处理

海量数据问题特征：数据量大，内存存不下

  1. 先考虑具有特点的数据结构能否解决。比如：位图、堆、布隆过滤器等等

  2. 大事化小思路。哈希切分（不能平均切分）切小以后，放到内存中能处理

OKOK，C++ 位图和布隆过滤器就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页

版权声明：本文为博主作者：Xpccccc原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/qq_44121078/article/details/137564267

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐