企业网站建设该怎么描述,抚州 提供网站建站 公司,非官方网站建设,三亚今天最新通知1、Bitmaps
首先#xff0c;最经典的应用场景就是用户日活的统计#xff0c;比如说签到等。 字段串#xff1a;“dbydc”#xff0c;根据对应的ASCII表#xff0c;最后可以得到对应的二进制#xff0c;如图所示 一个字符占8位#xff08;bit#xff09;#xff0c;…1、Bitmaps
首先最经典的应用场景就是用户日活的统计比如说签到等。 字段串“dbydc”根据对应的ASCII表最后可以得到对应的二进制如图所示 一个字符占8位bit不够就在最高位补 0零我们只需设置值为 1 的位。如图所示二进制最高位是在最左边的但数组索引最高位是在最右边。字符“d”只需在偏移量offset即数组索引第 1、2、5 位设置 1 字符“b”只需在偏移量offset即数组索引第 9、10、14 位设置 1 字符“y”只需在偏移量offset即数组索引第 17、18、19、20、23 位设置 1 字符“d”只需在偏移量offset即数组索引第 25、26、29 位设置 1 字符“c”只需在偏移量offset即数组索引第 33、34、38、39 位设置 1 。
字符“d”存储第 1、2、5 位设置1
127.0.0.1:6379 setbit mykey 1 1(integer) 0
127.0.0.1:6379 setbit mykey 2 1(integer) 0
127.0.0.1:6379 setbit mykey 5 1(integer) 0字符“b”存储第 9、10、14 位设置1
127.0.0.1:6379 setbit mykey 9 1
(integer) 0
127.0.0.1:6379 setbit mykey 10 1
(integer) 0
127.0.0.1:6379 setbit mykey 14 1
(integer) 0字符“y”存储第 17、18、19、20、23 位设置1 127.0.0.1:6379 setbit mykey 17 1(integer) 0127.0.0.1:6379 setbit mykey 18 1(integer) 0127.0.0.1:6379 setbit mykey 19 1(integer) 0127.0.0.1:6379 setbit mykey 20 1(integer) 0127.0.0.1:6379 setbit mykey 23 1(integer) 0字符“d”存储第 25、26、29 位设置1 127.0.0.1:6379 setbit mykey 25 1(integer) 0127.0.0.1:6379 setbit mykey 26 1(integer) 0127.0.0.1:6379 setbit mykey 29 1(integer) 0字符“c”存储第 33、34、38、39 位设置1 127.0.0.1:6379 setbit mykey 33 1(integer) 0127.0.0.1:6379 setbit mykey 34 1(integer) 0127.0.0.1:6379 setbit mykey 38 1(integer) 0127.0.0.1:6379 setbit mykey 39 1(integer) 0获取键 mykey 对应的值
127.0.0.1:6379 get mykey“dbydc”所以我们在统计某位用户系统签到的时候sign1就是签到0就是没有签到。
setbit 2023-jack-sign 1 1 //第一日签到
setbit 2023-jack-sign 2 0 //第二日未签到
setbit 2023-jack-sign 3 1 //第三日签到
...统计出全年的签到次数 127.0.0.1:6379 BITCOUNT 2023-jack-sign 0 3 #统计1的数量
(integer) 22、布隆过滤器与Bitmaps
1970 年布隆提出了一种布隆过滤器的算法目的是用来判断一个元素是否在一个集合中。 算法由一个二进制数组和一个 Hash 算法组成 布隆过滤器的误判问题? 布隆过滤器的使用场景之缓存穿透 当用户查询的时候缓存中的key不存在则进行数据库的大量查询导致的数据库的崩溃场景. 解决思路在查询的时候快速判断查询的用户是否存在有效的缓存数据布隆过滤器。 解决缓存穿透的问题所以在用户查询缓存没有命中的时候需要兜底去查询数据库因此redis是无法完全取代数据库的。
3、布隆过滤器的代码实现
?xml version1.0 encodingUTF-8?
project xmlnshttp://maven.apache.org/POM/4.0.0 xmlns:xsihttp://www.w3.org/2001/XMLSchema-instancexsi:schemaLocationhttp://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsdmodelVersion4.0.0/modelVersionparentgroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-parent/artifactIdversion2.5.3/versionrelativePath/ !-- lookup parent from repository --/parentgroupIdcom.nengxing/groupIdartifactIdredis-base/artifactIdversion0.0.1-SNAPSHOT/versionnameredis-base/namedescriptionDemo project for Spring Boot/descriptionpropertiesjava.version1.8/java.version/propertiesdependenciesdependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-web/artifactId/dependencydependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-test/artifactIdscopetest/scope/dependency!-- https://mvnrepository.com/artifact/redis.clients/jedis --dependencygroupIdredis.clients/groupIdartifactIdjedis/artifactIdversion3.6.3/version/dependency!--引入Redis--dependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-redis/artifactIdversion1.4.2.RELEASE/version/dependencydependencygroupIdorg.redisson/groupIdartifactIdredisson/artifactIdversion3.12.3/version/dependencydependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion30.1.1-jre/version/dependencydependency!-- this is needed or IntelliJ gives junit.jar or junit-platform-launcher:1.3.2 not found errors --groupIdorg.junit.platform/groupIdartifactIdjunit-platform-launcher/artifactIdscopetest/scope/dependency/dependenciesbuildpluginsplugingroupIdorg.springframework.boot/groupIdartifactIdspring-boot-maven-plugin/artifactId/plugin/plugins/build/project布隆过滤器核心代码
import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import com.google.common.primitives.Longs;
import org.springframework.beans.factory.annotation.Autowired;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;
import redis.clients.jedis.Pipeline;import java.nio.charset.Charset;/*仿Google的布隆过滤器实现基于redis支持分布式*/
public class RedisBloomFilter {public final static String RS_BF_NS rbf:;private int numApproxElements; /*预估元素数量在配合使用数组的时候使用*/private double fpp; /*布隆过滤器所能接受的最大误差*/private int numHashFunctions; /*自动计算的hash函数个数*/private int bitmapLength; /*自动计算的最优Bitmap长度*/Autowiredprivate JedisPool jedisPool;/*** 构造布隆过滤器* param numApproxElements 预估元素数量* param fpp 可接受的最大误差* return*/public RedisBloomFilter init(int numApproxElements,double fpp){this.numApproxElements numApproxElements;this.fpp fpp;/*位数组的长度*///this.bitmapLength (int) (-numApproxElements*Math.log(fpp)/(Math.log(2)*Math.log(2)));this.bitmapLength128;/*算hash函数个数此处为了简便直接写死*///this.numHashFunctions Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2)));this.numHashFunctions2;return this;}/*** 计算一个元素值哈希后映射到Bitmap的哪些bit上* 用两个hash函数来模拟多个hash函数的情况* * param element 元素值* return bit下标的数组*/private long[] getBitIndices(String element){long[] indices new long[numHashFunctions];/*会把传入的字符串转为一个128位的hash值并且转化为一个byte数组*/byte[] bytes Hashing.murmur3_128().hashObject(element, Funnels.stringFunnel(Charset.forName(UTF-8))).asBytes();long hash1 Longs.fromBytes(bytes[7],bytes[6],bytes[5],bytes[4],bytes[3],bytes[2],bytes[1],bytes[0]);long hash2 Longs.fromBytes(bytes[15],bytes[14],bytes[13],bytes[12],bytes[11],bytes[10],bytes[9],bytes[8]);/*用这两个hash值来模拟多个函数产生的值*/long combinedHash hash1;for(int i0;inumHashFunctions;i){//数组下标indices[i](combinedHashLong.MAX_VALUE) % bitmapLength;combinedHash combinedHash hash2;}System.out.print(element数组下标);for(long index:indices){System.out.print(index,);}System.out.println( );return indices;}/*** 插入元素** param key 原始Redis键会自动加上前缀* param element 元素值字符串类型* param expireSec 过期时间秒*/public void insert(String key, String element, int expireSec) {if (key null || element null) {throw new RuntimeException(键值均不能为空);}//为了与redis中的其他key进行区别String actualKey RS_BF_NS.concat(key);try (Jedis jedis jedisPool.getResource()) {try (Pipeline pipeline jedis.pipelined()) {for (long index : getBitIndices(element)) {pipeline.setbit(actualKey, index, true);}pipeline.syncAndReturnAll();} catch (Exception ex) {ex.printStackTrace();}jedis.expire(actualKey, expireSec);}}/*** 检查元素在集合中是否可能存在** param key 原始Redis键会自动加上前缀* param element 元素值字符串类型*/public boolean mayExist(String key, String element) {if (key null || element null) {throw new RuntimeException(键值均不能为空);}String actualKey RS_BF_NS.concat(key);boolean result false;try (Jedis jedis jedisPool.getResource()) {try (Pipeline pipeline jedis.pipelined()) {for (long index : getBitIndices(element)) {pipeline.getbit(actualKey, index);}result !pipeline.syncAndReturnAll().contains(false);} catch (Exception ex) {ex.printStackTrace();}}return result;}Overridepublic String toString() {return RedisBloomFilter{ numApproxElements numApproxElements , fpp fpp , numHashFunctions numHashFunctions , bitmapLength bitmapLength };}
}判断不在的一定不在判断在的情况大概率都不在除非存在一定的hash冲突 测试
SpringBootTest
public class TestRedisBloomFilter {private static final int DAY_SEC 60 * 60 * 24;Autowiredprivate RedisBloomFilter redisBloomFilter;Testpublic void testInsert() throws Exception {// System.out.println(redisBloomFilter);redisBloomFilter.insert(bloom:user, 20210001, DAY_SEC);redisBloomFilter.insert(bloom:user, 20210002, DAY_SEC);redisBloomFilter.insert(bloom:user, 20210003, DAY_SEC);redisBloomFilter.insert(bloom:user, 20210004, DAY_SEC);redisBloomFilter.insert(bloom:user, 20210005, DAY_SEC);}Testpublic void testMayExist() throws Exception {System.out.println(redisBloomFilter.mayExist(bloom:user, 20210001));System.out.println(redisBloomFilter.mayExist(bloom:user, 20210002));System.out.println(redisBloomFilter.mayExist(bloom:user, 20210003));System.out.println(redisBloomFilter.mayExist(bloom:user, 20211001));}}Guava的布隆
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;/*单机下无Redis的布隆过滤器使用Google的Guava的BloomFilter*/
public class GuavaBF {public static void main(String[] args) {long expectedInsertions 100000;double fpp 0.00005;BloomFilterString bloomFilter BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions, fpp);bloomFilter.put(10081);bloomFilter.put(10082);bloomFilter.put(10083);bloomFilter.put(10084);bloomFilter.put(10085);bloomFilter.put(10086);System.out.println(123456:BF--bloomFilter.mightContain(123456));//falseSystem.out.println(10086:BF--bloomFilter.mightContain(10086));//trueSystem.out.println(10084:BF--bloomFilter.mightContain(10084));//true}
}
基于Redisson的实现
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
/*Redisson底层基于位图实现了一个布隆过滤器使用非常方便*/
public class RedissonBF {public static void main(String[] args) {Config config new Config();config.useSingleServer().setAddress(redis://127.0.0.1:6379);//构造RedissonRedissonClient redisson Redisson.create(config);RBloomFilterString bloomFilter redisson.getBloomFilter(phoneList);//初始化布隆过滤器预计元素为100000000L,误差率为3%bloomFilter.tryInit(100000000L,0.03);//将号码10081~10086插入到布隆过滤器中bloomFilter.add(10081);bloomFilter.add(10082);bloomFilter.add(10083);bloomFilter.add(10084);bloomFilter.add(10085);bloomFilter.add(10086);//判断下面号码是否在布隆过滤器中System.out.println(123456:BF--bloomFilter.contains(123456));//falseSystem.out.println(10086:BF--bloomFilter.contains(10086));//trueSystem.out.println(10084:BF--bloomFilter.contains(10084));//true}
}布隆过滤器的实现 Redis Redisson Redis 自主实现 无Redis Guava
