算法【哈希】 | 哈希【布隆过滤器】_布隆过滤器 局部敏感哈希

一、概念

1.1 简介

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

• 可用于检索一个元素是否在一个集合中；
• 优点：空间效率和查询时间都远远超过一般的算法；
• 缺点：有一定的误识别率和删除困难；

1.2 原理

当元素被加入到集合内部，通过K个散列函数将改元素映射成一个位数组中的K个点，且将其置为1；当我们检索元素时，只需通过散列函数查看这些点是否为1即可，若其中任意一点为0，则即可判断一定不在集合里面；

• 【注意】：若检索都为1，只能说很可能在集合内部。因为集合具有一定的误识别率，需要通过结合集合的大小以及散列函数的个数来降低错误率；

1.3 复杂度

时间复杂度:

插入以及查询 ==》常数O(k)；

1.4 使用步骤

• 需要先确定布隆过滤器的元素需要多少位；

• 确定集合需要多少空间【m】，根据提供的失误率【p】和样本数量【n】得出；

• 通过样本数量即空间大小【m】确定出使用散列函数个数【k】；

• 计算真实失误率【p】；

ln2 近似为0.7

p、m、k之间的关系

• 当样本量n不变时，此时集合空间m越大，则失误率越低；
• 当样本量、空间不变时，当k较小时，会导致散列的点分布较少，即可能出现局部密集的点，导致失误率降低，若k较大时，会出现在在整个空间内密集，从而降低失误率，故k需要选择一个较为合适的大小；

1.5 扩展和应用

黑名单系统：

缓存过滤：

网络部署Web缓存以更高的性能和可靠性缓存并为用户提供 Web 内容；

• 用于有效地确定将哪些Web 对象存储在这些 Web 缓存中。访问一次，后续不在访问的用户缓存显然是浪费磁盘资源，因为它将不会被再次访问。即用于跟踪用户访问的所有 URL。Web 对象仅在之前至少被访问过一次时才被缓存，即对象在其第二次请求时被缓存。减少了磁盘写入工作量。此外，节省磁盘上的缓存空间，从而提高缓存命中率；

分布式过滤器

可以实现并行布隆过滤器以利用并行无共享机器中存在的多个处理元素(PE) ；

• 并行布隆过滤器的主要障碍之一是无序数据的组织和通信，通常在启动或批量插入时均匀分布在所有 PE 上。要对数据进行排序，可以使用两种方法，一种是对存储在每个 PE 上的所有数据进行布隆过滤器，称为复制布隆过滤器，或者对所有数据进行布隆过滤器分成相等的部分，每个 PE 存储它的一部分对于这两种方法，都使用“Single Shot”布隆过滤器，它只计算一个哈希，导致每个元素一个翻转位，以减少通信量；

二、简单模拟构建bit数组

/*----------------------------------------------------------------------
	> File Name: bitMap.cpp
	> Author: Jxiepc
	> Mail: Jxiepc
	> Created Time: Thu 03 Mar 2022 11:14:50 AM CST
----------------------------------------------------------------------*/

#include <iostream>

template<class T>
class bitMap {
public:
    bitMap() {
        T a;
        bitNum(a);
    }
    /** 数据类型的bit */
    int bitNum(T a) {
        std::cout << sizeof(a) * 8  << std::endl;  
        return sizeof(a) * 8;
    }
    
    /** 要取出的bit数，对应列表中的哪个数值 */
    void setNumIdx(T bit) const {
        numIdx = bit/m_bit;
    }

    int getNumIdx(T bit) {
        return numIdx;
    }

    /** 取出的bit数种，对应列表中数值的哪一位上 */
    void setbitIdx(T bit) const {
        bitIdx = bit % m_bit;
    }

    int getbitIdx() {
       return bitIdx; 
    }

    /** 取出该位的状态 */
    int getStatus() {
        return ((arr[numIdx] >> (bitIdx)) &1);
    }

    /** 设置状态为0 */
   void setFalse() {
        arr[numIdx] = arr[numIdx] & (~ (1 << bitIdx));
   } 

   /** 设置状态为1 */
   void setTrue() {
       arr[numIdx] = arr[numIdx] | (1<<bitIdx);
   }
private:
    int m_bit = 0;
    int numIdx = -1;
    int bitIdx = -1;
    T arr[];
};



int main(int argc, char* argv[])
{
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68