BitSet的使用场景及简单示例_bitset使用场景-程序员宅基地

技术标签: 计算机原理  lang  

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

 

参考:

http://blog.csdn.net/haojun186/article/details/8482343

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jfengamarsoft/article/details/86076754

智能推荐

以前的的华为手机可不可以用鸿蒙系统_华为启用鸿蒙操作系统后,原有的华为手机可以更换为鸿蒙系统吗?...-程序员宅基地

文章浏览阅读853次。华为启动鸿蒙操作系统后,根据笔者的经验,原有的华为手机可能只有部分可以升级到鸿蒙系统已经在手机厂混迹多年仍一事无成的笔者,对于这个问题还是有一定的发言权,因为任何一个全新的手机开发项目,还是一个旧的维护项目,对于操作系统的适配是一个非常复杂的系统工程,其难度不亚于重新开工一个新项目。不知道大家有没发现一个规律,Google的安卓操作系统几乎每年都会发布一个全新的版本,手机芯片厂商也会跟随着每年也会...

终极解决vc++1935安装错误办法_错误1935-程序员宅基地

文章浏览阅读3.9k次,点赞8次,收藏10次。看到网上有很多关于这个错误的解决方式,但是千篇一律都是改什么注册表,运行什么命令,而操作到最后发现都没用,甚至反而多出很多乱七八糟的东西研究发现,这个1935错误特别集中在vc++2005和2008中,部分2010也会,其它office的1935都是连带的,所以根本问题应该在vc++这个问题从WindowsXP时代就有,经过Windows Vista/7/8/8.1,带现在的Windows10依然存在,所以不可能是某个版本特有的这个问题涉及的范围也很广,包括AutoCAD、3dsMax、Revit、._错误1935

iOS 防 DNS 污染方案调研 --- Cookie 业务场景-程序员宅基地

文章浏览阅读199次。概述本文将讨论下类似这样的问题:WKWebView 对于 Cookie 的管理一直是它的短板,那么 iOS11 是否有改进,如果有,如何利用这样的改进?采用 IP 直连方案后,服务端返回的 Cookie 里的 Domain 字段也会使用 IP 。如果 IP 是动态的,就有可能导致一些问题:由于许多 H5 业务都依赖于 Cookie 作登录态校验,而...

你不知道的那些,说说&和&&的区别-程序员宅基地

文章浏览阅读202次。说说&和&&的区别&和&&都可以用作逻辑与的运算符,表示逻辑与(and),当运算符两边的表达式的结果都为true时,整个运算结果才为true,否则,只要有一方为false,则结果为false。&&还具有短路的功能,即如果第一个表达式为false,则不再计算第二个表达式。例如,对于if(str!=null&&!str.equals(“”))的表达式,当str为null时,后面的表达式不会执行,所以不会出现NullpointE_&&

计算机网络(13)-应用层(一)_某计算机a需要访问域名-程序员宅基地

文章浏览阅读266次。目录一、域名系统DNS(Domain Name System)1、域名2、域名解析的过程3、内网的DNS服务器二、动态主机配置协议DHCP三、文件传输——FTP协议四、Telent协议——远程终端协议五、RDP协议——远程桌面协议网络模型一、域名系统DNS(Domain Name System)DNS服务器的作用:负责解析域名,把域名解析成IP1、域名跟域名:. // 所有域名都是从根域名开始的,根域名就是一个小圆点顶级域名:com(商用)、edu_某计算机a需要访问域名

抓取速度提升3倍!Python的这个编库你用上了吗?_a下面那个模块是加快网页下载速度 ? a. asyncio b. plotly c. pandas -程序员宅基地

文章浏览阅读211次。但是,无论是否,您也同时发送多个请求,并在它们返回时处理的结果,这种方式的提升请求的效果是非常显着的。我们的第一次不会有可能同时遇到问题,所以在使用每个URL的时候可能会运行它的请求情况......好吧,它会同时执行所有这些请求。运行到一个函数,并在允许的时候将发生切换在我们的例子中,HTTP请求切换是允许的。在这个页面中,我们注意到来自时间的响应时,响应时,这然然。的优势可以选择不同的站点使用和使用不同的区域,我们可以选择不同的区域来使用不同的使用方式,来获取不同的使用方式,带来自己的不同之处。..._a下面那个模块是加快网页下载速度 ? a. asyncio b. plotly c. pandas d. numpy

随便推点

第九周 项目一-猴子选大王(数组版)-程序员宅基地

文章浏览阅读248次。/* Copyright (c)2015,烟台大学计算机与控制工程学院 All rights reserved. 文件名称:猴子选大王(数组版).cpp 作 者:林颖完成日期:2016年10月24日 版 本 号:v1.0 问题描述: 一群猴子,编号是1,2,3 …m,这群猴子(m个)按照1-m的顺序围坐一圈。从第1只开始数,每数到第n个,该猴子就要离开此圈

maven冲突报红线,‘dependencies.dependency.version‘ for xxxx is missing. @ xxxxxx:[unknown-version]-程序员宅基地

文章浏览阅读1.5k次。问题:子项目继承父POM,本应该继承版本号,发现子标签报错,错误如下:omitted for conflict with unknow,忽略的冲突的版本。冲突原因可以参考一下这篇文章:https://blog.csdn.net/liu865033503/article/details/85139193问题发现:父节点定义的POM文件,外部有<dependencyManagement>标签,为了让子项目继承。<dependency> <group_dependencies.dependency.version

Java随堂练习-1 三个程序运用赋值、输入、输出_java赋值与输出的练习-程序员宅基地

文章浏览阅读169次。1.编写一个程序模拟这个过程:两个整数分别保存在两个变量中,将这两个变量的值互换,并输出互换后的结果。2. 商店为员工提供了基本工资、物价津贴以及房租津贴。 其中,物价津贴为基本工资的40%。房租津贴为基本工资的25%。要求从控制台输入基本工资,并计算输出实领工资。3. 银行提供了整存整取定期储蓄业务,其存期为一年、两年、三年、五年,到期凭存单支取本息。 编写一个程序,输入存入的本金数目, 计算假设存一年、两年、三年和五年,到期取款时,银行应该支付的本息分别是多少,输出结果。_java赋值与输出的练习

人生与下棋-程序员宅基地

文章浏览阅读497次。· 人生犹如下棋。高者能看出五步七步甚至十几步棋,低能者只能看两三步。高手顾大局,谋大势,不以一子一地为重,以最终赢棋为目标;低手则寸土必争,结果辛辛苦苦地屡犯错误,以失败告终。赢家一般能表示谦虚,输家却往往不服,弄得赢家不舒畅。如果赢家盛气凌人,双方必然伤和气。最好是赢者宽容谦雅,输者恭谦好学,共酿斯文气氛,教者、学者都愉快。学问之

MySQL实战(四):多表查询_mysql查询每个院系有多少人-程序员宅基地

文章浏览阅读3.1k次,点赞3次,收藏23次。MySQL多表查询练习_mysql查询每个院系有多少人

选择IT我不曾后悔?希望高人指点迷津-程序员宅基地

文章浏览阅读171次。小弟周志豪,男,未婚,23岁 8) ,来自广西壮族自治区来宾市凤凰镇的一个农村。2005年由于上瘾网络游戏,放弃了学业,当时初中毕业,在社会上瞎混了5年了,钱没赚到,技术没学到,媳妇没讨到。 2011年4月份到浙江临海跟姐姐在这边打工,姐姐是世界最疼我人之一,当时姐姐说我一个大男人没有点技术在外面打工不是办法,姐姐想让我去学点技术,问我想学什么,当时想想觉得学计算机在现在..._学舞蹈我不曾后悔