哈希思想的应用 - 位图，布隆过滤器

目录

位图

海量数据处理问题：

哈希思想的应用：位图

位图实现：

位图处理海量数据

布隆过滤器

引：

布隆过滤器的概念：

布隆过滤器简单实现：

布隆过滤器的查找

布隆过滤器的删除

布隆过滤器优点

布隆过滤器缺点

有关布隆过滤器中，哈希函数的个数选取，位图长度

哈希切分（哈希切割） 

---

位图

海量数据处理问题：

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

分析：1G大约等于10亿字节，1M约等于一百万字节。40亿无符号整数即160亿字节，约等于16G（实际上应该是15.xG）所以，这么多数据全存入内存中组织为哈希表或者红黑树这样的key value搜索数据结构进行处理在大多数普通计算机上都不现实。因为红黑树的每个结点中除了存储数据本身，还有三个指针，还有一个颜色标记，直接将所需空间扩大了若干倍（32位机器还是64位机器）。而哈希表中也要存储next指针。

这种问题属于海量数据处理问题，哈希表和红黑树都适于搜索，但是不适于处理海量数据。

哈希思想的应用：位图

哈希思想：将元素关键值与元素的存储位置之间建立映射关系，而这种关键值与存储位置之间可以通过哈希函数进行转换，哈希函数中的一种是直接定址法，Hash（Key）= A*Key + B，优点：简单、均匀，且直接定址法不会产生哈希冲突  缺点：需要事先知道关键字的分布情况。

对于上方海量数据处理问题：关键值即无符号整数，而对应的value为存在 or 不存在，我们可以用1 0来进行标记，而无符号整数的范围为0 ~ 42亿... 所以，我们可以直接用数组的下标来对应关键值，存储的比特位标记存在状态。其实也就是直接定址法的A和B设为1。此时40亿个比特位即5亿个字节，约等于0.5G。当查找某个整数是否存在时，直接判断对应下标处的比特位为1或0，即可判断是否对应整数存在。

所谓位图，就是用每一比特位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用 来判断某个数据存不存在的。

位图实现：

    // N表示整数范围
    template<size_t N>
    class bitset
    {
    public:
        bitset() {
            _bits.resize(N/8 + 1, 0);
        }
 
        void set(size_t x) {
            size_t i = x/8; // 数组下标
            size_t j = x%8; // _bits[i]的那个char的第j位(0 <= j <= 7)
            _bits[i] |= (1 << j);
        }
 
        void reset(size_t x) {
            size_t i = x/8;
            size_t j = x%8;
            _bits[i] &= ~(1 << j);
        }
 
        bool test(size_t x) {
            size_t i = x/8;
            size_t j = x%8;
            return _bits[i] & (1 << j);
        }
    private:
        vector<char> _bits;
    };

STL中也有位图，std::bitset   template class bitset;

对于上方实现中，set和reset的方式很好理解，注意此处的<<。此处将一个char的低位到高位依次看作0 ~ 7位。若机器为小端，则低位存在低字节，高位存在高字节，此时1<<1仍然是那个1往高位移动，若左边显示低地址数据，右边显示高地址数据，则在视觉上，就是往右移动。若机器为大端，低位存在高字节，高位存在低字节，则1 << 1，在视觉上1就是往左移动。  
总之，左移右移，不论小端还是大端机器，永远都是往高位移动。而对于数组中某一个char，1<

位图的应用范围比较小，只能针对海量整型，因为这样才能直接映射到数组下标，且需要表示的状态比较少时，一般都是存在或不存在。

位图处理海量数据

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

这里的只出现一次，也就是每个整数对应的状态为 出现0次，出现1次，出现次数>1次。一个比特位是无法表示三种状态的，故我们可以用两个比特位来标记一个整数，00表示出现0次，01表示出现1次，10表示出现大于1次。此处可以直接用两个位图实现。

    template <size_t N>
    class twobitset
    {
    public:
        void set(size_t x) {
            bool t1 = _bits1.test(x);
            bool t2 = _bits2.test(x);
 
            if(!t1 && !t2) {
                // 00 -> 01  0次->1次
                _bits2.set(x);
            }
            else if(!t1 && t2) {
                // 01 -> 10 1次->2次
                _bits1.set(x);
                _bits2.reset(x);
            }
        }
        bool test(size_t x) {
            bool t1 = _bits1.test(x);
            bool t2 = _bits2.test(x);
            return !t1 && t2; // 01 一次
        }
    private:
        bitset _bits1;
        bitset _bits2;
    };

这样，对应为01的位，就是出现一次的整数。

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

一个文件的数据放入一个位图，这样两个位图中都为1的位就是两个文件的交集。bitset<0xffffffff>

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

依旧是整数，出现次数不超过两次，即0次1次2次，大于两次。分别用00 01 10 11标记即可，两个位图即可解决。

布隆过滤器

引：

位图的特点是插入快，查找快，节省空间（处理大量数据）。但是缺陷之一是只能针对整型数据。那么，如果有大量的字符串或者其他非整型数据，该如何处理。

一种思想是：将非整型数据例如字符串通过哈希函数转为整型，再由哈希函数转为哈希地址，这样通过比特位的1 和 0也能标志这个数据存在或不存在。查询时，通过同样的哈希函数，获取哈希地址，通过比特位的1 和 0就能判断这个数据在或不在。注意，布隆过滤器和位图只能适用于处理海量数据的少量状态，比如在或不在。

但是，可能有多个字符串例如AB得到的哈希地址相同，此时若A在，B不在。判断B时，也会得到在的结果，也就是存在误判的可能性。这里的解决方法是：对于每个字符串（数据）通过多个哈希函数获取多个哈希地址，判断时，结合多个哈希地址处的01标记位进行判断，有一个为0即不存在，全为1为可能存在，这样就能减少误判的概率。但是不能完全杜绝误判，因此布隆过滤器是一种概率型数据结构。它能够准确地告诉你某个元素不存在，能够不准确地告诉你某个元素存在。而这里存在的误判率可以通过调整哈希函数的个数和布隆过滤器的大小来降低。

布隆过滤器的概念：

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。 

布隆过滤器 是 哈希和位图的结合。

布隆过滤器简单实现：

//
// Created by yangzilong on 2022/11/18.
//
 
#ifndef STL_BLOOMFILTER_H
#define STL_BLOOMFILTER_H
 
struct HashBKDR
{
    // BKDR
    size_t operator()(const string& key)
    {
        size_t val = 0;
        for (auto ch : key)
        {
            val *= 131;
            val += ch;
        }
 
        return val;
    }
};
 
struct HashAP
{
    // BKDR
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (size_t i = 0; i < key.size(); i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
            }
        }
        return hash;
    }
};
 
struct HashDJB
{
    // BKDR
    size_t operator()(const string& key)
    {
        size_t hash = 5381;
        for (auto ch : key)
        {
            hash += (hash << 5) + ch;
        }
 
        return hash;
    }
};
 
// 此处的布隆过滤器默认处理string类型数据
template <size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:
    void set(const K& key) {
        // 将数据通过3个不同处理函数转为3个整型，通过一个哈希函数转为三个哈希地址，获得三个标记位。
        size_t hash1 = Hash1()(key) % (_radio * N);
        size_t hash2 = Hash2()(key) % (_radio * N);
        size_t hash3 = Hash3()(key) % (_radio * N);
 
        _bits->set(hash1);
        _bits->set(hash2);
        _bits->set(hash3);
    }
 
    bool test(const K& key) {
        size_t hash1 = Hash1()(key) % (_radio * N);
        if(!_bits->test(hash1)) {
            return false; // 某一个位为0，返回假，准确的
        }
        size_t hash2 = Hash2()(key) % (_radio * N);
        if(!_bits->test(hash2)) {
            return false; // 某一个位为0，返回假，准确的
        }
        size_t hash3 = Hash3()(key) % (_radio * N);
        if(!_bits->test(hash3)) {
            return false; // 某一个位为0，返回假，准确的
        }
        // 3个位都为1，返回真，存在误判概率
        return true;
    }
private:
    const static size_t _radio = 5;
    std::bitset<_radio * N>* _bits = new std::bitset<_radio * N>;
};
#endif //STL_BLOOMFILTER_H

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在位图中，否则可能在位图中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在。查询结果表明该元素存在时，该元素可能存在，因为有些元素的哈希地址相同，存在一定的误判。

布隆过滤器的删除

很明显，若删除A元素时直接将A元素对应的三个哈希地址处的比特位改为0，可能直接影响其他元素，故不能直接简单地删除。可以通过增加每个映射位的比特位数来强行支持布隆过滤器的删除，比如现在一个比特位只能表示两个状态，若一个哈希地址的映射位占8个比特位，就能表示255种状态，也就是一个小型计数器。但是布隆过滤器本身就是为了处理海量数据的少量状态，故一般情况下，布隆过滤器不支持删除操作。

布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

有关布隆过滤器中，哈希函数的个数选取，位图长度

现假定哈希函数选取3个，当位图长度越长时，误判率肯定越低，但是也不能过于长。位图长度和插入元素个数之间是数学关系的，当哈希函数个数一定时，位图长度 = 插入元素个数 * 4.2是比较合适的。

哈希切分（哈希切割） 

1. 给两个文件AB，分别有100亿个query（字符串），我们只有1G内存，如何找到两个文件交集?分别给出精确算法和近似算法

这里100亿个字符串，仍然是海量数据，因此不能直接全放入内存中进行处理。

近似算法：将一个文件的字符串，加载到一个位图中。用该位图依次查找B文件的query即可。这里若判断为在，是可能在，因此为近似算法。

精确算法：哈希切分思想：

计算出一个大文件大致分为多少份小文件合适（一份文件的数据要加载到内存中），文件数量设为N。

建立A(0) ~ A(N-1)共N个小文件，B(0) ~ B(N-1)个小文件。依次遍历A文件中每个query，i = Hash(query) % N，将query存入对应的Ai文件中。B文件也是如此，获取每个query的哈希地址i，存入Bi中。

以上即为哈希切分的过程，之后可以将两个小文件存入两个set中，利用常规算法即可求出其中的相同query，即AB文件的交集。

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

依旧是海量字符串数据，哈希切分：设计N个小文件，依次读取每个ip， i = Hash(ip) % N，将ip存入第i个小文件中。

完成哈希切分，每个相同的ip都会进入同一个小文件中，再对每个小文件使用map统计次数。
若想找出topK的ip，建立一个K个元素的小堆，按照ip的出现次数进行统计。

---

一个非常大的文件，若不能直接处理，则需要切分为小的文件。但是切分时，利用哈希思想，即可将某些相同的数据存入同一个小文件中，后面的处理就会高效很多。 哈希切割的关键就在于切分小文件时利用哈希思想。