可以参考自己的微信订阅号“ape in”搜索关注。 Bitset基本细节bitset(bitmap)也是一种位图，经常出现在各种算法设计中，因为它能以非常紧凑的格式表示给定范围内的连续数据。 类实现了一个按需增长的位向量。 该位的每个组成部分都有一个布尔值。 用非负整数索引位集位 每个索引位都可以被测试、设置或清除。 通过逻辑AND、逻辑OR和逻辑OR，可以使用一个位集修改另一个位集的内容。 默认情况下，set中所有位的初始值都是假的。 每个位组都有一个当前大小，即该位组当前使用的空间位数。 请注意，这个大小与位集的实现有关，因此它可能因实现而异。 位组的长度与位组的逻辑长度相关，并且独立于实现来定义。 除非另有说明，否则将null参数传递给BitSet中的任何方法都会导致NullPointerException。 如果没有外部同步，多个线程操作一个位集是不安全的。下图来自c++库中的位集图。 图像位集的基本原理是位操作的对象，值只有0或1，即假和真。它内部维护一个长数组，开头只有一个long，所以BitSet的最小大小是64。当存储的元素越来越多时，BitSet会在内部动态扩展，最后按N longs存储。这些操作是透明的。 1位用来表示一段数据是否曾经出现过，0表示从未出现过，1表示出现过。 用的时候可以注明某个数字能不能是0，这个数字是否曾经出现过。 一个1G的空间，加上8102410241024=8.5810^9bit，可以代表85亿种不同的数据使用场景。常见的应用是那些需要对海量数据做一点统计工作的应用，比如日志分析、客户统计等。比如对40亿个数据中没有出现的数据进行计数，对40亿个不同的数据进行排序等等。 现在有1000万个随机数，从1亿到1亿不等。 现在要求写一个算法，找出1亿到1亿之间不在随机数里的数。Java BitsetBitset这个结构很简单，但是实现的时候有几个细节需要main。 其中，关键是少量的位操作，比如如何反相和置位指定位，查询指定位的状态(0或1)。 本文分析了bitset在java中的实现，希望对需要自己设计位图结构的程序员有所启发。 位图的基本操作是:初始化一个位集并指定大小。 空位集 反转指定的位 设置指定的位。 得到一点地位。 当前位集的总位数 参考代码:导入Java . util . bitset；public class BitSet demo { public static void main(String args[]){ BitSet bits 1 = new BitSet(16)；比特集bits2 =新比特集(16)；//为(int i=0设置一些位；我& lt16;i++){ if((I % 2)= = 0)bits 1 . set(I)；if((i%5)！= 0)bits 2 . set(I)；} system . out . println(" bit S1中的初始模式:")；system . out . println(bits 1)；system . out . println(" \ n bits 2中的初始模式:")；system . out . println(bits 2)；//和位bits 2 . AND(bits 1)；System.out.println("\nbits2和bits 1:")；system . out . println(bits 2)；//或者bits bits 2 . OR(bits 1)；System.out.println("\nbits2或bits 1:")；system . out . println(bits 2)；//XOR bits bits 2 . XOR(bits 1)；system . out . println(" \ n bits 2 XOR bits 1:")；system . out . println(bits 2)；} }包util导入Java . util . arrays；导入Java . util . bitset；class bitset demo {/* * * Find char * */public static void contained chars(string str){ bitset used = new bitset()；for(int I = 0；我& ltstr . length()；i++)used . set(str . charat(I))；//为char StringBuilder sb = new StringBuilder()设置位；某人追加("[")；int size = used . size()；system . out . println(size)；for(int I = 0；我& lt尺寸；i++){ if(used . get(I)){ sb . append((char)I)；} } sb . append("]")；system . out . println(sb . tostring())；}/* * *素数有无穷多个。 大于1的自然数，如果不能被除1以外的其他自然数和它本身(除0)整除，则称为素数(素数)，否则称为合数*/public static void compute prime(){ bitset sieve = new bitset(1024)；int size = sieve . size()；for(int I = 2；我& lt尺寸；i++)sieve . set(I)；int final bit =(int)math . sqrt(sieve . size())；for(int I = 2；我& ltfinalBiti++)if(sieve . get(I))for(int j = 2 * I；j & lt尺寸；j+= I)sieve . clear(j)；int counter = 0；for(int I = 1；我& lt尺寸；i++){ if(sieve . get(I)){ system . out . printf(" % 5d "，I)；if(++counter % 15 = = 0)system . out . println()；} } system . out . println()；}/* * *排序编号*/public static void sortray(){ int[]array = new int[]{ 423，700，9999，2323，356，6400，1，2，3，2，2，2 }；BitSet bitSet =新的位集(2 & lt& lt13);//虽然容量可以自动扩展，但是在构造的时候尽量指定估计的大小，默认值为64 system . out . println(" bit set size:"+bit set . size())；for(int I = 0；我& lt数组.长度；i++){ bitset . set(array[I])；}//剔除重复数后的元素个数int bitLen = bitset . cardinality()；//Sort，即将bit为true的元素复制到另一个数组int[]Ordered Array = new int[Bitlen]；int k = 0；for(int I = bitset . nextset bit(0)；我& gt= 0;I = bit set . nextset bit(I+1)){ ordered array[k++]= I；} System.out.println("订购后:")；for(int I = 0；我& lt比特伦；i++){ system . out . print(ordered array[I]+" \ t ")；} System.out.println("迭代位集中的真位")；//或者直接迭代for (int I = bitset.nextsetbit (0))的位集中的真位；我& gt= 0;I = bit set . nextset bit(I+1)){ system . out . print(I+" \ t ")；} system . out . println("-")；}/* * *将BitSet对象转换为bytearray * @ param BitSet * @ return */public static byte[]BitSet 2 byte数组(BitSet bit set){ byte[]bytes = new byte[BitSet . size()/8]；for(int I = 0；我& ltbitset . size()；i++){ int index = I/8；int offset = 7-I % 8；bytes[index] |= (bitSet.get(i)？1:0)& lt；& lt偏移；}返回字节；}/* * *将ByteArray对象转换为bitset * @ param bytes * @ return */public static bitset ByteArray 2 bitset(byte[]bytes){ bitset bitset = new bitset(bytes . length * 8)；int index = 0；for(int I = 0；我& lt字节.长度；i++){ for(int j = 7；j & gt= 0;j - ) { bitSet.set(index++，(bytes[I]& amp；(1 & lt& ltj))& gt；& gtj == 1？真:假)；} }返回位集；}/* * *简单使用示例*/public static void简单示例(){string names [] = {"Java "，" source "，" and "，" support " }；BitSet bits = new BitSet()；for (int i = 0，n = names.length我& ltn；i++) { if ((names[i].length()% 2)= = 0){ bits . set(I)；} } System.out.println(位)；system . out . println(" Size:"+bits . Size())；system . out . println(" Length:"+bits . Length())；for (int i = 0，n = names.length我& ltn；i++) { if(！bits . get(I)){ system . out . println(names[I]+“是奇数”)；} } BitSet bites = new BitSet()；bites . set(0)；bites . set(1)；bites . set(2)；bites . set(3)；bites.andNot(位)；system . out . println(bites)；} public static void main(string args[]){//Bitset使用示例bitsetdemo.containchars ("how do？你好”)；bitset demo . computeprime()；bitset demo . sort array()；bitset demo . simple example()；//BitSet和字节数组翻译示例bit set bit set = new bit set()；bitSet.set(3，true)；bitSet.set(98，true)；system . out . println(bitset . size()+"，"+bitset . cardinality())；//将BitSet对象转换为字节数组byte[]bytes = BitSet demo . BitSet 2 byte数组(BitSet)；system . out . println(arrays . tostring(bytes))；//将字节数组转回bitset = bitset demo . bytearray 2 bitset(bytes)；system . out . println(bitset . size()+"，"+bitset . cardinality())；system . out . println(bitset . get(3))；system . out . println(bitset . get(98))；for(int I = bitset . nextset bit(0)；我& gt= 0;I = bit set . nextset bit(I+1)){ system . out . print(I+" \ t ")；}}}使用场景分析Redis并使用bitset(位图)来统计日常活动。假设这样一个场景，如果每个网站都有1亿客户，我们怎么统计这个网站的日登录次数或者有哪些客户登录过这个网站？ 最常见的方式是设计一个客户登录表单:user _ log in:user _ uid log in _ date 02017-7-112017-7-102017-7-2。如果一个普通人每天登录一次，1亿个客户一周会产生1 * 1 * 7 = 7亿条数据，一个月会产生30亿条数据。 这时候我们可以用reids的位图来处理。 客户是否可以登录可以用0/1来表示。0表示客户不登录，1表示客户登录。那么1bit可以表示客户是否可以登录。 一亿客户一天的数据量是1 0000 0000bit = 11.92m，也就是说客户一天的登录信息会产生11.92m的数据量。 一个月只有357.63m的数据。 具体实现过程(为了实验方便，我们假设四个客户0、1、2、3，统计两天的登录量):周一:1010(客户0未登录，客户1登录，客户2登录，客户3登录)周二:1101(客户0登录，客户1未登录，客户2登录，客户3登录)初始化数据:120。setbit mon 0 0(整数)1127 . 0 . 0 . 1:6379 & gt；setbit mon 1 1(整数)1127 . 0 . 0 . 1:6379 & gt；setbit mon 2 0(整数)0127 . 0 . 0 . 1:6379 & gt；setbit mon 3 1(整数)0127 . 0 . 0 . 1:6379 & gt；setbit tue 0 1(整数)1127 . 0 . 0 . 1:6379 & gt；setbit tue 1 0(整数)1127 . 0 . 0 . 1:6379 & gt；setbit tue 3 1(整数)0127 . 0 . 0 . 1:6379 & gt；设置tue41 (integer) 1如果要统计这两天登录的客户:127.0.0.1: 6379 >: bitop和result mon tue(integer)1127 . 0 . 0 . 1:6379 & gt；getbit结果0(整数)0127 . 0 . 0 . 1:6379 & gt；getbit结果1(整数)0127 . 0 . 0 . 1:6379 & gt；getbit结果2(整数)0127 . 0 . 0 . 1:6379 & gt；得到结果3(整数)1可以看到周一和周二做and运算，结果是0001，表示客户3连续两天登录，其余客户两天只登录一天。 基于bitset实现手机号码黑白列表的方案。目前很多应用都是用手机号作为登录账号名称。本文详细介绍了一种基于手机号码实现黑白名单的高效方案。 这里我将用一个例子来说明位图。 假设我有一个0到31的集合，集合中的元素不重复，像这样{0，3，1，5，2，19，7，8，31，21，10} 通过位图，我可以把这样一个集合表示为111000110000000010000001，其中1表示集合中存在带下标的数，比如第一个1表示集合中存在0，第二个1表示集合中存在1，以此类推。 这样做，我们至少可以获得两个节省空间的好处——可以用一个二进制位存储两条信息，一个是是否存在，而是存在多少条信息(一个位可以获得这么多信息，太神奇了)。 排序——从左到右遍历这张图片，我们可以得到排序后的集合。例如，在上面的例子中，我们可以得到集合{0，1，2，3，7，8，10，19，21，31}。如果所有这些电话号码都用位图表示，那么9999999位(10个9，手机号码的号码是第一位) 999999999 bit =(99999999/8)byte =(9999999/(8 * 1024))KB =(9999999/8 10241024)m = 192m，um...，1192M，内存 考虑到手机号的前三位几乎相同，总数高达30，所以考虑将手机号拆分成两部分(前三位和剩下的八位)，从而将位图的位数减少两个数量级。 所以如果要在内存中安装手机号的后8位，需要9999999(8 ^ 9)位，做一下数学:9999999 bit =(999999/8)byte =(999999/(8 * 1024))KB =(999999/8 10241024)m = 11.92m内存加载前两位(手机号第一位始终为1，手机第一位 12M左右内存可以代表所有手机号码，达到黑白名单。 这比使用redis等缓存要高效得多，java中的bitset也是同样的原理。 可以参考自己的微信订阅号“ape in”搜索关注。 参考【Redis使用bitset(位图)统计日活跃】https://blog.csdn.net/QQ _ 30788949/Article/details/74120254【基于bitset的手机号码黑白列表方案】https://blog.csdn.net/nature502/文章/details/52371299【Java中BitSet的使用及详细讲解】https://blog.csdn.net/jiangnan2014/article/details/53735429【Java BitSet类】https://www.runoob.com/java/java-bitset-class