文档章节

JDK8--BitSet 笔记

路人丁语
 路人丁语
发布于 2017/06/21 09:59
字数 1609
阅读 19
收藏 0
点赞 0
评论 0

源码理解:

1.内部是一个long[],而数组内每个元素有8*8=64位组成,bitset.操作的就是这64个位

2.每个元素中的64位默认都是0

3.此时,可以把BitSet看成一个是二维数组了,一维不固定,二维固定长度是64(可以想象一下Excel表格,行数不固定,列项是64,里面的数都是0)

4.如果set(3):表示把[0][3]处的0改成1

5.Bitset有size()和length()之分:size:位数的总和,64的倍数;length:数组的长度

6.wordsInUse字段记录的是:long[]中存有数据的角标+1

bits1:{0, 3, 6, 9, 12, 15}

bits2:{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

 bits1 AND bits2:
bits1{3, 6, 9, 12}
bits2{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

 bits2 AND bits1:
bits1{0, 3, 6, 9, 12, 15}
bits2{3, 6, 9, 12}

 bits1 OR bits2:
bits1{0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15}
bits2{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}
 bits2 OR bits1:
bits1{0, 3, 6, 9, 12, 15}
bits2{0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15}

 bits1 XOR bits2:
bits1{0, 1, 2, 4, 7, 8, 11, 13, 14, 15}
bits2{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

 bits2 XOR bits1:
bits1{0, 3, 6, 9, 12, 15}
bits2{0, 1, 2, 4, 7, 8, 11, 13, 14, 15}

 bits1 andNot bits2:
bits1{0, 15}
bits2{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

 bits2 andNot bits1:
bits1{0, 3, 6, 9, 12, 15}
bits2{1, 2, 4, 7, 8, 11, 13, 14}

在学习是感谢这位博主 https://my.oschina.net/cloudcoder/blog/294810,一下内容就是他的博客

BitSet简介

    类实现了一个按需增长的位向量。位 set 的每个组件都有一个boolean值。用非负的整数将BitSet的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作,可以使用一个BitSet修改另一个BitSet的内容。

    默认情况下,set 中所有位的初始值都是false。

    每个位 set 都有一个当前大小,也就是该位 set 当前所用空间的位数。注意,这个大小与位 set 的实现有关,所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关,并且是与实现无关而定义的。

    除非另行说明,否则将 null 参数传递给BitSet中的任何方法都将导致NullPointerException。

    在没有外部同步的情况下,多个线程操作一个BitSet是不安全的

基本原理

    BitSet是位操作的对象,值只有0或1即false和true,内部维护了一个long数组,初始只有一个long,所以BitSet最小的size是64,当随着存储的元素越来越多,BitSet内部会动态扩充,最终内部是由N个long来存储,这些针对操作都是透明的。

    用1位来表示一个数据是否出现过,0为没有出现过,1表示出现过。使用用的时候既可根据某一个是否为0表示,此数是否出现过。

    一个1G的空间,有 8*1024*1024*1024=8.58*10^9bit,也就是可以表示85亿个不同的数

使用场景

    常见的应用是那些需要对海量数据进行一些统计工作的时候,比如日志分析、用户数统计等等

    如统计40亿个数据中没有出现的数据,将40亿个不同数据进行排序等。
    现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来

代码示例

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");
		}
	}
}

© 著作权归作者所有

共有 人打赏支持
路人丁语
粉丝 4
博文 41
码字总数 16324
作品 0
西安
程序员
bitset学习笔记

bitset提供位操作的数据集合。 bitset() bitset(unsigned long val)创建bitset 例如bitset<8> bs,创建一个8位的bitset 1.支持!=, ==, &=, ^=, |=, ~, <<=, >>=, []操作符号 2.any() 函数返回......

ryany ⋅ 2011/04/11 ⋅ 0

Elasticsearch结构化搜索_filter执行原理深度剖析(bitset机制与caching机制)

课程大纲 (1)在倒排索引中查找搜索串,获取document list date来举例 到倒排索引中一找,发现2017-02-02对应的document list是doc2,doc3 (2)为每个在倒排索引中搜索到的结果,构建一个b...

小红牛 ⋅ 05/21 ⋅ 0

Java.util包下BitSet的用法

BitSet:是一个字节集合,用它可以表示整数和进行求两个集合的交集、并集等运算。 我们知道,计算机存储的最小单位是比特bit,而我们在java程序中的最小单位是字节Byte,他们之间的换算关系是...

吴小河 ⋅ 2016/07/12 ⋅ 2

关于BitMap的疑问

java中实现BitMap的类是BitSet,BitSet有个构造方法是BitSet(int nbits) 中文的解释是“创建一个位 set,它的初始大小足以显式表示索引范围在0到nbits-1的位。” 但是为什么 java.util.BitS...

luger ⋅ 2012/11/13 ⋅ 0

若只有4KB内存可用,该如何打印数组中所有重复的元素

/** * 功能:给定一个数组,包含1到N的整数,N最大为32000,数组可能含有重复的值,且N的取值不定。 * 若只有4KB内存可用,该如何打印数组中所有重复的元素。 / [java] view plain copy /* ...

一贱书生 ⋅ 2016/11/23 ⋅ 0

redis相关知识积累

在学习redis时总结的问题 setbit的作用 参考自: https://www.zhihu.com/question/27672245 作者:Andy 链接:https://www.zhihu.com/question/27672245/answer/123641959 来源:知乎 著作权归......

wangtenfee ⋅ 2017/05/21 ⋅ 0

c++ bitset coredump

c++ bitset coredump include include using namespace::std; int main() { size_t const size = 500000000; #5亿 bitset b; return 0; } Segmentation fault (core dumped) 改成5000 0000 是......

larryaxie ⋅ 2016/07/14 ⋅ 3

BitSet的使用场景及简单示例

BitSet简介 类实现了一个按需增长的位向量。位 set 的每个组件都有一个boolean值。用非负的整数将BitSet的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和...

cloud-coder ⋅ 2014/07/25 ⋅ 4

BitSet与Byte数组互转

BitSet是位操作的对象,值只有0或1即false和true,最常用的地方是用户、系统开关,原理是内部维护了一个long数组,初始只有一个long,所以BitSet最小的size是64,当随着开关越来越多,会动态...

恐怖幻觉 ⋅ 2013/05/05 ⋅ 1

【C++ Primer学习笔记】第3章:标准库类型

除第2章介绍的基本数据类型外,C++还定义了一个内容丰富的抽象数据类型标准库。 3.1命名空间的using声明 在编译我们提供的实例程序前,读者一定要注意在程序中添加适当的#include和using说明...

Geek_Hao ⋅ 2012/03/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mahout基于内存的DataMode 推荐引擎Demo2

Mahout基于内存的DataMode 推荐引擎Demo2 //注释的部分是基于文件也可以理解为基于日志文件的, //DataModel 可以有很多种,实现abstractDataMode的子类,原则上都可以作为数据源,个人觉得,...

xiaomin0322 ⋅ 12分钟前 ⋅ 0

Docker部署Tomcat及Web应用

一、在线下载docker yum install -y epel-releaseyum install docker-io # 安装dockerchkconfig docker on # 加入开机启动service docker start # 启动docker服务 1 ...

Jeam_ ⋅ 12分钟前 ⋅ 0

研发运营一体化能力成熟度模型

研发运营一体化是指在 IT 软件及相关服务的研发及交付过程中,将应用的需求、开发、测试、部 署和运营统一起来,基于整个组织的协作和应用架构的优化,实现敏捷开发、持续交付和应用运营的无...

stars永恒 ⋅ 18分钟前 ⋅ 0

jQuery缩小放大触发事件

jquery的resize()方法使用 <html> <head> <script type="text/javascript" src="/jquery/jquery.js"></script> <script type="text/javascript"> var i = 0; $(document).ready(function(){ ......

RobertZou ⋅ 18分钟前 ⋅ 0

eclipse python 搭建

https://jingyan.baidu.com/article/9113f81b68ebce2b3214c7e0.html https://www.cnblogs.com/ZhangRuoXu/p/6397756.html https://blog.csdn.net/zhangphil/article/details/78962159 字符集......

之渊 ⋅ 19分钟前 ⋅ 0

weex,react native,flutter

weex: 一次编写,处处运行 RN: 学一次,到处写(针对安卓,IOS平台特性 各自写,会有很大一部分是一样的代码) 这些方案是否真正的解决了跨平台问题呢?从目前的状况来看,很显然是没有的,因...

东东笔记 ⋅ 25分钟前 ⋅ 0

Spring Cloud微服务分布式云架构-集成项目

Spring Cloud集成项目有很多,下面我们列举一下和Spring Cloud相关的优秀项目,我们的企业架构中用到了很多的优秀项目,说白了,也是站在巨人的肩膀上去整合的。在学习Spring Cloud之前大家必...

明理萝 ⋅ 30分钟前 ⋅ 1

SpringMVC图片上传问题解决

当我们上传图片时一直发现: MultipartFile file = null; if (request instanceof MultipartHttpServletRequest) 匹配不上, 解决方案: 在前端xml加入如下配置代码即可 <!-- 图片上传bean --...

泉天下 ⋅ 32分钟前 ⋅ 0

Spring表达式语言(SpEL)

1、SpEL引用 Spring EL在bean创建时执行其中的表达式。此外,所有的Spring表达式都可以通过XML或注解的方式实现。下面将使用Spring表达式语言(SpEL),注入字符串,整数,Bean到属性。 SpEL的...

霍淇滨 ⋅ 48分钟前 ⋅ 0

Gradle使用阿里云镜像

gradle 生命周期中有一个初始化( Initialization )的过程,这个过程运行在 build script 之前,我们可以在这个地方做一点系统全局的设置,如配置仓库地址。 你可以在以下几个位置实现仓库地址...

明MikeWoo ⋅ 56分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部