2025年【数据结构】BitMap

科技前沿 • 2025-03-15 11:50 • 阅读 25

大家好，我是讯享网，很高兴认识大家。

(转载请删除括号里的内容)

一、BitMap介绍

二、BitMap应用场景

1、查询统计、定位查询，排序，去重

2、取两个集合的交集，并集等

三、BitMap的实现

1、自己动手实现BitMap

2、JDK中实现的BitMap —— BitSet 集合

讯享网

3、谷歌实现的BitMap —— EWAHCompressedBitmap

四、BitMap总结

一、BitMap介绍

BitMap，即位图，使用每个位表示某种状态，适合处理整型的海量数据。本质上是哈希表的一种应用实现，原理也很简单，给定一个int整型数据，将该int整数映射到对应的位上，并将该位由0改为1。例如：

// 存在一个int整型数组 int[] arr = new int[]{6,2,7,14,3};

讯享网

arr数组中最大值为14，考虑位的下标从0开始，需要长度为15的bit，因此每个bit代表着0~14的整数，如图所示：

很显然，使用 BitMap 存储这个数组只使用了使用15bit，而使用 HashSet 或 HashMap 的话，一个数组元素会存储为一个int，而一个int占4个byte，即4*8=32bit，这里有5个数组元素则需要5*32=160bit，这样的话，使用 BitMap 存储一个元素则可以节省32倍的内存空间。因此，BitMap 的优势就不言而喻了。

俗话说，结构决定功能，BitMap非常适合对整型的海量数据进行查询统计、排序、去重；适合对两个集合做交集、并集运算，但不支持非运算，如果需要进行非运算则需要提供一个全量的BitMap才行。另外，Java中的 BitSet 集合是对 BitMap 算法相对简单的实现，而谷歌开发的 EWAHCompressedBitmap 是一种更为优化的实现，后面再详细分析下。

二、BitMap应用场景

举个很常见的例子，比如我们项目的数据库表中经常会有ID列，通过该ID列可以映射我们需要统计查询的列，或需要去重的列，比如有一张订单表：

order_id	sale_name	to_addr	to_consumer	order_time
1	十足便利店	高新区	张三	2021-04-07 12:16:20
2	领几便利店	高新区	李四	2021-04-07 12:16:24
3	十足便利店	政务区	王二	2021-04-07 17:56:00
4	十足便利店	经开区	熊大	2021-04-07 18:26:00
5	沙县小吃	政务区	张三	2021-04-07 18:00:00

2025年【数据结构】BitMap

一、BitMap介绍

二、BitMap应用场景

相关推荐