位图(bitmap)原理以及实现

大家好,我是蓝胖子,我一直相信编程是一门实践性的技术,其中算法也不例外,初学者可能往往对它可望而不可及,觉得很难,学了又忘,忘其实是由于没有真正搞懂算法的应用场景,所以我准备出一个系列,囊括我们在日常开发中常用的算法,并结合实际的应用场景,真正的感受算法的魅力。

今天,我们就来学习下位图bitmap的原理以及作用。

代码已经上传github

https://github.com/HobbyBear/codelearning/tree/master/bitmap

位图作用

bitmap 是一种高效的且占用内存很小的 判断 某个值 存在与否的数据结构。它用二进制的某一位去表示某个值是否存在。

比如我们需要统计10亿用户是否签到,正常的做法是你可以设计一个10亿长度的map,将用户的uid设置为key,是否签到设计为value,假设uid是int64 类型,占用8个字节,10亿用户就需要大约8G的内存 ,而如果 设计成bitmap去存储,则只需要大约125M 。极大的节约了内存。

原理

因为bitmap中用二进制位代表某个uid是否存在,所以一个字节能够代表8个uid是否存在,如下图所示:

image.png

bit位为1代表所在uid的用户已经签到,0则代表未签到。图中,uid为1和5的用户都没有签到,uid为2,3,4,6,7,8的用户都已经签到。

实现

要实现这样一个bitmap,我们可以用一个字节数组来保存所有的bit位,将bit位 设置为1 就是确认某个数字或者说是像例子里的uid,定位uid对应在这个字节数组的哪个位置,将特定位置的字节定位到以后,再定位这个uid在字节中的bit位是在什么位置。

整个过程看代码会更加清晰,如下代码所示,我们在bitmap的构造函数里定义了整个bitmap的最大长度。

type BitMap struct {  flags []byte  
}  func New(max int64) *BitMap {  flagLen := max/8 + 1  return &BitMap{flags: make([]byte, flagLen)}  
}

接着看下它的set方法,找到某个数字index再bitmap中的bit位,将其设置为1,一个字节是8位,通过index/8 得到其bit位是在哪个字节上,通过index%8 取余得到设置的bit位 在字节的第几个bit为上,然后通过或运算将特定bit位设置为1。

func (b *BitMap) Set(index int64) {  arrIndex := index / 8  offset := index % 8  // 将offset位置设置为1,或运算,0 | 1 = 1  1|1= 1, 0|0 =0, 1的| 将原值设置为1 ,0的| 不改变原值  b.flags[arrIndex] = b.flags[arrIndex] | (0x1 << offset)  
}

我还定义了Exits 方法快速判断某个值是否被bitmap记录,同样也是先找到index对应的bit位 在数组中的位置,然后通过与运算去判断特定bit位是0还是1。

func (b *BitMap) Exits(index int64) bool {  arrIndex := index / 8  offset := index % 8  res := b.flags[arrIndex] & (0x1 << offset)  if res == 0 {  return false  }  return true  
}

除此以外,你还可以定义一个remove方法,用于清除特定bit位上的值,

func (b *BitMap) Clean(index int64) {  arrIndex := index / 8  offset := index % 8  // 0 & 1 = 0 ,0 & 0 = 0, 1&1 =1  1的& 不会改变原来的值, 0的& 将原值变为0  b.flags[arrIndex] = b.flags[arrIndex] & ^(0x1 << offset)  
}

你可以看到bitmap用到的位运算其实本质上是用到下面的性质:

1, 1 与 0或者 1的 & 运算不会改变原值, 0 的& 会将特定bit位设置为0。
2, 0的或运算 不会改变原来的值, 1的或运算是将原来的bit位设置为1。

整个实现并不难,但这种结构的确在大数据量下达到了节约内存进行排重的目的,后续讲到的布隆过滤器也是在这种数据结构上实现的。

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

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

相关文章

tp5连接多个数据库

一、如果你的主数据库配置文件都在config.php里 直接在config.php中中定义db2&#xff1a; 控制器中打印一下&#xff1a; <?php namespace app\index\controller; use think\Controller; use think\Db; use think\Request; class Index extends Controller {public fun…

千兆以太网传输层 UDP 协议原理与 FPGA 实现

文章目录 前言心得体会一、UDP 协议介绍二、UDP 数据报格式三、UDP 数据发送测试四、Verilog实现UDP 数据发送1、IP 头部检验 IPchecksun 的计算2、以太网报文的校验字段 FCS 的计算3、以太网报文发送模块实现五、以太网数据发送测试六、仿真代码七、仿真波形展示八、上板测试九…

一百八十二、大数据离线数仓——离线数仓从Kafka采集、最终把结果数据同步到ClickHouse的完整数仓流程(待续)

一、目的 经过6个月的奋斗&#xff0c;项目的离线数仓部分终于可以上线了&#xff0c;因此整理一下离线数仓的整个流程&#xff0c;既是大家提供一个案例经验&#xff0c;也是对自己近半年的工作进行一个总结。 二、项目背景 项目行业属于交通行业&#xff0c;因此数据具有很…

yo!这里是c++中的多态

前言 在学完继承之后&#xff0c;紧接着我们来认识多态&#xff0c;建议继承不太熟的先把继承部分的知识点搞熟&#xff0c;再来学习多态&#xff0c;否则会走火入魔&#xff0c;会混乱。因为多态是建立在继承的基础之上&#xff0c;而且多态中还存在与继承类似的概念&#xff…

如何使用jenkins、ant、selenium、testng搭建自动化测试框架

如果在你的理解中自动化测试就是在eclipse里面讲webdriver的包引入&#xff0c;然后写一些测试脚本&#xff0c;这就是你所说的自动化测试&#xff0c;其实这个还不能算是真正的自动化测试&#xff0c;你见过每次需要运行的时候还需要打开eclipse然后去选择运行文件吗&#xff…

Linux Ubuntu命令行快速配置C++开发环境

本文介绍在Linux操作系统的Ubuntu版本中&#xff0c;基于命令行&#xff0c;快速配置C 编辑、编译、运行的代码开发环境的简便方法。 在之前的文章Linux操作系统Ubuntu 22.04配置Visual Studio Code与C代码开发环境的方法(https://blog.csdn.net/zhebushibiaoshifu/article/det…

C++标准模板库——vector的使用及其模拟实现

目录 一. vector的介绍 1.vector的介绍 二.vector的使用 vector中常见接口的介绍vector的构造和析构函数vector的三种遍历方式 三.vector的模拟实现 vector的增删查改vector容器的容量变化和大小增减vector迭代器失效问题vector的小框架 构造函数和析构函数迭代器和operat…

基于Java的高校竞赛管理系统设计与实现(亮点:发起比赛、报名、审核、评委打分、获奖排名,可随意更换主题如蓝桥杯、ACM、王者荣耀、吃鸡等竞赛)

高校竞赛管理系统 一、前言二、我的优势2.1 自己的网站2.2 自己的小程序&#xff08;小蔡coding&#xff09;2.3 有保障的售后2.4 福利 三、开发环境与技术3.1 MySQL数据库3.2 Vue前端技术3.3 Spring Boot框架3.4 微信小程序 四、功能设计4.1 主要功能描述4.2 系统角色 五、系统…

vue获取本地缓存并转为json格式

场景 要求获取当前登录用户id&#xff0c;传入后台去筛选属于该用户的数据&#xff1b; 当前登录用户信息一般会在本地存储中&#xff0c;有些则是在session中&#xff0c;此处只对本地存储做讨论&#xff1b; 本地缓存的用法 1 存储数据 localStorage.setltem(userId,"…

VS Code用AI写代码:Codeium插件

文章目录 Codeiumchat代码生成 Codeium Codeium是基于边缘计算的代码AI工具&#xff0c;提供超过70种编程语言的代码补全、对话、搜索等功能&#xff0c;相当霸道。 在插件栏搜索到Codeium之后&#xff0c;需要科学上网安装&#xff0c;安装完成后会提示注册。注册之后&#…

2023-9-22 滑雪

题目链接&#xff1a;滑雪 #include <cstring> #include <algorithm> #include <iostream>using namespace std;const int N 310;int n, m; int h[N][N]; int f[N][N];int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};int dp(int x, int y) {int &v f…

MySQL数据库简介+库表管理操作+数据库用户管理

Mysql Part 1 一、数据库的基本概念1.1 使用数据库的必要性1.2 数据库基本概念1.2.1 数据&#xff08;Data&#xff09;1.2.2 表1.2.3 数据库1.2.4 数据库管理系统&#xff08;DBMS&#xff09;1.2.5 数据库系统 1.3 数据库的分类1.3.1 关系数据库 SQL1.3.2 非关系数据库 NoSQL…

看阿里测试工程师如何玩转postman+newman+jenkins接口自动化

【软件测试面试突击班】如何逼自己一周刷完软件测试八股文教程&#xff0c;刷完面试就稳了&#xff0c;你也可以当高薪软件测试工程师&#xff08;自动化测试&#xff09; postman用来做接口测试非常方便&#xff0c;接口较多时&#xff0c;则可以实现接口自动化 一、环境准备…

【DLL修复工具下载】一键修复电脑丢失d3dcompiler_47.dll问题方法

在我们使用电脑的过程中&#xff0c;有时候会遇到一些错误提示&#xff0c;其中“缺失 d3dcompiler_47.dll”就是比较常见的一种。那么&#xff0c;d3dcompiler_47.dll 到底是什么呢&#xff1f;为什么会出现缺失的情况&#xff1f;丢失 d3dcompiler_47.dll 又会对电脑产生什么…

芋道商城,基于 Vue + Uniapp 实现,支持分销、拼团、砍价、秒杀、优惠券、积分、会员等级、小程序直播、页面 DIY 等功能

商城简介 芋道商城&#xff0c;基于 芋道开发平台 构建&#xff0c;以开发者为中心&#xff0c;打造中国第一流的 Java 开源商城系统&#xff0c;全部开源&#xff0c;个人与企业可 100% 免费使用。 有任何问题&#xff0c;或者想要的功能&#xff0c;可以在 Issues 中提给艿艿…

低代码助力企业数字化转型

在当今这个数字化快速发展的时代&#xff0c;企业面临的竞争越来越激烈&#xff0c;数字化转型已成为企业发展的必经之路。低代码平台作为一种新型的开发工具&#xff0c;正在逐渐成为企业数字化转型的重要助力。本文将从数字化转型背景、低代码平台介绍、低代码平台的应用、低…

SIEM 中的事件关联

什么是 SIEM 中的事件关联 SIEM 中的事件关联可帮助安全团队识别来自不同来源的安全事件并确定其优先级&#xff0c;从而提供更全面的整体安全环境视图。 在典型的 IT 环境中&#xff0c;会跨各种系统和应用程序生成大量事件和日志。孤立地看&#xff0c;其中许多事件可能看起…

聊一聊 TLS/SSL

哈喽大家好&#xff0c;我是咸鱼 当我们在上网冲浪的时候&#xff0c;会在浏览器界面顶部看到一个小锁标志&#xff0c;或者网址以 “https://” 开头 这意味着我们正在使用 TLS/SSL 协议进行安全通信。虽然它可能看起来只是一个小小的锁图标和一个 “https” &#xff0c;但…

记录一次错误---想让U-net网络输入大小不一致的图片

最近在看Deeplab系列的论文&#xff0c;文中提到了语义分割领域的一个难题是&#xff1a;将图片输入网络之前需要resize成统一大小&#xff0c;但是resize的话会造成细节信息的损失&#xff0c;所以想要网络处理任意大小的图片输入。我之前训练的U-net网络都是resize成224*224大…

Linux 本地 Docker Registry本地镜像仓库远程连接【内网穿透】

Linux 本地 Docker Registry本地镜像仓库远程连接 文章目录 Linux 本地 Docker Registry本地镜像仓库远程连接1. 部署Docker Registry2. 本地测试推送镜像3. Linux 安装cpolar4. 配置Docker Registry公网访问地址5. 公网远程推送Docker Registry6. 固定Docker Registry公网地址…