位图数组 布隆过滤器
文章目录
- 位图数组
- 获取索引
- 获取索引状态
- 设置索引状态
- 布隆过滤器
- 特点
- 大致原理
位图数组
一个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…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
