MENU

EnumSet

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

枚举大量用于条件判断,如果要判断对象同时满足多个条件,或者满足其中之一,可将多个枚举实例存入 Set,使用集合操作 containscontainsAll 完成判断,我们希望这些操作都能以少于 O(n) 的时间完成。Java 中的 EnumSet 是一个使用 位数组 辅助实现的专门操作枚举类型元素的高性能集合。它是一个抽象类,有两个实现类,分别为 RegularEnumSetJumboEnumSet。前者用来处理常量数小于等于 64 的枚举,后者处理超过 64 个常量的情况。我们着重分析两个实现类的 add, remove, containscontainsAll 方法,观察位数组如何使枚举集合变得高效。

下面是 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。常量的 ordinalelements 位一一对应,并且就是 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.length63 后右移 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] 相当于 RegularEnumSetelements 变量。那关键就在于 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。这里需要遍历数组,数组的每个元素采取 RegularEnumSetelements 变量相同的判断逻辑,所以时间复杂度是数组大小。例如,如果有 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 大佬群

返回文章列表 文章二维码
本页链接的二维码
打赏二维码