BitSet / EnumSet / 位操作集合源码

概述

BitSet 和 EnumSet 是 Java 中以**位向量（bit vector）**为底层存储的两类集合：用一个比特位表示"某个元素是否存在"，从而把内存占用压缩到极致，并把集合运算（并、交、差）降级为一次位运算。

BitSet 是通用的动态位向量，内部用 long[] 存储任意数量的位。EnumSet 是专为枚举设计的 Set 实现，用枚举常量的 ordinal() 直接作为位下标：枚举数量不超过 64 时用单个 long（RegularEnumSet），超过 64 时退化为 long[]（JumboEnumSet）。

本文基于 OpenJDK 21 源码，从 BitSet 的 words 数组开始，逐步拆解位读取、位设置、位集合运算与位计数，再深入到 EnumSet 两个子类的位掩码实现。

---

核心源码解析

① BitSet 的内部存储：long[] words

public class BitSet implements Cloneable, java.io.Serializable {
    private long[] words;              // 位存储：每个 long 承载 64 位
    private transient int wordsInUse;  // 实际使用的 word 数量（逻辑大小）
    private boolean sizeIsSticky;      // 是否固定 size

    private final static int ADDRESS_BITS_PER_WORD = 6;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; // 64

    public BitSet() {
        initWords(BITS_PER_WORD);      // 默认分配 1 个 long（64 位）
        sizeIsSticky = false;
    }

    private void initWords(int nbits) {
        words = new long[wordIndex(nbits - 1) + 1];
    }

    private static int wordIndex(int bitIndex) {
        return bitIndex >> 6;          // 等价于 bitIndex / 64
    }
}

核心要点：

• words 数组：每个 long 保存 64 个连续比特位，下标 i 对应 bits[64i, 64i+63]。
• wordIndex(int)：bitIndex >> 6（除以 64 向下取整）定位目标位所在的 long 下标。
• wordsInUse：words 数组中最后一个非 0 元素的下标 + 1，表示"逻辑上用了多少位"。它严格小于等于 words.length，是绝大多数位操作（and、cardinality 等）的遍历上界，避免扫描未初始化的尾部。
• sizeIsSticky：区分 new BitSet()（默认 64 位，可随设置自动增长）与 new BitSet(nbits)（用户指定初始容量）。

BitSet 没有像 HashSet 那样的哈希与冲突，set / get / clear 全部是 O(1) 位运算，且天然有序——遍历位总是从小到大。

② BitSet.get(int bitIndex) 的位读取

public boolean get(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    checkInvariants();
    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
}

读取分两步：

1. wordIndex(bitIndex) 定位 long 下标，先校验 wordIndex < wordsInUse——超过逻辑大小直接返回 false，避免读到未使用的垃圾位。
2. words[wordIndex] & (1L << bitIndex) 提取目标位。注意这里 1L << bitIndex 的移位量在 Java 中只会取低 6 位，因此当 bitIndex >= 64 时，1L << bitIndex 自动等价于 1L << (bitIndex & 63)，恰好作用到该 long 内的对应位置，无需显式取余。

get(int, int) 范围版本 get(fromIndex, toIndex) 会先做参数校验，再定位首尾 word，逐 word 用掩码切出 [from, to) 区间并拷贝到新 BitSet。

③ BitSet.set(int bitIndex) 的位设置

public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);                          // 容量不足先扩容
    words[wordIndex] |= (1L << bitIndex);         // 置 1，保持其他位不变
    checkInvariants();
}

扩容与 wordsInUse 维护：

private void expandTo(int wordIndex) {
    int wordsRequired = wordIndex + 1;
    if (wordsInUse < wordsRequired) {
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;               // 逻辑大小同步推进
    }
}

private void ensureCapacity(int wordsRequired) {
    if (words.length < wordsRequired) {
        int request = Math.max(2 * words.length, wordsRequired);  // 至少翻倍
        words = Arrays.copyOf(words, request);    // 拷贝旧数据并扩容
    }
}

• set 把对应位置 1，set(bitIndex, false) 等价于 clear。
• 扩容翻倍：ensureCapacity 采用至少 2 倍策略摊还扩容成本，与 ArrayList 类似。
• wordsInUse 的两种维护路径：set / set(from, to) 这类"只会变多"的操作在 expandTo 中直接推进 wordsInUse；而 clear / and / or / xor / andNot 这类"可能变少"的操作，结束后调用 recalculateWordsInUse() 从尾向前扫描重算：

private void recalculateWordsInUse() {
    int i;
    for (i = wordsInUse - 1; i >= 0; i--)
        if (words[i] != 0) break;                 // 找最后一个非 0 word
    wordsInUse = i + 1;
}

set(from, to) 范围版本针对首尾 word 生成掩码（-1L << from 与 -1L >>> -to），中间整 word 直接写 -1L，同样是 O(1) 级别的批量置位。

④ BitSet.and(BitSet set) 的位与

public void and(BitSet set) {
    if (this == set) return;                      // 自交无操作
    while (wordsInUse > set.wordsInUse)
        words[--wordsInUse] = 0;                  // 超出的高位清零并收缩
    for (int i = 0; i < wordsInUse; i++)
        words[i] &= set.words[i];                 // 逐 word 按位与
    recalculateWordsInUse();                      // 重算逻辑大小
    checkInvariants();
}

• 先收缩再运算：and 的结果不可能超过较短一方，所以先把多出的尾部 word 清零（同时缩小 wordsInUse）。
• 逐 word 位与：核心循环 words[i] &= set.words[i] 一次处理 64 位，性能极佳。
• 结束时 recalculateWordsInUse() 消除高位可能残留的 0 字。

与 and 对称的集合运算：

方法	位运算	说明
and(BitSet)	words[i] &= set.words[i]	交集
or(BitSet)	`words[i]	= set.words[i]`
xor(BitSet)	words[i] ^= set.words[i]	对称差
andNot(BitSet)	words[i] &= ~set.words[i]	差集
intersects(BitSet)	(words[i] & set.words[i]) != 0	是否相交（只读，短路返回）

⑤ BitSet.cardinality() 的位计数

public int cardinality() {
    int sum = 0;
    for (int i = 0; i < wordsInUse; i++)
        sum += Long.bitCount(words[i]);           // 统计每个 long 中 1 的个数
    return sum;
}

• Long.bitCount 是 JVM 内置的 popcount 指令（x86 的 popcnt），HotSpot 会将其编译为单条硬件指令，逐个 64 位字统计 1 的个数，再累加得到集合大小——cardinality() 就是 EnumSet.size() 的实现基础。

其他与"大小"相关的查询：

• length()：最高置位位索引 + 1（wordsInUse == 0 时返回 0），计算依赖 Long.numberOfLeadingZeros(words[wordsInUse - 1])。
• size()：words.length * 64，即当前分配的存储容量（可能与 length() 不一致）。
• nextSetBit(int) / previousSetBit(int)：用 Long.numberOfTrailingZeros / Long.numberOfLeadingZeros 在单个 word 内快速跳到下一个置位，遍历位集合时避免逐位检查。

⑥ EnumSet.noneOf(Class) 的工厂方法

public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
    Enum<?>[] universe = getKeyUniverse(elementType);   // 反射拿到全部枚举常量
    if (universe == null)
        throw new ClassCastException(elementType + " not an enum");
    if (universe.length <= 64)
        return new RegularEnumSet<>(elementType, universe);  // 单 long 位向量
    else
        return new JumboEnumSet<>(elementType, universe);    // long[] 位向量
}

private static <E extends Enum<E>> E[] getKeyUniverse(Class<E> elementType) {
    return elementType.getEnumConstants();
}

• getEnumConstants()：Class 内部缓存枚举常量数组（enumConstantDirectory），EnumSet 在创建时一次性拿到所有常量，之后不再依赖反射。
• 按数量分流：枚举常量不超过 64 个时用 RegularEnumSet（单 long，64 位恰好容纳），超过 64 个时用 JumboEnumSet（long[] 分段存储）。这是 EnumSet 性能的关键分水岭。
• 工厂方法家族：of(...)（1~5 个参数的重载）、allOf(Class)、complementOf(EnumSet)、range(E, E)、copyOf(Collection) 都经由 noneOf 创建空集合，再填充位掩码。

⑦ RegularEnumSet 的内部存储

class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {
    private long elements = 0L;      // 单个 long：第 ordinal 位代表常量 ordinal 存在

    RegularEnumSet(Class<E> elementType, Enum<?>[] universe) {
        super(elementType, universe);
    }
}

• 整个集合的状态就是一个 long 的 64 位掩码：位 ordinal 为 1 表示"序号为 ordinal 的枚举常量在集合中"。
• size() 直接委托 Long.bitCount(elements)，isEmpty() 判断 elements == 0，contains(Object) 判断 (elements & (1L << ordinal)) != 0——全部是单条位运算，这是枚举集合能做到 O(1) 的根本原因。

批量构造方法也是纯位运算：

void addRange(int from, int to) {
    elements = (-1L >>> (from - to - 1)) << from;   // [from, to] 区间置 1
}

void addAll() {
    if (universe.length != 0)
        elements = -1L >>> -universe.length;        // 低 n 位全部置 1
}

void complement() {
    if (universe.length != 0)
        elements = ~elements;                        // 取反
}

⑧ RegularEnumSet.add(E) 的位操作

public boolean add(E e) {
    typeCheck(e);                                   // 校验枚举类型一致
    long oldElements = elements;
    elements |= (1L << ((Enum<?>) e).ordinal());    // 目标位置 1
    return elements != oldElements;                 // 集合是否发生变化
}

• typeCheck 会校验元素声明类型与 elementType 一致（含子类声明情况），非法元素抛 ClassCastException。
• 1L << e.ordinal() 把 1 左移到常量序号对应的位，|= 置 1 且不影响其他位。
• 返回 elements != oldElements 判断"本次是否真的新增"，符合 Set.add 的语义契约。
• remove 对称地使用 elements &= ~(1L << ordinal) 清位；addAll(EnumSet) 对同类集合直接 elements |= other.elements，一次位或完成合并。

迭代器：EnumSetIterator 用 unseen 记录未访问位的掩码，每次通过 Long.numberOfTrailingZeros(unseen) 找到下一个置位索引并返回对应常量，因此遍历顺序恒为枚举声明顺序（即 ordinal 升序）。

⑨ JumboEnumSet 的超 64 枚举存储

class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
    private long elements[];        // 分段位向量：每段 64 位
    private int size = 0;           // 显式维护元素个数

    JumboEnumSet(Class<E> elementType, Enum<?>[] universe) {
        super(elementType, universe);
        elements = new long[(universe.length + 63) >>> 6];  // 向上取整到 64 的倍数
    }

    public boolean add(E e) {
        typeCheck(e);
        int eOrdinal = e.ordinal();
        int eWordNum = eOrdinal >>> 6;                  // 定位所在分段
        long oldElements = elements[eWordNum];
        elements[eWordNum] |= (1L << eOrdinal);         // 段内置位
        boolean result = (elements[eWordNum] != oldElements);
        if (result)
            size++;
        return result;
    }
}

要点：

• 分段存储：elements[i] 承载常量序号 [64i, 64i+63]，e.ordinal() >>> 6（即 >> 6）得到段下标。
• 移位截断技巧：1L << eOrdinal 在 eOrdinal >= 64 时只保留低 6 位，自动落到段内正确位置，与 BitSet 中 1L << bitIndex 的原理相同，因此这里不需要 eOrdinal & 63。
• 由于段内只统计 64 位，JumboEnumSet 无法像 RegularEnumSet 那样用 Long.bitCount(elements) 直接得出 size，改为显式维护 size 计数器（add 成功加 1，remove 成功减 1）。
• addRange 对首尾段生成部分掩码、中间段整段置 -1L，addAll 逐段执行 |=，与 BitSet.set(from, to) 思路一致。

---

总结

位操作集合把"集合"抽象成"比特串"，用硬件位指令换性能：

维度	BitSet	EnumSet
底层存储	long[] words（动态扩容）	RegularEnumSet 单 long / JumboEnumSet long[]
位定位	bitIndex >> 6 找 word，1L << bitIndex 取位	e.ordinal() >> 6 找段，1L << e.ordinal() 取位
集合大小	cardinality() 累加 Long.bitCount	Long.bitCount(elements) 或显式 size 计数
核心运算	and / or / xor / andNot / intersects	add / remove / contains / addRange / complement
复杂度	O(wordsInUse)	O(1)
适用场景	通用位图、海量标记、布隆过滤	枚举常量集合、位标志组合

无论是 BitSet 的 words 数组还是 EnumSet 的位掩码，本质都是用位下标映射集合元素：set 置 1、get 读 1、and / or / xor 做集合运算、bitCount 数元素个数。理解这一层位运算，就理解了这两类集合的全部性能优势来源。