位图数组 布隆过滤器
文章目录
- 位图数组
- 获取索引
- 获取索引状态
- 设置索引状态
- 布隆过滤器
- 特点
- 大致原理
位图数组
一个int类型的整数用4字节,也就是32个bit位来表示,将整数类型的数组转换成位图数组,那么存储长度将变为原来的32倍
arr[0] 表示0-31
arr[1] 表示32-63
//...
获取索引
假设当前数为178,那么178在位图数组中的位置为:
// 数组索引,要存放的index
index=Math.floor(178/32)
// 位图索引,对应32位要存放的索引
bitIndex=178%32
获取索引状态
// 拿到index,再右移bitIndex位,那此时状态就变到了最后一位,再& 1
// ... 0000000s
// ... 00000001
int s=(arr[index]>>bitIndex)& 1
设置索引状态
将对应位置设置为1
// ...s...
// ...1...
// 注意是或操作,1其他位为0,最后只会将s位变为1,其他位不会影响
arr[index] | (1 << bitIndex)
将对应位置设为0
// 1 << bitIndex 后取反将变为, ... 1110111 ...
// 注意 & 1 不会影响其他位
arr[index] & (~ (1 << bitIndex))
布隆过滤器
特点
- 存在一定失误率,但很小
- 不能删除已设置的元素
- 假设要查询当前url是否在黑名单
- 只会存在将非黑名单判定成黑名单这种失误,而不会出现将黑名单判定成白名单的情况
- 通过位图数组,大幅度减少存储空间
大致原理
场景:要存储100亿个黑名单url,并且给定一个url要判断是否在黑名单内
- 假设数组长度为m
- 对100亿个黑名单url,对每个url用k个hash函数求得k个转换出来的整型数n,对n%m获取到不超过m的映射值n2,对n2进行上面位图的操作,放入bit中
- 这里要求k个hash,拿到k个n2,k个bit是因为对样本提取多个指纹,最后结果更精确
- 为什么只会出现将非黑名单判定成黑名单这种这种情况
- 假设黑名单url1对应的k个指纹bit位置为32,11,22,黑名单url2对应的k个指纹bit位置为9,11,10
- 如果要判定的url在黑名单内,那么通过hash得出指纹bit一定被设置了,因为hash函数的特效会得到相同的输出,所以如果是黑名单的url不可能被判定成白名单
- 如果要判定的url不在黑名单内,那么因为hash冲突可能bit位置为22,10,因为被其他黑名单url设置了,所以白名单的url会被判定成黑名单
- 为什么要求元素设置后不能被删除
- 因为黑名单url2删除bit位11时,会将黑名单url1的bit位11也影响,那么再进行判定时,黑名单url1会因为bit位11没有设置,被判定为白名单url
- 对于数组长度m、失误率p和哈希函数的个数k,都存在数学公式去计算
相关文章:
位图数组 布隆过滤器
文章目录位图数组获取索引获取索引状态设置索引状态布隆过滤器特点大致原理位图数组 一个int类型的整数用4字节,也就是32个bit位来表示,将整数类型的数组转换成位图数组,那么存储长度将变为原来的32倍 arr[0] 表示0-31 arr[1] 表示32-63 //...获取索引…...
多线程Thread常用方法和状态
Thread类 及常见方法 1、常见构造方法 方法说明Thread()创建线程对象Thread(Runnable target)使用 Runnable 对象创建线程对象Thread(String name)创建线程对象,并命名Thread(Runnable target, String name)使用 Runnable 对象创建线程对象,并命名Thre…...
Codeforces Round #836 (Div. 2)
A SSeeeeiinngg DDoouubbllee 题意:告诉你一个字符串。若该串上每一位上的字母都可以出现两次,求回文串 思路:正向再反向输出s即可 #include <bits/stdc.h> #define lowbit(x) x&(-x) #define ios cin.sync_with_stdio(false)…...
Python学习之项目实践: 写一个MP3播放器
下面呢,是一个 Python MP3 播放器,它使用 pygame 模块来实现音乐播放功能: import pygame class MP3Player: """ MP3 播放器类 """ def __init__(self): pygame.mixer.init() def play(self, file_path): &quo…...
RocketMQTemplate 实现消息发送
代码托管于gitee:easy-rocketmq 文章目录一、前置工作二、消费者三、生产者1. 普通消息2. 过滤消息3. 同步消息4. 延时消息5. 批量消息6. 异步消息7. 单向消息8. 顺序消息9. 事务消息概要Demo源码解读一、前置工作 1、导入依赖 <dependency><groupId>…...
教师干货丨这5款微课必备提效神器,我要告诉全世界!
微课是一种短小精悍的视频教学形式,其设计和演示因特别简洁明了而被定义为“小而美”。由于只在几分钟时间内向学生传授所需知识,微课为学习者提供更多的选择机会和时间节约的便利,而这种趋势已经逐渐在新的社交媒体环境中显现出来。在制作微…...
timm使用swin-transformer
1.安装 pip install timm2.timm中有多少个预训练模型 #timm中有多少个预训练模型 model_pretrain_list timm.list_models(pretrainedTrue) print(len(model_pretrain_list), model_pretrain_list[:3])3加载swin模型一般准会出错 model_ft timm.create_model(swin_base_pat…...
【java基础】java八大基本数据类型和运算符
文章目录说明八大基本数据类型整型浮点型字符型布尔类型类型转换java运算符基础运算符二元运算符自增自减运算符关系和boolean运算符三元运算符位运算符运算符优先级说明 这里介绍java的八大基本数据类型和运算符 八大基本数据类型 java中有八大数据类型,4个整型…...
Mybatis源码学习笔记(四)之Mybatis执行增删改查方法的流程解析
1 Mybatis流程解析概述 Mybatis框架在执行增伤改的流程基本相同, 很简单,这个大家只要自己写个测试demo跟一下源码,基本就能明白是怎么回事,查询操作略有不同, 这里主要通过查询操作来解析一下整个框架的流程设计实现。 2 Mybat…...
浅谈测试用例设计
前言 最近干的最多的事情就是设计测试用例、评审测试用例了,于是我不禁又想到了一个经典的问题:如何设计出优秀的测试用例? 可能有些童鞋看到这个问题会有些不以为然,这有什么好想的?干个测试谁还不会设计测试用例&a…...
python 利用装饰器实现类似于flask路由
例子1: def f1():print(1111)def f2():print(2222)if __name__ __main__:print(33)打印结果: 33 在例子1中,f1() 与f2() 都没有被调用,只执行了print(33) f1与f2,是没有被调用的,但是如果f1 和 f2 上面…...
git 拉取远程分支到本地
目录:***!本小作者,是将终端和Git的可视化插件结合使用,刚接触的可以自习看一下,内容简单,避免弯路!***一,简单了解远程分支1,连接远程:2,提交&am…...
Answering Multi-Dimensional Range Queries under Local Differential Privacy
文章目录AbstractIntroduction2 PRELIMINARIES2.12.2 Categorical Frequency Oracles4 GRID APPROACHES4.1概述Abstract 在本文中,我们解决了在局部差异隐私下回答多维范围查询的问题。有三个关键的技术挑战:捕捉属性之间的相关性,避免维度的…...
手把手搭建springboot项目05-springboot整合Redis及其业务场景
目录前言一、食用步骤1.1 安装步骤1.1.1 客户端安装1.2 添加依赖1.3 修改配置1.4 项目使用1.5 序列化二、应用场景2.1 缓存2.2.分布式锁2.2.1 redis实现2.2.2 使用Redisson 作为分布式锁2.3 全局ID、计数器、限流2.4 购物车2.5 消息队列 (List)2.6 点赞、签到、打卡 (Set)2.7 筛…...
Flutter基础语法(六)var、final、const、late
Flutter基础 第六章 Flutter关键字var、final、const、late的区别与使用 文章目录Flutter基础前言一、var1.var是什么?2.var如何使用3.var自动推断类型4.var可以再次赋值5.var指定类型二、final1.final是什么?2.final声明但不赋值3.final赋值多次4.final正常使用三、const1.…...
Linux之安装node
Linux之安装node步骤如下 1.去网站下载node 下载地址: https://npm.taobao.org/mirrors/ 2.上传到指定目录下 3.解压 tar -zxvf node-v17.3.0-linux-x644.配置node环境变量 //执行以下命令 vim /etc/profile //在path中加入以下内容 /usr/local/node-v15.14.0/b…...
二叉树、二叉搜索树、二叉树的最近祖先、二叉树的层序遍历【零神基础精讲】
来源0x3f:https://space.bilibili.com/206214 文章目录二叉树[104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)[111. 二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)[129. 求根节点到叶节点…...
【算法】【数组与矩阵模块】求最长可整合子数组和子数组的长度
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 问题介绍 …...
数据结构:循环队列的实现(leetcode622.设计循环队列)
目录 一.循环队列简单介绍 二.用静态数组实现循环队列 1.数组循环队列结构设计 2.数组循环队列的堆区内存申请接口 3.数据出队和入队的接口实现 4.其他操作接口 5.数组循环队列的实现代码总览 三.静态单向循环链表实现循环队列 1.链表循环队列的结构设计 2.创建静…...
[qiankun]实战问题汇总
[qiankun]实战问题汇总ERROR SyntaxError: Cannot use import statement outside a module问题分析解决方案子应用命名问题问题分析解决方案jsonpFunction详细错误信息问题分析解决方案微应用的注册问题Uncaught Error: application cli5-beta6-test-name died in status LOADI…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
