-
布隆过滤器以及如何删除
2022-04-20 01:31布隆过滤器介绍
在数以亿计的数据中判断存不存在一个元素,用来解决缓存穿透。
“实际上就是个位数组,元素经过几个hash函数,分别把位数组对应位置设置为1。判断是否存在这个元素,直接去对应位置判断是不是1。”
什么是布隆过滤器
布隆过滤器(Bloom Filter)是由布隆在
1970
年提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率而且删除困难。
下图就是一个经过了
2
次哈希函数得到的布隆过滤器,根据下图我们很容易看到:假如Redis
这个字符串根本不存在,但是Redis
经过2
次哈希函数之后得到的两个位置已经是1
了(一个是wolf
通过f2
得到,一个是Nosql
通过f1
得到,这就是发生了哈希碰撞,也是布隆过滤器可能存在误判的原因)。所以通过上面的现象,我们从布隆过滤器的角度可以得出布隆过滤器主要有
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]--; } }
-
HashMap实现
2022-03-30 02:28 -
洪水填充算法判断地图是否有封闭区域
2022-03-21 03:08 -
A*寻路
2022-03-03 00:48 -
游戏定时器
2021-10-20 22:40 -
心跳检测
2021-10-18 11:31 -
环形缓冲区
2021-09-15 19:30 -
观察者模式
2021-08-31 01:05