MENU

EnumSet

2021 年 07 月 08 日 • 阅读: 4164 • 算法

枚举大量用于条件判断，如果要判断对象同时满足多个条件，或者满足其中之一，可将多个枚举实例存入 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;
}

以上便完成了枚举集合的原理分析，相信你对位数组也有了直观认识。实际上位数组还有很多运用，如数据压缩，布隆过滤器等，更多细节见参考链接。

参考链接

如有问题请在下方留言，文章转载请注明出处，详细交流请加下方群组！请大佬不要屏蔽文中广告，因为它将帮我分担服务器开支，如果能帮忙点击我将万分感谢。

TG 大佬群 QQ 大佬群

Algorithm
返回文章列表 文章二维码
本页链接的二维码
打赏二维码
添加新评论

Loading captcha...