bitset(位图)原理与用法
分享自我的微信订阅号“猿in”,可以搜索关注。
Bitset基础
详情
bitset(bitmap)也就是位图,因为可以用非常紧凑的格式来表示给定范围的连续数据而经常出现在各种算法设计中。
类实现了一个按需增长的位向量。位 set的每个组件都有一个boolean值。用非负的整数将BitSet的位编入索引。可以对每个编入索引的位进行测试、设置或者者清理。通过逻辑与、逻辑或者和逻辑异或者操作,可以使用一个BitSet修改另一个BitSet的内容。
默认情况下,set 中所有位的初始值都是false。
每个位 set 都有一个当前大小,也就是该位 set 当前所用空间的位数。注意,这个大小与位 set 的实现有关,所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关,并且是与实现无关而定义的。
除非另行说明,否则将 null 参数传递给BitSet中的任何方法都将导致NullPointerException。
在没有外部同步的情况下,多个线程操作一个BitSet是不安全的
下面的图来自c++库中bitset的一张图。
image
基本原理
BitSet是位操作的对象,值只有0或者1即false和true,内部维护了一个long数组,初始只有一个long,所以BitSet最小的size是64,当随着存储的元素越来越多,BitSet内部会动态扩充,最终内部是由N个long来存储,这些针对操作都是透明的。
用1位来表示一个数据能否出现过,0为没有出现过,1表示出现过。使用用的时候既可根据某一个能否为0表示,此数能否出现过。
一个1G的空间,有 8102410241024=8.5810^9bit,也就是可以表示85亿个不同的数
使用场景
常见的应用是那些需要对海量数据进行少量统计工作的时候,比方日志分析、客户数统计等等
如统计40亿个数据中没有出现的数据,将40亿个不同数据进行排序等。
现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来
Java的Bitset
Bitset这种结构尽管简单,实现的时候也有少量细节需要主要。其中的关键是少量位操作,比方如何将指定位进行反转、设置、查询指定位的状态(0或者者1)等。
本文,分析一下java中bitset的实现,抛砖引玉,希望给那些需要自己设计位图结构的需要的程序员有所启发。
Bitmap的基本操作有:
- 初始化一个bitset,指定大小。
- 清空bitset。
- 反转某一指定位。
- 设置某一指定位。
- 获取某一位的状态。
- 当前bitset的bit总位数。
参考代码:
import java.util.BitSet; public class BitSetDemo { public static void main(String args[]) { BitSet bits1 = new BitSet(16); BitSet bits2 = new BitSet(16); // set some bits for(int i=0; i<16; i++) { if((i%2) == 0) bits1.set(i); if((i%5) != 0) bits2.set(i); } System.out.println("Initial pattern in bits1: "); System.out.println(bits1); System.out.println("\nInitial pattern in bits2: "); System.out.println(bits2); // AND bits bits2.and(bits1); System.out.println("\nbits2 AND bits1: "); System.out.println(bits2); // OR bits bits2.or(bits1); System.out.println("\nbits2 OR bits1: "); System.out.println(bits2); // XOR bits bits2.xor(bits1); System.out.println("\nbits2 XOR bits1: "); System.out.println(bits2); }}package util; import java.util.Arrays;import java.util.BitSet; public class BitSetDemo { /** * 求一个字符串包含的char * */ public static void containChars(String str) { BitSet used = new BitSet(); for (int i = 0; i < str.length(); i++) used.set(str.charAt(i)); // set bit for char StringBuilder sb = new StringBuilder(); sb.append("["); int size = used.size(); System.out.println(size); for (int i = 0; i < size; i++) { if (used.get(i)) { sb.append((char) i); } } sb.append("]"); System.out.println(sb.toString()); } /** * 求素数 有无限个。一个大于1的自然数,假如除了1和它本身外,不能被其余自然数整除(除0以外)的数称之为素数(质数) 否则称为合数 */ public static void computePrime() { BitSet sieve = new BitSet(1024); int size = sieve.size(); for (int i = 2; i < size; i++) sieve.set(i); int finalBit = (int) Math.sqrt(sieve.size()); for (int i = 2; i < finalBit; i++) if (sieve.get(i)) for (int j = 2 * i; j < size; j += i) sieve.clear(j); int counter = 0; for (int i = 1; i < size; i++) { if (sieve.get(i)) { System.out.printf("%5d", i); if (++counter % 15 == 0) System.out.println(); } } System.out.println(); } /** * 进行数字排序 */ public static void sortArray() { int[] array = new int[] { 423, 700, 9999, 2323, 356, 6400, 1,2,3,2,2,2,2 }; BitSet bitSet = new BitSet(2 << 13); // 尽管可以自动扩容,但尽量在构造时指定估算大小,默认为64 System.out.println("BitSet size: " + bitSet.size()); for (int i = 0; i < array.length; i++) { bitSet.set(array[i]); } //剔除重复数字后的元素个数 int bitLen=bitSet.cardinality(); //进行排序,即把bit为true的元素复制到另一个数组 int[] orderedArray = new int[bitLen]; int k = 0; for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { orderedArray[k++] = i; } System.out.println("After ordering: "); for (int i = 0; i < bitLen; i++) { System.out.print(orderedArray[i] + "\t"); } System.out.println("iterate over the true bits in a BitSet"); //或者直接迭代BitSet中bit为true的元素iterate over the true bits in a BitSet for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { System.out.print(i+"\t"); } System.out.println("---------------------------"); } /** * 将BitSet对象转化为ByteArray * @param bitSet * @return */ public static byte[] bitSet2ByteArray(BitSet bitSet) { byte[] bytes = new byte[bitSet.size() / 8]; for (int i = 0; i < bitSet.size(); i++) { int index = i / 8; int offset = 7 - i % 8; bytes[index] |= (bitSet.get(i) ? 1 : 0) << offset; } return bytes; } /** * 将ByteArray对象转化为BitSet * @param bytes * @return */ public static BitSet byteArray2BitSet(byte[] bytes) { BitSet bitSet = new BitSet(bytes.length * 8); int index = 0; for (int i = 0; i < bytes.length; i++) { for (int j = 7; j >= 0; j--) { bitSet.set(index++, (bytes[i] & (1 << j)) >> j == 1 ? true : false); } } return bitSet; } /** * 简单使用示例 */ public static void simpleExample() { String names[] = { "Java", "Source", "and", "Support" }; BitSet bits = new BitSet(); for (int i = 0, n = names.length; i < n; i++) { if ((names[i].length() % 2) == 0) { bits.set(i); } } System.out.println(bits); System.out.println("Size : " + bits.size()); System.out.println("Length: " + bits.length()); for (int i = 0, n = names.length; i < n; i++) { if (!bits.get(i)) { System.out.println(names[i] + " is odd"); } } BitSet bites = new BitSet(); bites.set(0); bites.set(1); bites.set(2); bites.set(3); bites.andNot(bits); System.out.println(bites); } public static void main(String args[]) { //BitSet使用示例 BitSetDemo.containChars("How do you do? 你好呀"); BitSetDemo.computePrime(); BitSetDemo.sortArray(); BitSetDemo.simpleExample(); //BitSet与Byte数组互转示例 BitSet bitSet = new BitSet(); bitSet.set(3, true); bitSet.set(98, true); System.out.println(bitSet.size()+","+bitSet.cardinality()); //将BitSet对象转成byte数组 byte[] bytes = BitSetDemo.bitSet2ByteArray(bitSet); System.out.println(Arrays.toString(bytes)); //在将byte数组转回来 bitSet = BitSetDemo.byteArray2BitSet(bytes); System.out.println(bitSet.size()+","+bitSet.cardinality()); System.out.println(bitSet.get(3)); System.out.println(bitSet.get(98)); for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { System.out.print(i+"\t"); } }}使用场景解析
Redis用bitset(bitmap)来统计日活跃量
假设这样一个场景,如果每个网站有1亿的客户,那么我们怎样来统计这个网站的日登陆数或者者说有哪些客户登录过这个网站。
最常见的做法就是设计一张客户登录表:
user_login:
| user_uid | login_date |
|---|---|
| 0 | 2017-7-1 |
| 1 | 2017-7-1 |
| 0 | 2017-7-2 |
假如平均一个人一天登录1次,那么1亿个客户一个星期就会产生1 * 1 * 7 = 7亿条数据,一个月就会产生30亿条数据,这对数据库的压力是很大的,只是统计一下客户登录,没必要花费这么多的资源。
这个时候我们即可以用reids 的bitmap来处理。
客户能否登录可以用0/1来表示,0代表客户不登陆,1表示登录,那么1bit 即可以表示客户能否登录。
1亿个客户一天的数据量也就 1 0000 0000bit = 11.92m,也就是说客户一天的登录信息也就产生11.92m的数据量。一个月也就357.63m的数据量。
具体实现过程(为了试验方便,我们就假设4个客户0,1,2,3,统计两天的登录量):
mon: 1010 (客户0未登录,客户1登录,客户2未登录,客户3登录)
tue: 1101 (客户0登录,客户1未登录,客户2登录,客户3登录)
初始化数据:
127.0.0.1:6379> setbit mon 0 0(integer) 1127.0.0.1:6379> setbit mon 1 1(integer) 1127.0.0.1:6379> setbit mon 2 0(integer) 0127.0.0.1:6379> setbit mon 3 1(integer) 0127.0.0.1:6379> setbit tue 0 1(integer) 1127.0.0.1:6379> setbit tue 1 0(integer) 1127.0.0.1:6379> setbit tue 3 1(integer) 0127.0.0.1:6379> setbit tue 4 1(integer) 1假如要统计这两天都登陆的客户:
127.0.0.1:6379> bitop AND result mon tue(integer) 1127.0.0.1:6379> getbit result 0(integer) 0127.0.0.1:6379> getbit result 1(integer) 0127.0.0.1:6379> getbit result 2(integer) 0127.0.0.1:6379> getbit result 3(integer) 1可以看到mon 和 tue做and运算,得到结果result为:0001,则表示客户3连续两天都登陆,其余客户两天中只有一天登录。
基于bitset实现手机号的黑白名单方案
目前很多应用都把手机号码作为登录的账户名,本文详情一种高效的基于手机号,来实现黑白名单的方案。
在这里我先用一个例子来说明位图。
假设我有一个0到31的集合,集合里面的元素不重复,比方这样{0,3,1,5,2,19,7,8,31,21,10}。通过位图,我可以将这样的集合表示为11110001101000000001010000000001, 其中1表示该数值为下标的数存在在集合中,比方第一个1表示0存在集合中,第二个1表示1存在集合中,等等。
通过这样做,我们起码可以得到两个好处
- 节省空间–我们可以用二进制一个位来存储存储两个信息,一是存不存在,而是存在的数是多少(通过一个bit即可以得到这么多信息,真了不起)。
- 排序–从左到右遍历这个为图,我们可以得到排序的集合,比方上例中,我们可以得到集合 {0,1,2,3,7,8,10,19,21,31}
假如将所有这电话号码用位图表示,那么需要9999999999个bit (10个9, 考虑到手机号码的第一位都是1)。 9999999999 bit = (9999999999/8) byte = (9999999999 / (8 * 1024)) KB = (9999999999 / 8 10241024) M = 1192M
嗯….,1192M,内存占有还是太大,我们前期的黑白名单所占内存远远低于这个值。 考虑到手机号码的前3位都差不多,而且总数最多30个,所以考虑到手机号码拆分为两部分(头3位和剩余8位),这样就把位图的位数就降2个数量级了。所以假如我们要在内存中装入手机号码后8位,需要99999999(8个9)个bit,算一下:99999999 bit = (99999999/8) byte = (99999999 / (8 * 1024)) KB = (99999999 / 8 10241024) M = 11.92M
内存中装入头2位(手机号第一位始终为1,因而只要装入后面2位),需要99(2个9)个bit,算下
99 bit = 99/8 byte =12.375 byte。
大约12M 内存,就能表示所有手机号码,达到黑白名单。
这个比用redis等缓存,高效很多,java里面的bitset也是这个原理。
分享自我的微信订阅号“猿in”,可以搜索关注。
参考
[Redis用bitset(bitmap)来统计日活跃量]
https://blog.csdn.net/qq_30788949/article/details/74120254
[基于bitset实现手机号的黑白名单方案]
https://blog.csdn.net/nature502/article/details/52371299
[Java中BitSet的使用及详解]
https://blog.csdn.net/jiangnan2014/article/details/53735429
[Java Bitset类]
https://www.runoob.com/java/java-bitset-class.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » bitset(位图)原理与用法