EnumMap / EnumSet / 位向量源码

概述

EnumMap 和 EnumSet 是专为枚举类型设计的高性能集合实现。它们利用了枚举常量的 ordinal() 方法，通过数组或位向量直接索引，在时间和空间上都具有极大的优势。

EnumMap 内部使用两个等长数组（keyUniverse + vals），枚举常量的 ordinal() 直接作为数组下标，实现 O(1) 的读写。EnumSet 使用位向量（RegularEnumSet 用 long，JumboEnumSet 用 long[]）表示枚举常量的存在状态。

BitSet 是通用的位向量实现，支持任意大小的位操作。

本文基于 OpenJDK 21 源码，从 EnumMap 的数组实现开始，逐层深入到 EnumSet 的位向量优化和 BitSet 的位操作实现。

本文基于 OpenJDK 21 源码分析。

---

核心源码解析

① EnumMap 的内部数组

public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
    implements java.io.Serializable, Cloneable {

    private final Class<K> keyType;
    private transient K[] keyUniverse;   // 所有枚举常量
    private transient Object[] vals;      // 值数组（索引对应 keyUniverse）
    private transient int size = 0;

    private static final Object NULL = new Object() { // null 值占位
        public int hashCode() { return 0; }
    };
}

• keyUniverse：固定大小的数组，包含该枚举类型的所有常量
• vals：与 keyUniverse 等长的值数组，null 表示该键没有映射
• NULL 对象：用于区分真正的 null 值和空槽位

② EnumMap.put() 的常数时间

public V put(K key, V value) {
    typeCheck(key);
    int index = key.ordinal();
    Object oldValue = vals[index];
    vals[index] = maskNull(value);
    if (oldValue == null)
        size++;
    return unmaskNull(oldValue);
}

private Object maskNull(V value) {
    return (value == null) ? NULL : value;
}

@SuppressWarnings("unchecked")
private V unmaskNull(Object value) {
    return (V)(value == NULL ? null : value);
}

• typeCheck()：确保键属于正确的枚举类型
• key.ordinal()：直接作为数组下标
• O(1) 复杂度，没有哈希计算和碰撞处理

EnumMap.get(K)：

public V get(Object key) {
    return (isValidKey(key) ?
            unmaskNull(vals[((Enum<?>)key).ordinal()]) : null);
}

③ EnumMap 的 keyUniverse 初始化

public EnumMap(Class<K> keyType) {
    this.keyType = keyType;
    keyUniverse = getKeyUniverse(keyType);
    vals = new Object[keyUniverse.length];
}

private static <K extends Enum<K>> K[] getKeyUniverse(Class<K> keyType) {
    return keyType.getEnumConstants(); // 反射获取所有枚举常量
}

• keyUniverse 在构造时确定，长度固定
• keyType.getEnumConstants() 最终调用 Class.enumConstants（内部缓存）
• 此缓存也是 TROOP 的 enumConstantDirectory 的基础

④ EnumSet.noneOf(Class) 选择 RegularEnumSet / JumboEnumSet

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[] 位向量
}

RegularEnumSet：

class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {
    private long elements = 0L; // 64 位的位向量
    // ...
}

JumboEnumSet：

class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
    private long[] elements;    // long[] 位向量
    private int size = 0;

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

• universe.length <= 64 → RegularEnumSet，单个 long 位向量
• universe.length > 64 → JumboEnumSet，long[] 位向量，每个 long 存 64 位

⑤ RegularEnumSet.add(E) 的位操作

public boolean add(E e) {
    typeCheck(e);
    long oldElements = elements;
    elements |= (1L << e.ordinal()); // 设置对应位为 1
    return elements != oldElements;
}

• 1L << e.ordinal()：将 1 左移到枚举常量对应的位位置
• elements |= ...：置 1
• O(1) 操作

addAll(Collection)：

public boolean addAll(EnumSet<E> c) {
    if (c instanceof RegularEnumSet) {
        long oldElements = elements;
        elements |= ((RegularEnumSet<E>)c).elements;
        return elements != oldElements;
    }
    return super.addAll(c);
}

• 同类型直接位或操作，批量化极快

⑥ RegularEnumSet.remove(Object) 的位清除

public boolean remove(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;
    long oldElements = elements;
    elements &= ~(1L << ((Enum<?>)e).ordinal()); // 清除对应位
    return elements != oldElements;
}

• ~(1L << ordinal)：生成掩码，将目标位改为 0，其他位为 1
• elements &= mask：清除该位

⑦ EnumSet.range(E, E) 的范围位

public static <E extends Enum<E>> EnumSet<E> range(E from, E to) {
    if (from.compareTo(to) > 0)
        throw new IllegalArgumentException(from + " > " + to);
    EnumSet<E> result = noneOf(from.getDeclaringClass());
    result.addRange(from.ordinal(), to.ordinal()); // 不同子类的实现不同
    return result;
}

RegularEnumSet 的实现：

void addRange(int from, int to) {
    elements = (-1L >>> (from - to - 1)) << from;
    // 假设 from=2, to=5:
    // from - to - 1 = -4
    // -1L >>> -4 = -1L >>> (64-4) = ...00001111
    // << 2 = ...00111100 (位 2-5 被设置)
}

JumboEnumSet 的实现：

void addRange(int from, int to) {
    int fromWord = from >>> 6;
    int toWord = to >>> 6;
    // 首尾 word 特殊处理，中间 word 全部置 -1L
    for (int i = fromWord; i <= toWord; i++) {
        elements[i] = -1L;
    }
    elements[fromWord] &= (-1L << from);
    elements[toWord] &= (-1L >>> -(to + 1));
}

⑧ BitSet 的位向量

BitSet 是通用的动态位向量实现：

public class BitSet implements Cloneable, java.io.Serializable {
    private long[] words;
    private transient int wordsInUse = 0;

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

get(int)：

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

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

set(int)：

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
}

clear(int)：

public void clear(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    int wordIndex = wordIndex(bitIndex);
    if (wordIndex < wordsInUse)
        words[wordIndex] &= ~(1L << bitIndex); // 清 0
    recalculateWordsInUse();
}

andNot / or / xor / and 操作：

public void andNot(BitSet set) {
    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
    for (int i = 0; i < wordsInCommon; i++)
        words[i] &= ~set.words[i]; // 按字运算
    recalculateWordsInUse();
}

---

总结

EnumMap 和 EnumSet 通过利用枚举常量的 ordinal() 特性，实现了极致的性能：

特性	EnumMap	EnumSet
底层存储	两个等长数组（keyUniverse + vals）	long 或 long[] 位向量
查找/插入	O(1)	O(1)
空间效率	固定大小（枚举常量数）	极高（位压缩）
适用场景	枚举→值的映射	枚举集合操作

BitSet 则提供了通用的可变长度位向量，适用于位图索引、海量数据去重等场景。