从位运算理解位图

news/2024/3/28 23:50:40/文章来源:https://blog.csdn.net/qq_37221991/article/details/127539078

位图是一种较难理解的数据结构,想了解位图,我需要先温习一下基础,复习下一些二进制的知识

位运算

1个字节=8个二进制位

二进制每逢二进一,下面是二进制对应的十进制转换方式

二进制十进制
0000 00012^0=1
0000 00102^1=2
0000 001121+20=3

左移

每个二进制位都向左移动一位
1 << 1
移动前
0000 0001
移动后
0000 0010

右移

每个二进制位都向右移动一位
1 >> 1
移动前
0000 0001
移动后
0000 0000

与运算

两个位都是1,结果为1。否则为0

  0000 0010&0000 0011=0000 0010

或运算

两个位都是0,结果为0。否则为1

    0000 0010|0000 0011=0000 0011

位图

位图的思想用利用每个二进制位的值来存储数据,优点是可以极大的节省空间

我们举个例子。有 1 千万个整数,整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢?

我们需要存储1000w个整数范围1-1亿之前的整数,用做已经使用过的数据。那么我们会选择怎么存储?我们可以使用hashSet来存储着1000w个数据,但是这样这个hashSet占据了4byte*1000w=40mb

我们试试用位图,假设我们用一亿个二进制位的数组表示位图,然后把每个数字放入位图。怎么放入呢,比如我们要放入4这个整数,那个我们就把数组第4个下标的值设置成1,以此类推。当我们要判断4是否存在,那么我们只需要取出下标为4的值判断是否为1,为1则存在了。

例如 [0,0,0,0,1,1,0,0],表示位图存储了2和3两个整数,这样我们只需要1亿个bit=12mb的内存


我们还可以用另一个存储结构来使用位图

我们举一个场景,订单有各种异常状态,大概有几十个。如果我们把订单的各种异常都存储成各个字段的话,那么整个订单表异常的字段会变得非常多。

我们可以使用一个long型运用位图的思想来存储。首先我们先约定各个异常对应的位图的位置,比如缺货异常是1,退款异常是2。如果一个订单标记了缺货和退款两个异常,那我们怎么来存储。首先没有异常情况是,这个字段二进制是0000(简写了,实际是64个二进制位),

这里有个数学公式,我们想要在第n位上标记成1,我们可以使用或运算 原值 | (1<<n) 的公式

然后我们需要标记缺货异常,只需要0|1<<1
00000 | 0010 = 0010
(既 0 | 1<<1 = 0 | 2 = 2)
这样第一个位置就变成1了,然后我们要标记退款异常,
0010 | 0100 = 0110
(既 2 | 1<<2 = 2 | 4 = 6)
这样第二个位置也变成了1

这样我们在订单表只需要存储一个字段,并存储为6就可以了

这样存储怎么查询呢,如果我要查询有缺货异常的订单。我们已知缺货异常对应的二进制位数是1,我们只需要使用与运算

例如
0110 && 0010 = 0010 (既 6&(1<<1)= 2)大于0则表示第一位是1,既有缺货异常

0100 && 0010 = 0000 (既 4&(1<<1)= 0)=0表示第一位是0,既没有缺货异常

进阶:布隆过滤器

我们会发现位图的大小会随着范围的变大而变大,回到之前的题目,如果有 1 千万个整数,整数的范围在 1 到 1 0亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢?

如果我们在使用位图就会发现我们需要使用一个10亿的二进制位来存储,那么则需要120mb的内存,内存占用反而比hashSet还要大。那么我们应该怎么办呢?

不知道大家有没有了解过布隆过滤器这个数据结构。布隆过滤器正是为了解决上述的问题,它是位图的一种改进版。

我们仍仅使用1亿个二进制位数组作为存储结构,然后对存储的值进行hash运算,运算后再对位图的大小进行取模,将对应位置设置为1。如果只有一个hash函数,那么冲突的概率还是很大的,比如1和1亿零1 对1亿取模都等于1,所以布隆过滤器会进行多个hash函数取模运算,并将这些位置都设置为1。经过多个hash函数的运算,hash冲突的概率会小很多。

在这里插入图片描述

布隆过滤器会存在一定的误判率,当我们判断某个整数是否在这 1 千万个整数中,同样会对这个数字进行多次hash取模运算,如果这些位置上都是1,那么可以判断这个整数可能存在如果这些位置上有0,但是可以判断这个整数肯定不存在

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_218720.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Shell编程案例

Shell编程案例 文章目录Shell编程案例熟悉shell编程的有关机制&#xff0c;如标准流。学习Linux环境变量设置文件及其内容/etc/profile/etc/bashrc/etc/environment~/.profile~/.bashrc熟悉编程有关基础命令技巧和规则sed掌握shell 程序执行的三种基本方式使用for循环语句,完成…

万字长文的CSS与JavaScript简易学习

近期学习web笔记&#xff0c;可供参考 目录 css: css导入方式&#xff1a; css选择器&#xff1a; javascript: javascript介绍&#xff1a; js引入方式&#xff1a; js书写语法&#xff1a; js变量&#xff1a; 5种原始类型&#xff1a; 运算符&#xff1a; JavaScr…

Spring Aop的学习(一):Spring Aop的简单入门

1. 什么是AOP AOP(Aspect Oriented Programming):面向切面编程,是OOP(面向对象编程)的一个延续,其和OOP一样,也是一种编程思想。不过AOP是一种横向开发模式。 2. AOP的作用及应用场景作用 AOP的主要作用就是减少代码量,提高代码的可重用性,有利于未来的可操作性与可维护性…

2022-2023-1 20221424《计算机基础与程序设计》第9周学习总结

2022-2023-1 20221424《计算机基础与程序设计》第9周学习总结 作业信息这个作业属于哪个课程 2022-2023-1-计算机基础与程序设计这个作业要求在哪里 2022-2023-1计算机基础与程序设计第一周作业这个作业的目标 操作系统责任,内存与进程管理,分时系统,CPU调度,文件、文件系统…

《JavaSE-第十五章》之文件(二)

前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页&#xff1a;KC老衲爱尼姑的博客主页 博主的github&#xff0c;平常所写代码皆在于此 刷题求职神器 共勉&#xff1a;talk is cheap, show me the code 作者是爪哇岛的新手&#xff0c;水…

neovim图标显示乱码,utf8字体显示乱码(Windows10和Centos安装nerd-fonts)

前言 作为一名想成为大神的菜鸟程序员&#xff0c;一个牛X的代码编辑环境是必不可少的&#xff0c;在这里我推荐neovim和emacs。我使用的是neovim&#xff0c;github上有neovim-from-scratch工程可以一步一步学习搭建&#xff0c;B站上也有相关视频可供学习&#xff0c;在这里…

升级python环境时gdal出现缺少proj的问题

gdal在做坐标转换时报出如此的错误。原系统的代码没有改变&#xff0c;为了更新sentinelhub包&#xff0c;将python环境由3.6升级至3.7。升级了python环境之后&#xff0c;所有相关的py包和第三方库重新进行安装。安装过程中基本没有遇到问题。但是在运行代码时gdal报出错误。 …

IDEA全局搜索快捷键方法

1、CtrlN 按名字搜索类 相当于eclipse的ctrlshiftR&#xff0c;输入类名可以定位到这个类文件&#xff0c;就像IDEA在其他的搜索部分表现一样&#xff0c;搜索类名也能对你所要搜索的内容多个部分进行匹配&#xff0c;而且如果能匹配的自己写的类&#xff0c;优先匹配自己写的类…

java实验报告4;

一、实验目的:【目的要求】 了解接口和抽象类的使用 熟悉类中成员的定义及权限的设定 掌握完整类的设计 【注意事项】 注意电源插座的用电安全&#xff1b; 遵守计算机的使用注意事项&#xff1b; 防范病毒。 二、使用工具 电脑 window系统 JDK环境 eclipse开发环境…

本博主二哈喇子!特此声明

免责声明 本博主二哈喇子&#xff01;为了避免各种纠纷&#xff0c;特做如下说明: 本博主一向尊重他人的知识产权&#xff0c;同时也注意保护自己的知识产权&#xff0c;因此建议您在进入本博客的各个页面前&#xff0c;请务必仔细阅读本声明。 一切网民以任何方式在进入本博客…

模拟登陆系统

1.问题 日常生活中我们会遇到许多需要密码来登陆账户的场景&#xff0c;如何使用Java来创建此类登陆代码呢&#xff1f; 2.方法 import java.util.Scanner; public static void main (String[] args) { Scanner sc new Scanner (System.in); int count 3; while(cou…

控制“恶意”代码,安全运行沙箱类技术崛起

据CNNIC的最新估算&#xff0c;截至10月31日&#xff0c;我国上网用户人数达到5800万&#xff0c;上网计算机数升至2300万&#xff0c;从七月份至今&#xff0c;在短短的四个月间分别增加了1220万和687万。 这预示着我国互联网在经过一段时间的发展低潮之后正在开始回暖。 但…

贪婪算法(Huffman编码)

如果一个算法分阶段的工作&#xff0c;并且在每一个阶段都认为所做的决定是最好的&#xff0c;而不考虑将来的后果&#xff0c;这样的算法就叫做贪婪算法。贪婪算法只考虑当前局部的最优解&#xff0c;而不去考虑全局的情况&#xff0c;如果最终得到的结果是全局最优的&#xf…

【pytest官方文档】解读- 开发可pip安装的第三方插件

在上一篇的 hooks 函数分享中,开发了一个本地插件示例,其实已经算是在编写插件了。今天继续跟着官方文档学习更多知识点。 一个插件包含一个或多个钩子函数,pytest 正是通过调用各种钩子组成的插件,实现了配置、搜集、运行和报告的所有方面的功能。 通常 pytes t中的插件有…

OS实战笔记(7)-- Linux同步机制

上一篇笔记中对x86平台上原子变量、关中断、自旋锁和信号量的原理做了复习&#xff0c;本笔记回顾一下Linux使用的几种常用的同步机制。 Linux上的原子变量 Linux上提供了一个atomic_t类型表示原子变量。32位和64位版本的结构体定义如下&#xff1a; typedef struct {int coun…

文件描述符0,1,2+lseek()+共享文件覆盖解决

1.文件描述符0&#xff0c;1&#xff0c;2 程序开始运行时&#xff0c;有三个文件被自动打开&#xff0c;打开时分别使用了这三个文件描述符依次打开的三个文件分别是 /dev/stdin&#xff0c;/dev/stdout&#xff0c;/dev/stderr /dev/stdin 标准输入文件 程序开始运行时&…

requests模块和openpyxl模块

第三方模块的下载和使用 1,第三方模块就是别人大神们已经写好的模块,功能特别强大。我们如果像使用第三方模块就先要进行下载。下载完成后 才可以在python中直接调用2.下载方式一:pip工具pip工具注意每个解释器都有pip工具 如果我们的电脑上有多个版本的解释器那么我们在使用…

模型交易平台--信用卡客户消费行为分析

业务问题&#xff1a; 据《中国银行卡产业发展蓝皮书&#xff08;2021&#xff09;》显示&#xff0c;截至2020年末&#xff0c;中国信用卡累计发卡量为11.3亿张&#xff0c;其中6个月内有使用记录的活卡为7.4亿张&#xff0c;有近4亿张信用卡处于“睡眠”状态。 睡眠信用卡…

【JUC】12.读写锁与StampedLock[完结]

文章目录1. 什么是读写锁2. 锁的演化历程3. 锁降级4. 锁降级的策略5. StampedLock简介6. StampedLock的特点7. StampedLock之传统读写8. StampedLock之乐观锁9. StampedLock缺点1. 什么是读写锁 读写锁是指ReentrantReadWriteLock类 该类能被多个读线程访问或者一个写线程访问…

第二节:数据类型与变量【java】

目录 &#x1f4c3;前言 &#x1f4d7;1.数据类型 &#x1f4d5;2. 变量 2.1 变量概念 2.2 语法格式 &#x1f4d9;3.整型变量 3.1 整型变量 3.2 长整型变量 3.3 短整型变量 3.4 字节型变量 &#x1f4d8;4.浮点型变量 4.1 双精度浮点型 4.2 单精度浮点型 &#…