位图算法,内存中连续的二进制位bit,用于对大量整型数据做去重和查询。
举个例子,给定一块长度是10bit的内存空间,依次插入4,3,2,1,怎么存储?
1. 给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。
2. 把整型数4存入bitmap,对应存储的位置就是下标为4的位置,将此bit置为1。
3. 把整型数2存入bitmap,对应存储的位置就是下标为2的位置,将此bit置为1。
4. 把整型数1存入bitmap,对应存储的位置就是下标为1的位置,将此bit置为1。
5. 把整型数3存入bitmap,对应存储的位置就是下标为3的位置,将此bit置为1。
Bitmap不仅方便查询,还可以去除掉重复的整型数。
使用场景:
开发一个用户画像系统,实现用户信息的标签化。用户标签包含用户的社会属性,生活习惯,消费行为。
通过用户标签,实现多样的用户群体统计,统计用户的男女比例,统计喜欢旅游的用户数量等。
1. 建立用户名和用户ID的映射: 1->me 2->you 3->he
2.让每一个标签存储包含此标签的所有用户ID,每一个标签都是一个独立的Bitmap。
男[1,2] 女[3] 爱旅游[2] 程序员[1,2]
3. 这样,实现用户的去重和查询统计,就变得一目了然:
Bitmap在做交集和并集运算的时候也有极大的便利。位运算的高性能。
男性的程序员 110&110=110
不能做非运算,并不是除了1,2的其他都是女性,其实只有3是女性。除非提供一个全量的Bitmap,做异或即可。
一个很长的Bitmap里使用率低的话很浪费空间。
谷歌所实现的EWAHCompressedBitmap中,对存储空间做了优化:
<dependency> <groupId>com.googlecode.javaewah</groupId> <artifactId>JavaEWAH</artifactId> <version>1.1.0</version> </dependency>