我们知道bit-map在大数据处理方面有着很大的用途,比如排序,去重等。
JDK 从1.0开始就提供了 java.util.BitSet 来对bit-map的支持。BitSet的set,get操作主要是通过 “位运算” 进行的。
BitSet的核心是一个 long的数组:
- /*
- * BitSets are packed into arrays of "words." Currently a word is
- * a long, which consists of 64 bits, requiring 6 address bits.
- * The choice of word size is determined purely by performance concerns.
- */
- private final static int ADDRESS_BITS_PER_WORD = 6;
- private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
- private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
- /* Used to shift left or right for a partial word mask */
- private static final long WORD_MASK = 0xffffffffffffffffL;
- /**
- * The internal field corresponding to the serialField "bits".
- */
- private long[] words;
- /**
- * The number of words in the logical size of this BitSet.
- */
- private transient int wordsInUse = 0;
- /**
- * Whether the size of "words" is user-specified. If so, we assume
- * the user knows what he's doing and try harder to preserve it.
- */
- private transient boolean sizeIsSticky = false;
从bit的角度看,words 应该是一个 二维的bit数据, bit [ ] [64] word, 当然 JDK中没有 bit 这个基本的数据类型。但是JDK提供了丰富的位运算符。每个bit 只有两个值 0 和1(ture 和false)。
bit-map的典型应用场景(伪码表示):
有一个 bit数组 bit [ ] bArray = new bit [ 1024 ]。 要对若干非负整数进行排序,例如:{ 2, 5, 78, 58, 11}。使用bit-map的做法是:
- bArray[2] = 1;
- bArray[5] = 1;
- bArray[78] = 1;
- bArray[58] = 1;
- bArray[11] = 1;
然后顺序遍历bArray就行了。
同样对于BitSet的方法一样,只不过要调用它的set方法,源码如下:
- /**
- * Sets the bit at the specified index to {@code true}.
- *
- * @param bitIndex a bit index
- * @throws IndexOutOfBoundsException if the specified index is negative
- * @since JDK1.0
- */
- public void set(int bitIndex) {
- if (bitIndex < 0)
- throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
- int wordIndex = wordIndex(bitIndex);
- expandTo(wordIndex);
- words[wordIndex] |= (1L << bitIndex); // Restores invariants
- checkInvariants();
- }
如果将 long [ ] words 理解成 bit [ ] [ 64 ] words的话
第一步,先算出一维(wordIndex(int bitIndex) 方法)
- /**
- * Given a bit index, return word index containing it.
- */
- private static int wordIndex(int bitIndex) {
- return bitIndex >> ADDRESS_BITS_PER_WORD;
- }
notice: ADDRESS_BITS_PER_WORD = 6.
第二步,使用位运算对对应的bit进行赋值为1, words[ wordIndex ] |= (1L << bitIndex).
BitSet的get方法和Set方法一样,先确定一维,再通过位运算得到二维中对应的值。
是不是感觉很美妙,通过long数组 再加上 位运算 可以模拟出 bit数组。当然,我们也可以使用int数组或者double行数据来构造 bit数组
相关推荐
Java提供日期(Data)类、日历(Calendar)类,随机数(Random)类,堆栈(Stack)、向量(Vector) 、位集合(Bitset)以及哈希表(Hashtable)等类来表示相应的数据结构
Java.util包是Java标准库中的核心包之一,它包含了大量用于日常编程的工具类和接口。这个包在Java 2版本中得到了显著增强,引入了许多重要的数据结构和算法,为Java程序员提供了更丰富的功能。 首先,Java.util包中...
Java.util包是Java编程语言中的核心包之一,它包含了大量用于日常编程的类和接口,是Java程序员必备的知识点。本教程重点讲解了Java.util包中的主要组件和使用方法,旨在帮助初学者深入理解并熟练运用这个包。 1. *...
### Java的.awt包和.java.util包的区别 #### Java.util包详解 Java.util包是一个非常重要的标准库之一,其中包含了大量有用的类和接口,为开发者提供了丰富的功能。此包中的类和接口可以分为以下几大类别: 1. **...
介绍Java的实用工具类库java.util包。在这个包中,Java提供了一些实用的方法和数据结构。例如,Java提供日期(Data)类、日历(Calendar)类来产生和获取日期及时间,提供随机数(Random)类产生各种类型的随机数,还提供...
### Java_util 工具包详解 #### 一、引言 `java.util`包作为Java标准库中的一个重要组成部分,提供了大量的实用工具类和接口,旨在简化开发者在处理数据结构、日期时间、事件处理等方面的工作。这个包包含了如日期...
例如,Java提供日期(Data)类、日历(Calendar)类来产生和获取日期及时间,提供随机数(Random)类产生各种类型的随机数,还提供了堆栈(Stack)、向量(Vector)、位集合(Bitset)以及哈希表(Hashtable)等类来表示相应的数据...
位集合类 BitSet 是 Java.util 包中一个非常实用的类,提供了一些方法来处理位集合数据结构。 BitSet 类中有两个常用的方法: (1) public BitSet():创建一个位集合对象。 (2) public void set(int bitIndex):...
以上只是`java.util`包中部分关键知识点的概述,实际上,该包还包括其他如排序算法(`Comparator`)、位集(`BitSet`)、事件模型(`EventObject`)等众多内容。熟练掌握这些工具类和接口,对于编写高质量的Java程序...
Java util包中还提供了许多其它有用的类,例如 BitSet类、 Dictionary类、 EventObject类、 ResourceBundle类、 StringTokenizer类等等。 Java util包提供了许多实用的工具类和数据结构,能够帮助开发者快速地编写...
Java编程语言的基础知识涵盖了许多方面,这里我们主要关注的是`java.util`包,这是一个非常重要的工具类库,提供了丰富的数据结构和实用方法。在Java开发中,`java.util`包几乎无处不在,它包含了处理日期时间、...
在 Java 中,BitSet 的实现位于 java.util 包中。BitSet 的底层实现是使用 long 数组作为内部存储结构的,所以 BitSet 的大小为 long 类型大小(64 位)的整数倍。它有两个构造函数:BitSet() 和 BitSet(int nbits)...
bitSet.set(bitSet.size() - 448 + i, ((lengthInBits >> i) & 1) == 1); } // 将BitSet转换回字节数组 ByteBuffer buffer = ByteBuffer.allocate((bitSet.size() + 7) / 8); buffer.put(bitSet.toByteArray...
JavaUtil包是Java类库中的一个非常重要的组成部分,它提供了许多实用的方法和数据结构。 ##### java.util包基本层次结构 java.util包包含了许多重要的类和接口,如BitSet、Calendar、Date、Dictionary、...
为了保证生成的随机数不重复,我们可以使用`java.util.HashSet`或`java.util.TreeSet`。这两个集合不允许存储重复元素,因此当我们尝试添加一个已经存在的元素时,它会被自动忽略。 4. **填充集合**: 我们可以先...
JAVA提供了`java.util.BitSet`和`java.nio.charset.CharsetEncoder`类来处理这些操作。 3. **短信协议支持**:SMS平台需要支持SMPP(Short Message Peer-to-Peer)协议,这是短信服务提供商与短信网关之间通信的...
15. **位向量(Bitset)**:`java.util.BitSet`类提供了位操作,用于高效地处理大量的布尔值,节省内存空间。 掌握这些Java数据结构和它们的实现,不仅能够编写更高效的代码,还能帮助你理解和解决复杂的编程问题。...