数据结构(2):BitMap的基本原理和实现
mhr18 2024-11-13 11:06 34 浏览 0 评论
一、原理
基本原理
BitMap 的基本原理就是用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素。由于采用一 个bit 来存储一个数据，因此可以大大的节省空间。
我们通过一个具体的例子来说明 BitMap 的原理，假设我们要对 0-31 内的 3 个元素 (10, 17,28) 排序，那么我们就可以采用 BitMap 方法（假设这些元素没有重复）。
如下图，要表示 32 个数，我们就只需要 32 个 bit（4Bytes），首先我们开辟 4Byte 的空间，将这些空间的所有 bit 位都置为 0。
然后，我们要添加(10, 17,28) 这三个数到 BitMap 中，需要的操作就是在相应的位置上将0置为1即可。如下图，比如现在要插入 10 这个元素，只需要将蓝色的那一位变为1即可。
将这些数据插入后，假设我们想对数据进行排序或者检索数据是否存在，就可以依次遍历这个数据结构，碰到位为 1 的情况，就当这个数据存在。
字符串映射
BitMap 也可以用来表述字符串类型的数据，但是需要有一层Hash映射，如下图，通过一层映射关系，可以表述字符串是否存在。
当然这种方式会有数据碰撞的问题，但可以通过 Bloom Filter 做一些优化。
二、实现
懂原理之后，还是要写代码来加深一下理解，这里用 Python 实现一个最基本的版本。
代码用到了 bitarry 库来直接操作 bit 数组；用 hashlib 来将字符串映射到数字，以便插入 BitMap。
代码很简单，看懂上面的原理的话，很容易就看懂了代码。
三、使用
BitMap 的使用场景很广泛，比如说 Oracle、Redis 中都有用到 BitMap。当然更多的系统会有比 BitMap 稍微复杂一些的算法，比如 Bloom Filter、Counting Bloom Filter，这些会在后面逐一展开。
下面举一个在算法中用到 BitMap 来解决问题的例子。
已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
在这里就不再做和其它算法的对比，直接说一下 BitMap 的思路。
8 位的整数，相当于是范围在(0,99999999)，也就是说 99999999 个 bit，也就是 12M 左右的内存，比起用类似 HashMap 的方式的话能节省很大的空间。 可以理解为从0 到 99999999 的数字，每个数字对应一个 Bit位，所以只需要 12M 左右的内存表示了所有的 8 位数的电话。
查询的时候就很简单了，直接统计有多少位是 1 就可以了。
四、总结
BitMap 的思想在面试的时候还是可以用来解决不少问题的，然后在很多系统中也都会用到，算是一种不错的解决问题的思路。
但是 BitMap 也有一些局限，因此会有其它一些基于 BitMap 的算法出现来解决这些问题。
- 数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
- 数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。
算法比较成熟，因此参考的东西也挺多，就不再列参考了。
转自：https://my.oschina.net/leejun2005/blog/76506
相关推荐
- Dubai's AI Boom Lures Global Tech as Emirate Reinvents Itself as Middle East's Silicon Gateway
-
AI-generatedimageAsianFin--Dubaiisrapidlytransformingitselffromadesertoilhubintoaglob...
- OpenAI Releases o3-pro, Cuts o3 Prices by 80% as Deal with Google Cloud Reported to Make for Compute Needs
-
TMTPOST--OpenAIisescalatingthepricewarinlargelanguagemodel(LLM)whileseekingpartnershi...
- 黄仁勋说AI Agent才是未来!但究竟有些啥影响?
-
，抓住风口（iOS用户请用电脑端打开小程序）本期要点：详解2025年大热点你好，我是王煜全，这里是王煜全要闻评论。最近，有个词被各个科技大佬反复提及——AIAgent，智能体。黄仁勋在CES展的发布...
- 商城微服务项目组件搭建(五)——Kafka、Tomcat等安装部署
-
1、本文属于mini商城系列文档的第0章，由于篇幅原因，这篇文章拆成了6部分，本文属于第5部分2、mini商城项目详细文档及代码见CSDN：https://blog.csdn.net/Eclipse_...
- Python+Appium环境搭建与自动化教程
-
以下是保姆级教程，手把手教你搭建Python+Appium环境并实现简单的APP自动化测试：一、环境搭建（Windows系统）1.安装Python访问Python官网下载最新版（建议...
- 零配置入门:用VSCode写Java代码的正确姿
-
一、环境准备：安装JDK，让电脑“听懂”Java目标：安装Java开发工具包（JDK），配置环境变量下载JDKJava程序需要JDK（JavaDevelopmentKit）才能运行和编译。以下是两...
- Mycat的搭建以及配置与启动（mycat2）
-
1、首先开启服务器相关端口firewall-cmd--permanent--add-port=9066/tcpfirewall-cmd--permanent--add-port=80...
- kubernetes 部署mysql应用（k8s mysql部署）
-
这边仅用于测试环境，一般生产环境mysql不建议使用容器部署。这里假设安装mysql版本为mysql8.0.33一、创建MySQL配置（ConfigMap）#mysql-config.yaml...
- Spring Data Jpa 介绍和详细入门案例搭建
-
1.SpringDataJPA的概念在介绍SpringDataJPA的时候，我们首先认识下Hibernate。Hibernate是数据访问解决技术的绝对霸主，使用O/R映射（Object-Re...
- 量子点格棋上线!“天衍”邀您执子入局
-
你是否能在策略上战胜量子智能？这不仅是一场博弈更是一次量子智力的较量——量子点格棋正式上线！试试你能否赢下这场量子智局！游戏玩法详解一笔一画间的策略博弈游戏目标：封闭格子、争夺领地点格棋的基本目标是利...
- 美国将与阿联酋合作建立海外最大的人工智能数据中心
-
当地时间5月15日，美国白宫宣布与阿联酋合作建立人工智能数据中心园区，据称这是美国以外最大的人工智能园区。阿布扎比政府支持的阿联酋公司G42及多家美国公司将在阿布扎比合作建造容量为5GW的数据中心，占...
- 盘后股价大涨近8%!甲骨文的业绩及指引超预期?
-
近期，美股的AI概念股迎来了一波上升行情，微软（MSFT.US）频创新高，英伟达（NVDA.US）、台积电（TSM.US）、博通（AVGO.US）、甲骨文（ORCL.US）等多股亦出现显著上涨。而从基...
- 甲骨文预计新财年云基础设施营收将涨超70%，盘后一度涨8% | 财报见闻
-
甲骨文（Oracle）周三盘后公布财报显示，该公司第四财季业绩超预期，虽然云基建略微逊于预期，但管理层预计2026财年云基础设施营收预计将增长超过70%，同时资本支出继上年猛增三倍后，新财年将继续增至...
- Springboot数据访问(整合MongoDB)
-
SpringBoot整合MongoDB基本概念MongoDB与我们之前熟知的关系型数据库（MySQL、Oracle）不同，MongoDB是一个文档数据库，它具有所需的可伸缩性和灵活性，以及所需的查询和...
- Linux环境下，Jmeter压力测试的搭建及报错解决方法
-
概述 Jmeter最早是为了测试Tomcat的前身JServ的执行效率而诞生的。到目前为止，它的最新版本是5.3，其测试能力也不再仅仅只局限于对于Web服务器的测试，而是涵盖了数据库、JM...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- Dubai's AI Boom Lures Global Tech as Emirate Reinvents Itself as Middle East's Silicon Gateway
- OpenAI Releases o3-pro, Cuts o3 Prices by 80% as Deal with Google Cloud Reported to Make for Compute Needs
- 黄仁勋说AI Agent才是未来!但究竟有些啥影响?
- 商城微服务项目组件搭建(五)——Kafka、Tomcat等安装部署
- Python+Appium环境搭建与自动化教程
- 零配置入门:用VSCode写Java代码的正确姿
- Mycat的搭建以及配置与启动（mycat2）
- kubernetes 部署mysql应用（k8s mysql部署）
- Spring Data Jpa 介绍和详细入门案例搭建
- 量子点格棋上线!“天衍”邀您执子入局
- 标签列表
-
- oracle位图索引 (74)
- oracle批量插入数据 (65)
- oracle事务隔离级别 (59)
- oracle 空为0 (51)
- oracle主从同步 (56)
- oracle 乐观锁 (53)
- redis 命令 (78)
- php redis (88)
- redis 存储 (66)
- redis 锁 (69)
- 启动 redis (66)
- redis 时间 (56)
- redis 删除 (67)
- redis内存 (57)
- redis并发 (52)
- redis 主从 (69)
- redis 订阅 (51)
- redis 登录 (54)
- redis 面试 (58)
- 阿里 redis (59)
- redis 搭建 (53)
- redis的缓存 (55)
- lua redis (58)
- redis 连接池 (61)
- redis 限流 (51)