企业网站托管常见问题中国企业500强门槛

当前位置： 首页 > news >正文

企业网站托管常见问题,中国企业500强门槛,天津外贸seo推广,html5的网站简介 布隆过滤器#xff08;Bloom Filter#xff09;是一种空间效率高、误判率低的数据结构#xff0c;通常用于判断一个元素是否在一个集合中。其原理是利用多个哈希函数将输入元素映射到一个位数组中#xff0c;并将对应的位标记为1。判断一个元素是否在集合中时#x…简介 布隆过滤器Bloom Filter是一种空间效率高、误判率低的数据结构通常用于判断一个元素是否在一个集合中。其原理是利用多个哈希函数将输入元素映射到一个位数组中并将对应的位标记为1。判断一个元素是否在集合中时只需要查询其对应的位是否都为1即可。 布隆过滤器的主要数据结构是一个由 m 个二进制位组成的位数组初始时所有位都被置为0。同时布隆过滤器还需要 k 个哈希函数这些哈希函数将输入元素映射到位数组中的 k 个位置上每个位置都标记为1。具体的哈希函数可以是任意一种哈希算法例如 MD5、SHA1 等。 将一个元素插入到布隆过滤器时需要将该元素通过 k 个哈希函数映射到位数组中的 k 个位置上并将这些位置的值都置为1。查询一个元素是否在布隆过滤器中时只需要将该元素通过 k 个哈希函数映射到位数组中的 k 个位置上检查这些位置的值是否都为1若都为1则该元素可能存在于集合中否则该元素肯定不存在于集合中。 由于布隆过滤器是基于哈希函数实现的所以其查询时间和空间复杂度都非常低但同时也存在误判率的问题。当布隆过滤器的位数组容量不够大时会产生误判即有些不存在于集合中的元素被错误地判断为存在于集合中。因此布隆过滤器通常用于辅助其他数据结构进行快速查询而不是单独使用。 如何计算具体的映射数组位置 计算布隆过滤器中元素的映射位置需要使用哈希函数。布隆过滤器通常使用多个哈希函数每个哈希函数将元素映射到位数组的不同位置。哈希函数的计算方法可以有多种但是需要保证相同的输入元素得到的输出结果是固定的且输出结果的分布尽可能均匀。 以最简单的一种哈希函数为例假设需要将一个元素 e 映射到一个 m 个二进制位组成的位数组上。可以使用取模运算将元素 e 映射到位数组的某个位置上 hash(e) e % m这种哈希函数的计算方法非常简单只需要将元素 e 的哈希值通常是一个整数进行取模运算然后将结果作为该元素在位数组中的映射位置。但是这种哈希函数的分布不一定均匀可能会导致某些位被频繁地标记为1而其他位则很少被标记。 更好的哈希函数设计可以通过使用多个哈希函数将元素映射到多个位置上从而减小误判率。例如可以使用 k 个不同的哈希函数将元素映射到位数组的 k 个位置上具体计算方法可以采用以下公式 hash_i(e) (hash_func_i(e) i) % m其中hash_func_i(e) 表示第 i 个哈希函数对元素 e 进行哈希计算得到的值i 是一个常量表示第 i 个哈希函数得到的映射位置偏移量。通过这种方法可以将元素映射到位数组的多个位置上从而减小误判率。 布隆过滤器中哈希函数的计算方法可以根据实际情况进行优化例如采用更加复杂的哈希算法或者引入其他技术来减小误判率例如 Counting Bloom Filter、Cuckoo Filter 等。 Bloom Filter 开源工具包 Google GuavaGuava 是一个 Google 开源的 Java 核心库其中包括了布隆过滤器的实现。Guava 提供了 BloomFilter 类可以使用 BloomFilter.create() 方法创建一个 BloomFilter 实例然后调用 add() 方法添加元素contains() 方法判断元素是否存在。 Apache Commons CollectionsCommons Collections 是一个 Apache 开源的 Java 工具包其中包括了布隆过滤器的实现。Commons Collections 提供了 BloomFilter 类可以使用 BloomFilter.create() 方法创建一个 BloomFilter 实例然后调用 add() 方法添加元素contains() 方法判断元素是否存在。 RedissonRedisson 是一个基于 Redis 的分布式 Java 工具包其中包括了布隆过滤器的实现。Redisson 提供了 RBloomFilter 类可以使用 RedissonClient.getBloomFilter() 方法获取一个 RBloomFilter 实例然后调用 add() 方法添加元素contains() 方法判断元素是否存在。 CountingBloomFilter 原理 Bloom Filter不支持删除功能。 Counting Bloom Filter的出现解决了这个问题它将标准Bloom Filter位数组的每一位扩展为一个小的计数器(Counter)在插入元素时给对应的k(k为哈希函数个数)个Counter的值分别加1删除元素时给对应的k个Counter的值分别减1Counting Bloom Filter通过多占用几倍的存储空间的代价给Bloom Filter增加了删除操作。 CountingBloomFilter添加删除 假设counter值设为4Bloom Filter位数组对应的每个位都是counter位的数组Counting Bloom Filter对应的添加删除过程如下图所示。
Counter取值 对于大多数情况来说4位就足够了。具体推导请见 https://blog.csdn.net/zhaoyunxiang721/article/details/41123007 Counting Bloom Filter 如何实现 Counting Bloom FilterCBF是一种基于 Bloom Filter 的改进算法它能够统计每个元素的重复次数并且允许删除元素。CBF 在网络协议、数据压缩、分布式存储系统等领域得到了广泛的应用。 CBF 的主要特点是在位数组中不再只存储 0 或 1而是使用计数器来存储每个元素出现的次数。具体来说CBF 采用一个 m 个元素的位数组 C 和 k 个哈希函数每个哈希函数可以将元素映射到位数组的一个位置上。对于一个元素 e对应的 CBF 计算方法如下 将 C 中所有经过哈希函数映射到的位置的计数器加 1。 如果计数器的值超过了一个阈值通常为 3则将这个元素标记为存在于 CBF 中。 查询一个元素是否在 CBF 中时需要查询所有哈希函数映射到的位置上的计数器的值是否都大于 0如果都大于 0则认为这个元素可能存在于 CBF 中。 删除一个元素时需要将 CBF 中所有哈希函数映射到的位置上的计数器减 1。如果某个位置上的计数器减为了 0则认为这个元素已经不存在于 CBF 中。 CBF 的实现过程比较简单只需要将 Bloom Filter 中的位数组改成计数器数组增加一个计数器加减的操作即可。CBF 中的计数器需要支持加法和减法操作因此通常采用计数器数组代替位数组计数器数组中的每个元素都是一个计数器可以进行加法和减法操作。此外CBF 还需要定义一个阈值用于判断某个元素是否存在于 CBF 中。阈值的选择需要根据具体的应用场景进行调整通常选择 3 或 4。 由于使用了计数器数组CBF 的空间复杂度要高于 Bloom Filter因为需要存储每个元素的计数器。此外CBF 的误判率也会随着计数器阈值的增大而增大。因此CBF 的适用场景需要根据具体的需求进行选择。 基于本地内存的CountingBloomFilter实现 网上已有代码实现基于本地内存的CountingBloomFilter方式基本一致分两种形式 当Counter为8、16、32、64时采用数组方式进行存储利用储存结构特性如果是8则取byte数组正好每一位对应的8bit如果是16则取short数组如果是32则取int数组如果是64则取long数组。当Counter不为这几个时建立一个大小为m总大小*counter的BitSet。 Add操作 和BloomFilter基本一致在每次计算出的hash位上加1。 Check操作 和BloomFilter基本一致检查是不是所有hash位的值大于0。 Delete操作 在每个hash位上减1。 基于Redis的CountingBloomFilter实现过程 基于Redis的CountingBloomFilter实现和基于内存的逻辑一致只是存储地址由本地内存改为了Redis。 在已有开源代码基础上需要自己实现的部分主要就CountingBloomFilter储存的初始化以及add、delete、check的逻辑代码。 初始化 因为CountingBloomFilter比BloomFilter膨胀了Counter倍所以对应可能使用的Redis的bitmap数量也会膨胀Counter倍。因此初始化CountingBloomFilter时需要根据总大小m来进行Redis的bitmap分片。总大小m为整型所以最大值为2^32-1。 假设总大小m为2^32-1Counter为4。 这时候分片结果: 共有4个bitMap,每个bitMap所负责的位 Bitmap1:[0,2^30-1]Bitmap2:[230,231-1]Bitmap3:[231,2312^30-1]Bitmap4:[231230,2^32-1] 逻辑运算 添加删除为了保证原子性操作通过Redis执行lua脚本方式保证其原子性Redis在执行脚本时不会执行其他脚本或Redis命令所以lua脚本不宜过长可能阻塞线程导致整个Redis服务不可用。 使用Redis位运算的方法BITFIELD BITFIELD key [GET type offset] [SET type offset value] [INCRBY type offset increment] [OVERFLOW WRAP|SAT|FAIL] 自3.2.0起可用。 该命令将 Redis字符串视为一个位数组进行操作。 所支持的子命令如下 GET- 返回指定的位域。 SET- 设置指定的位域并返回其旧值。 INCRBY-递增或递减如果给定负递增指定的位域并返回新值。 type字段决定操作的类型通过 i 为有符号整数和 u 无符号整数加上整数类型的位数来组成。 offset字段为起始的位 value字段为要设置的值(十进制) increment字段为递增或递减的值 OVERFLOW为溢出控制控制溢出处理策略。 WRAP默认值。环绕例如如果i8整数设置为127则将其递增1 -128。 SAT饱和算术向上溢出置为最大整数想下溢出置为最小。例如i8从数值120开始递增一个以10 为增量的整数结果为数值127。 FAIL溢出直接失败返回值 NULL以向调用者发送信号。 有了BITFIELD这个方法处理就很简单了。 添加删除的lua脚本 –lua 下标从 1 开始–rediskey local key KEYS[1] –起始操作位 local position tonumber(ARGV[1]) –创建bitfield的 local countingBits u .. ARGV[2] –自增的值如果为add则为1del时 则为-1 local bit tonumber(ARGV[3]) – 自增或自减采取fail模式如果失败则返回null local res redis.call(bitfield, key , overflow, fail,incrby, countingBits, position ,bit) return res查询方法伪代码 //check方法public boolean check(String redisKey, int position, int counter){ //判断当前Counter位的十进制值是否大于0return redisClient.bitfield(redisKey,get, u counter ,position )0; }至此CountingBloomFilter主要逻辑完成。至于如何实现累加只需要增加一个配置开关。 如果需要累加添加时不判断是否存在直接添加如果不需要累加添加时先判断是否存在 使用场景总结 Bloom Filter 结论适用于大数据量下的集合过滤。 优点空间效率和查询时间都远远超过一般的算法。 缺点有一定的误识别率和无法删除。 使用场景举例 网页爬虫对URL的去重避免爬取相同的URL地址反垃圾邮件从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱同理垃圾短信缓存击穿将已存在的缓存放到布隆中当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。 Counting Bloom Filter 结论Bloom Filter的变种支持了计数及删除。 优点保证了空间和时间的同时支持了计数及删除。 缺点有一定的误识别率和空间上使用比Bloom Filter多。 使用场景举例 需要支持删除的名单缓存.caffine cache的LRU缓存实现了类似的功能