EnumSet
枚举大量用于条件判断，如果要判断对象同时满足多个条件，或者满足其中之一，可将多个枚举实例存入 Set，使用集合操作 contains 或 containsAll 完成判断，我们希望这些操作都能以少于 O(n) 的时间完成。Java 中的 EnumSet 是一个使用 位数组 辅助实现的专门操作枚举类型元素的高性能集合。它是一个抽象类，有两个实现类，分别为 RegularEnumSet 和 JumboEnumSet。前者用来处理常量数小于等于 64 的枚举，后者处理超过 64 个常量的情况。我们着重分析两个实现类的 add, remove, contains 和 containsAll 方法，观察位数组如何使枚举集合变得高效。
下面是 EnumSet 的部分签名，它使用 Enum<?>[] universe 缓存枚举类型 E 的所有成员实例。需要说明的是，Java 内置的两个 EnumSet 实现类都只能在 java.util 包下访问，这意味着通常不需要你手动创建子类对象，而是调用抽象类的静态工厂方法。这能确保 Java 使用适当子类，并正确初始化 universe 数组。
public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
implements Cloneable, java.io.Serializable {
// All of the values comprising E. (Cached for performance.)
final transient Enum<?>[] universe;
public boolean add(E e);
public boolean remove(Object e);
public boolean contains(Object e);
public boolean containsAll(Collection<?> c);
}每个枚举实例都有一个唯一的整型 ordinal 属性，代表实例的声明位置，从 0 开始依次增加，只要将它映射到位数组，即代表实例被集合保存。
public abstract class Enum<E extends Enum<E>>
implements Constable, Comparable<E>, Serializable {
/**
* The ordinal of this enumeration constant (its position
* in the enum declaration, where the initial constant is assigned
* an ordinal of zero).
*
* Most programmers will have no use for this field. It is designed
* for use by sophisticated enum-based data structures, such as
* {@link java.util.EnumSet} and {@link java.util.EnumMap}.
*/
private final int ordinal;
public final int ordinal() {
return ordinal;
}RegularEnumSet
EnumSet 的第一个实现类是 RegularEnumSet，它的最大容量为 64，使用一个 long 变量映射所有枚举元素，每一位代表一个枚举元素在 universe 数组中的下标，下面是类的部分签名。
class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {
// Bit vector representation of this set. The 2^k bit indicates the presence of universe[k] in this set.
private long elements = 0L;
}接着看它如何添加元素。
/**
* Adds the specified element to this set if it is not already present.
*
* @param e element to be added to this set
* @return {@code true} if the set changed as a result of the call
*
* @throws NullPointerException if {@code e} is null
*/
public boolean add(E e) {
typeCheck(e);
long oldElements = elements;
elements |= (1L << ((Enum<?>)e).ordinal());
return elements != oldElements;
}add 方法首先检测元素类型，如果与泛型类型不一致则抛出 ClassCastException。接着复制一份位映射变量到 oldElements，再修改原始 elements，如果修改前后位映射发生了改变则添加成功返回 true，否则表明元素已存在返回 false。该函数的时空复杂度都是 O(1)。
最关键的是修改 elements 的语句，它先获得枚举实例的 ordinal，这是一个 int 型变量，上文提到它是枚举实例的唯一标识。接着将 1L 循环左移 ordinal 位，再与 elements 按位或，最后将结果赋值给 elements。不妨看一个例子：
elements=0L, ordinal=63
1<<63 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000
e | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
---------------------------------------------------------------------------------------
e 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000假如 elements 现在没有元素，值为 0，要添加一个 ordinal==63 的元素。先将 1 循环左移 63 位，结果是第 64 位是 1，其它位都为 0。将它和 e=0L 按位或，那么 e 的第 64 位就会被置 1，其它位不受影响。这样就完成了元素的添加。
因为 RegularEnumSet 用于处理大多数常量数小于等于 64 的枚举类型，所以这里的 ordinal 范围为 0-63。常量的 ordinal 与 elements 位一一对应，并且就是 universe 数组的下标。
再看 remove 方法。
/**
* Removes the specified element from this set if it is present.
*
* @param e element to be removed from this set, if present
* @return {@code true} if the set contained the specified element
*/
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;
}可以看到，除了移位那行都和 add 方法类似（这行其实也相似），我们着重分析它。它与 add 方法的不同在于，1 被移位后又按位取反，也就是索引位 置 0，其它位 置 1。这样，再将结果与 elements 按位与，就会将 elements 上的索引位 置 0，其它位不变。这就完成了删除操作，时空复杂度均为 O(1)。
接着看 contains 方法。
/**
* Returns {@code true} if this set contains the specified element.
*
* @param e element to be checked for containment in this collection
* @return {@code true} if this set contains the specified element
*/
public boolean contains(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
return (elements & (1L << ((Enum<?>)e).ordinal())) != 0;
}这个函数也很好理解，关键是最后一句声明。1 左移对应索引位 置 1，其它位是 0。接着和 elements 按位与，如果 elements 上的索引位是 0，则最终结果必然是 0，表明元素不存在。
最后看 containsAll 方法。
/**
* Returns {@code true} if this set contains all of the elements
* in the specified collection.
*
* @param c collection to be checked for containment in this set
* @return {@code true} if this set contains all of the elements
* in the specified collection
* @throws NullPointerException if the specified collection is null
*/
public boolean containsAll(Collection<?> c) {
if (!(c instanceof RegularEnumSet))
return super.containsAll(c);
RegularEnumSet<?> es = (RegularEnumSet<?>)c;
if (es.elementType != elementType)
return es.isEmpty();
return (es.elements & ~elements) == 0;
}最后一行把自身的 elements 按位取反，包含元素的索引位被置 0，其它位被置 1。再将它与另一容器的 elements 按位与，要求结果为 0。换句话说，对于 this 容器不包含的那些索引位，要求被测容器 c 的对应位也是 0。即 c 不包含 this 元素之外的其它元素。也就是 this contains all elems of c。所以即使是 containsAll 操作，借助位映射也能在 O(1) 时间完成。
JumboEnumSet
上面的情况比较简单，再看大型枚举集合 JumboEnumSet，它使用 long elements[] 保存位映射，并增加了一个 size 变量记录集合大小。这样做的原因是，它要保存超过 64 个枚举常量，所以用数组；其次，如果不维护 size 变量，则要遍历 elements 才能获得元素个数，时间复杂度有所增加。下面是类的部分签名。
class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
/**
* Bit vector representation of this set. The ith bit of the jth
* element of this array represents the presence of universe[64*j +i]
* in this set.
*/
private long elements[];
// Redundant - maintained for performance
private int size = 0;
JumboEnumSet(Class<E>elementType, Enum<?>[] universe) {
super(elementType, universe);
elements = new long[(universe.length + 63) >>> 6];
}
}我们看到，它在构造函数中将 universe.length 加 63 后右移 6 位，即除以 64，作为数组长度。这是因为一个 long 变量可以映射 64 个常量，那么把总常量数除以 64 代表需要几个变量，也就是几个数组元素。加上 63 确保即使多出 1 个常量也再分配一个数组空间。
下面看 add() 方法。
/**
* Adds the specified element to this set if it is not already present.
*
* @param e element to be added to this set
* @return {@code true} if the set changed as a result of the call
*
* @throws NullPointerException if {@code e} is null
*/
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[eWordNum] 相当于 RegularEnumSet 的 elements 变量。那关键就在于 eWordNum 如何获得，可以看到它是枚举元素的 ordinal 右移 6 位，即除以 64。换句话说，就是把常量先映射到一个数组元素，再进一步把它映射到元素的一个比特位。为什么除以 64，因为一个数组元素可以映射 64 个常量。除以 64 确保，每 64 个元素就映射到不同的数组下标。例如，ordinal 在 [0, 63] 范围的常量映射到数组第 1 个元素，[64, 127] 映射到第 2 个，[64*i, 64*i + 63] 映射到第 i + 1 个。
映射到某个数组下标后，如何把 ordinal 映射到比特位呢？ 1L << ordinal 便是答案，对于 [0-63] 范围的 ordinal，情况同 RegularEnumSet。对于 [64-∞] 的 ordinal，循环左移相当于左移 ordinal % 64 位，仍然落在 [0-63] 之间。
接着看 remove 方法。有了上面的分析，结合 RegularEnumSet 的删除方法，不难看出此处思路相同，不再解释。
/**
* Removes the specified element from this set if it is present.
*
* @param e element to be removed from this set, if present
* @return {@code true} if the set contained the specified element
*/
public boolean remove(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
int eOrdinal = ((Enum<?>)e).ordinal();
int eWordNum = eOrdinal >>> 6;
long oldElements = elements[eWordNum];
elements[eWordNum] &= ~(1L << eOrdinal);
boolean result = (elements[eWordNum] != oldElements);
if (result)
size--;
return result;
}接着看 contains 方法。同样结合 RegularEnumSet 的包含方法，很容易理解。
/**
* Returns {@code true} if this set contains the specified element.
*
* @param e element to be checked for containment in this collection
* @return {@code true} if this set contains the specified element
*/
public boolean contains(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
int eOrdinal = ((Enum<?>)e).ordinal();
return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
}最后是 containsAll。这里需要遍历数组，数组的每个元素采取 RegularEnumSet 的 elements 变量相同的判断逻辑，所以时间复杂度是数组大小。例如，如果有 6,400 个常量，则需 100 次计算，一次可判断 64 个。
/**
* Returns {@code true} if this set contains all of the elements
* in the specified collection.
*
* @param c collection to be checked for containment in this set
* @return {@code true} if this set contains all of the elements
* in the specified collection
* @throws NullPointerException if the specified collection is null
*/
public boolean containsAll(Collection<?> c) {
if (!(c instanceof JumboEnumSet))
return super.containsAll(c);
JumboEnumSet<?> es = (JumboEnumSet<?>)c;
if (es.elementType != elementType)
return es.isEmpty();
for (int i = 0; i < elements.length; i++)
if ((es.elements[i] & ~elements[i]) != 0)
return false;
return true;
}以上便完成了枚举集合的原理分析，相信你对位数组也有了直观认识。实际上位数组还有很多运用，如数据压缩，布隆过滤器等，更多细节见参考链接。