布隆过滤器以及如何删除

布隆过滤器介绍

在数以亿计的数据中判断存不存在一个元素，用来解决缓存穿透。

“实际上就是个位数组，元素经过几个hash函数，分别把位数组对应位置设置为1。判断是否存在这个元素，直接去对应位置判断是不是1。”

什么是布隆过滤器

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

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率而且删除困难。

下图就是一个经过了2次哈希函数得到的布隆过滤器，根据下图我们很容易看到：假如Redis这个字符串根本不存在，但是Redis经过2次哈希函数之后得到的两个位置已经是1了（一个是wolf通过f2得到，一个是Nosql通过f1得到，这就是发生了哈希碰撞，也是布隆过滤器可能存在误判的原因）。

所以通过上面的现象，我们从布隆过滤器的角度可以得出布隆过滤器主要有2大特点：

1. 如果布隆过滤器判断一个元素存在，那么这个元素可能存在。
2. 如果布隆过滤器判断一个元素不存在，那么这个元素一定不存在。

bloom过滤器简单demo

“实际上就是个位数组，元素经过几个hash函数，分别把位数组对应位置设置为1。判断是否存在这个元素，直接去对应位置判断是不是1。”

public static class MyBloomFilter
{
    private static BitArray _body; //位数组
    private static int _size; // 数组长度

    public static void Init()
    {
        _size = 65535;
        _body = new BitArray(_size);
    }

    public static void Add(string str)
    {
        // 三个hash函数
        var hash1 = Math.Abs(Hash(str));
        var hash2 = Math.Abs(Hash(str + "1"));
        var hash3 = Math.Abs(Hash(str + "2"));
        // 将对应位设置1
        _body[hash1 & _size] = true;
        _body[hash2 & _size] = true;
        _body[hash3 & _size] = true;
    }

    private static int Hash(string str)
    {
        return str.GetHashCode();
    }

    public static bool Contains(string str)
    {
        var hash1 = Math.Abs(Hash(str));
        var hash2 = Math.Abs(Hash(str + "1"));
        var hash3 = Math.Abs(Hash(str + "2"));
        return _body[hash1 & _size] && _body[hash2 & _size] && _body[hash3 & _size];
    }
}

bloom过滤器的删除

布隆过滤器的删除，传统布隆过滤器根据单个bit位来判断元素存在，当然不支持删除。

带计数器的布隆过滤器，最简单的实现：直接把bit换成byte就ok。

1byte=8bit，11111111 = 255

所以一个byte最大表示的数字是255，也就是说最多能支持254个hash碰撞

“实际上就是个字节数组，元素经过几个hash函数，分别把位数组对应位置+1，判断是否存在这个元素，直接去对应位置判断是不是大于1。删除某个元素就对应位置-1。”

public class MyCounterBloomFilter
{
    private static byte[] _body; //byte数组
    private static int _size; // 数组长度
    private static int _sizemask; // 数组长度-1

    public static void Init(int size = 65535)
    {
        if ((size & size - 1) != 0)
        {
            throw new Exception("数组长度必须为2的幂，求余数用了与运算");
        }

        _size = size;
        _sizemask = _size - 1;
        _body = new byte[_size];
    }

    public static void Add(string str)
    {
        // 三个hash函数
        var hash1 = Math.Abs(Hash(str));
        var hash2 = Math.Abs(Hash(str + "1"));
        var hash3 = Math.Abs(Hash(str + "2"));
        // 将对应位+1
        _body[hash1 & _sizemask]++;
        _body[hash2 & _sizemask]++;
        _body[hash3 & _sizemask]++;
    }

    private static int Hash(string str)
    {
        return str.GetHashCode();
    }

    public static bool Contains(string str)
    {
        var hash1 = Math.Abs(Hash(str));
        var hash2 = Math.Abs(Hash(str + "1"));
        var hash3 = Math.Abs(Hash(str + "2"));
        return _body[hash1 & _sizemask] > 0 && _body[hash2 & _sizemask] > 0 && _body[hash3 & _sizemask] > 0;
    }

    public static void Delete(string str)
    {
        var hash1 = Math.Abs(Hash(str));
        var hash2 = Math.Abs(Hash(str + "1"));
        var hash3 = Math.Abs(Hash(str + "2"));
        _body[hash1 & _sizemask]--;
        _body[hash2 & _sizemask]--;
        _body[hash3 & _sizemask]--;
    }
}