HBase布鲁姆滤波器原理深度分析1 .数据结构与原理1.1初始化1.2变量映射1.3变量检索1.4总结2 .滤波器特性2.1误判率2.2判定特征3 .方案二维码
1970年，“布隆过滤器”(BloomFilter )用于确定集合中是否存在某些元素，但无法准确确定集合中是否存在元素。
通常，要确定业务场景集合中是否存在元素，通常通过比较来确定元素，例如将元素存储在集合中，并采用链表、树、哈希表和Hash Table等数据结构。 但是，随着集合中元素的增加，所需的存储空间也呈线性增加，最终成为瓶颈，检索速度也逐渐变慢。 因此，为了解决这种时间和空间性能的问题，引入了布隆过滤器。
1 .数据结构和原理bloom滤波器由固定大小的二进制向量或位图以及一系列映射函数组成。
1.1若要初始化初始状态，必须指定位图(数组)的长度(n )，并且所有位图都必须为0。
在上图中，假设N=18，则初始化array=0000000000000000。
1.2变量映射对于房间过滤器映射，必须指定映射次数k。 也就是说，必须将变量映射到位图的k个点，并将该位置的值设置为1。
如上图所示，假设位图长度N=18、映射次数K=3、散列计算函数分别为hash1、hash2、hash3。
在中，如果对元素A={x，y，z}放置光晕过滤器，则：
元素一次映射位置二次映射位置三次映射位置xhash1(x ) n=1hash2) x ) n=5hash3) x ) n=13yhash1 ) y ) n=4hash2) y ) n=11hash3) y )
1.3变量检索时，有必要判断要素w是否存在。 首先，经过k次映射，计算其所在的模糊滤波器的位置。
元素一次映射位置二次映射位置三次映射位置whash1(x ) n=4hash2) x ) n=13hash3 ) x ) % N=15其次，读取映射位置元素值时，三次映射位置的元素值为0，元素w为
1.4在总结某个变量的检索时，只要判断映射点的值是否全部为1，就可以高概率判断是否存在于集合中。
如果映射点有任何0，则查找的变量一定不存在； 如果都是1，则检索的变量存在的可能性很高。思考:为什么它可能存在，而不是一定存在？ 这是因为映射函数本身就是散列函数，而散列函数会发生冲突。
2 .滤波器特性2.1误判率布隆滤波器误判：映射多个密钥后，同一位设置为1，无法判断是来自哪个输入。 因此，错误判断的原因是同一bi位被多次映射并设置为1。
这种情况在删除布隆过滤器方面也有问题。 因为布隆过滤器并不是按位独占的，所以很可能共享有多个元素的位。 如果我们直接删除这个位，就会影响其他因素。
2.2判断特征的一个元素存在时，元素不一定存在，判断不存在时，元素不一定存在。 布隆过滤器可以添加元素，但不能删除元素。 因为删除要素会提高误判率。 3 .案例代码package org.apache.ithink；/* * bloom filter * @ author ithink/Guo JL.szu @ hotmail.com * @ date 2021-09-04 */publiccclassbloomfilter {/*/} /** *位图大小* /私有int bitsize； /** *基础存储位图*/private byte[] array； publicbloomfilter(intk，int bitsPerKey ) { this.k=k； this.bitsPerKey=bitsPerKey； } /** *生成键值的位图* @param Keys键* @return键是位图*/public byte [ ] generate [ ] keys ] { /所有key占用位数intactuatual 为了避免bitSize 8/83:bitsize8，bitSize/8为0//() bitsize7)/8 ) :保证位数为8的整数倍intmiddlebitsize=() actuallize ) )
int bitSize = middleBitSize < 64 ? 64 : middleBitSize; // 创建位图, 因为byte是8位, 所以需要将所有位数除以8 array = new byte[bitSize >> 3];// 保存位图占用大小this.bitSize = bitSize; // 循环处理 for (int i = 0; i < keys.length; i++) { // 生成Hash值 int hashCode = Bytes.hash(keys[i].getBytes()); // 循环映射K次 for (int t = 0; t < k; t++) { // 计算所在位图位置 // hashCode % bitSize + bitSize: 保证取模之后不为负数 // (hashCode % bitSize + bitSize) % bitSize: 有可能括号内超过bitSize, // 所以需要再次取模计算 int position = (hashCode % bitSize + bitSize) % bitSize; // 由于每个字节占用8位 // position % 8: 计算位置所在当前字节第几位 // (1 << (position % 8)): 将所在字节位值设置为1 // position / 8: 计算position所在字节位置 array[position / 8] |= (1 << (position % 8)); // 将hashCode前17位和后15位进行位置切换 int delta = (hashCode >> 17) | (hashCode << 15); // 保证每次计算的hashCode不同 hashCode += delta; } } return array; } /** * 判断Key是否存在 * @param key 键 * @return true:存在, false:不存在 */ public boolean contains(String key) { // 生成哈希值 int hashCode = Bytes.hash(key.getBytes()); // 循环映射K次 for (int t = 0; t < k; t++) { // 计算所在位图位置 int position = (hashCode % bitSize + bitSize) % bitSize; // 如果只要一个位置值为0, 则表示不存在 if ((array[position / 8] & (1 << (position % 8))) == 0) { return false; } // 将hashCode前17位和后15位进行位置切换 int delta = (hashCode >> 17) | (hashCode << 15); hashCode += delta; } return true; }}