Jdk1.6 Collections Framework源码解析(11)-EnumSet

Jdk1.6 Collections Framework源码解析(11)-EnumSet

作者：大飞

 

功能简介：

• EnumSet是一种针对Enum类型提供的特殊的Set，每个EnumSet只能基于一个Enum类型来建立。
• EnumSet内部采用位域的方式建立(相当于bit数组)，所以操作起来非常高效(几乎所有的基本操作都能在常数时间内完成)，包括retainAll和retainAll这种批量操作也一样。
• EnumSet的迭代器中元素顺序按照Enum的自然序(即定义顺序)排列；迭代器是弱一致的，不会抛出ConcurrentModificationException。
• EnumSet的元素不允许为null；EnumSet非线程安全。

 

源码分析：

• 先看下EnumSet内部结构：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
    implements Cloneable, java.io.Serializable
{
    /**
     * The class of all the elements of this set.
     */
    final Class<E> elementType;
    /**
     * All of the values comprising T.  (Cached for performance.)
     */
    final Enum[] universe;
    EnumSet(Class<E>elementType, Enum[] universe) {
        this.elementType = elementType;
        this.universe    = universe;
    }

       EnumSet支持克隆和序列化。内部会保存具体的枚举类型和还有具体枚举值的数组(作为缓存用？为毛？)。

 

       同时会发现，EnumSet的构造方法只是包内可见，外部没法直接构造。实际用起来也是通过of、allOf这样的方法来构造EnumSet实例的。下面先看一个比较重要的方法-noneOf： 

    public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
        Enum[] universe = getUniverse(elementType);
        if (universe == null)
            throw new ClassCastException(elementType + " not an enum");
        if (universe.length <= 64)
            return new RegularEnumSet<E>(elementType, universe);
        else
            return new JumboEnumSet<E>(elementType, universe);
    }
    private static <E extends Enum<E>> E[] getUniverse(Class<E> elementType) {
        return SharedSecrets.getJavaLangAccess()
					.getEnumConstantsShared(elementType);
    }

       通过代码可见，noneOf内部首先通过一个getUniverse方法来获取具体枚举值的数组，然后再根据数组的长度来决定构造RegularEnumSet还是JumboEnumSet。

       这里就会有2个疑问：

       1.getUniverse怎么实现的？

       2. RegularEnumSet和JumboEnumSet这两个子类，构造谁是通过universe长度来决定，小于等64构造RegularEnumSet，否则构造JumboEnumSet。结合前面介绍的EnumSet内部使用位域结构，猜测RegularEnumSet内部使用一个long域来保存内部状态，那么JumboEnumSet就是long数组喽，猜的对不对呢？

 

• 带着上面的2个疑问，我们来进行关键源码的分析：

       先来解答第一个问题，接着上面getUniverse中的实现，我们先看下SharedSecrets的源码(可通过openjdk查看)： 

public class SharedSecrets {
    
    ...
    public static void setJavaLangAccess(JavaLangAccess jla) {
        javaLangAccess = jla;
    }
    public static JavaLangAccess getJavaLangAccess() {
        return javaLangAccess;
    }

       可见SharedSecrets中的javaLangAccess是某个时机设置进来的。

       原来在JVM初始化过程中会有初始化系统类的过程，这个过程的详细代码可参见hotspot/src/share/vm/runtime/thread.cpp中的call_initializeSystemClass方法，代码就不贴了。这个方法其实是调用了System类的initializeSystemClass方法： 

    /**
     * Initialize the system class.  Called after thread initialization.
     */
    private static void initializeSystemClass() {
	    
        ...
        // Workaround until DownloadManager initialization is revisited.
        // Make JavaLangAccess available early enough for internal
        // Shutdown hooks to be registered
        setJavaLangAccess();
        ...

    }

 

       再看下这个setJavaLangAccess方法：

    private static void setJavaLangAccess() {
        // Allow privileged classes outside of java.lang
        sun.misc.SharedSecrets.setJavaLangAccess(new sun.misc.JavaLangAccess(){
            public sun.reflect.ConstantPool getConstantPool(Class klass) {
                return klass.getConstantPool();
            }
            public void setAnnotationType(Class klass, AnnotationType type) {
                klass.setAnnotationType(type);
            }
            public AnnotationType getAnnotationType(Class klass) {
                return klass.getAnnotationType();
            }
            public <E extends Enum<E>>
		    E[] getEnumConstantsShared(Class<E> klass) {
                return klass.getEnumConstantsShared();
            }
            public void blockedOn(Thread t, Interruptible b) {
                t.blockedOn(b);
            }
            public void registerShutdownHook(int slot, Runnable r) {
                Shutdown.add(slot, r);
            }
            public int getStackTraceDepth(Throwable t) {
                return t.getStackTraceDepth();
            }
            public StackTraceElement getStackTraceElement(Throwable t, int i) {
                return t.getStackTraceElement(i);
            }
        });
    }

 

       可见，其中的实现是直接调用了传入Class的getEnumConstantsShared方法，继续看： 

    T[] getEnumConstantsShared() {
	    if (enumConstants == null) {
	        if (!isEnum()) return null;
	        try {
		        final Method values = getMethod("values");
                java.security.AccessController.doPrivileged
                    (new java.security.PrivilegedAction() {
                            public Object run() {
                                values.setAccessible(true);
                                return null;
                            }
                        });
		        enumConstants = (T[])values.invoke(null);
	        }
	        // These can happen when users concoct enum-like classes
	        // that don't comply with the enum spec.
	        catch (InvocationTargetException ex) { return null; }
	        catch (NoSuchMethodException ex) { return null; }
	        catch (IllegalAccessException ex) { return null; }
	    }
	    return enumConstants;
    }

       原来是调用了给定枚举中的静态方法values，来获取枚举中所有枚举值组成的一个数组。

       到这里可能又会产生疑问，我们平时写枚举很简单，哪会写什么values方法，values方法哪来的？

       好吧，我们来写一个简单的枚举：

public enum Laugh {
	HAHA,
	HEHE,
	HEIHEI
	
}

 

       然后用javap分析下这个class(javap -p -c 目标class路径)：

public final class com.brokendreams.Laugh extends java.lang.Enum<com.brokendreams.Laugh> {
  public static final com.brokendreams.Laugh HAHA;
  public static final com.brokendreams.Laugh HEHE;
  public static final com.brokendreams.Laugh HEIHEI;
  private static final com.brokendreams.Laugh[] ENUM$VALUES;
  static {};
    Code:
       0: new           #1                  // class com/brokendreams/Laugh
       3: dup
       4: ldc           #14                 // String HAHA
       6: iconst_0
       7: invokespecial #15                 // Method "<init>":(Ljava/lang/String;I)V
      10: putstatic     #19                 // Field HAHA:Lcom/brokendreams/Laugh;
      13: new           #1                  // class com/brokendreams/Laugh
      16: dup
      17: ldc           #21                 // String HEHE
      19: iconst_1
      20: invokespecial #15                 // Method "<init>":(Ljava/lang/String;I)V
      23: putstatic     #22                 // Field HEHE:Lcom/brokendreams/Laugh;
      26: new           #1                  // class com/brokendreams/Laugh
      29: dup
      30: ldc           #24                 // String HEIHEI
      32: iconst_2
      33: invokespecial #15                 // Method "<init>":(Ljava/lang/String;I)V
      36: putstatic     #25                 // Field HEIHEI:Lcom/brokendreams/Laugh;
      39: iconst_3
      40: anewarray     #1                  // class com/brokendreams/Laugh
      43: dup
      44: iconst_0
      45: getstatic     #19                 // Field HAHA:Lcom/brokendreams/Laugh;
      48: aastore
      49: dup
      50: iconst_1
      51: getstatic     #22                 // Field HEHE:Lcom/brokendreams/Laugh;
      54: aastore
      55: dup
      56: iconst_2
      57: getstatic     #25                 // Field HEIHEI:Lcom/brokendreams/Laugh;
      60: aastore
      61: putstatic     #27                 // Field ENUM$VALUES:[Lcom/brokendreams/Laugh;
      64: return
  private com.brokendreams.Laugh(java.lang.String, int);
    Code:
       0: aload_0
       1: aload_1
       2: iload_2
       3: invokespecial #31                 // Method java/lang/Enum."<init>":(Ljava/lang/String;I)V
       6: return
  public static com.brokendreams.Laugh[] values();
    Code:
       0: getstatic     #27                 // Field ENUM$VALUES:[Lcom/brokendreams/Laugh;
       3: dup
       4: astore_0
       5: iconst_0
       6: aload_0
       7: arraylength
       8: dup
       9: istore_1
      10: anewarray     #1                  // class com/brokendreams/Laugh
      13: dup
      14: astore_2
      15: iconst_0
      16: iload_1
      17: invokestatic  #35                 // Method java/lang/System.arraycopy:(Ljava/lang/Object;ILjava/lang/Object;II)V
      20: aload_2
      21: areturn
  public static com.brokendreams.Laugh valueOf(java.lang.String);
    Code:
       0: ldc           #1                  // class com/brokendreams/Laugh
       2: aload_0
       3: invokestatic  #43                 // Method java/lang/Enum.valueOf:(Ljava/lang/Class;Ljava/lang/String;)Ljava/lang/Enum;
       6: checkcast     #1                  // class com/brokendreams/Laugh
       9: areturn
}

       这货就是我们刚才写的很简单的枚举Laugh，我们会发现：

       1. Laugh编译后其实还是一个class，并且继承了Enum类；Laugh里面的枚举值也变成了Laugh中的常量，并且在静态块儿中赋值；

       2.Laugh中还多出来一个ENUM$VALUES常量，是一个枚举数组，在静态块儿中会将所有的枚举实例放到这个常量里面；Laugh中多出了一些方法，包括上面让我们产生疑惑的values方法，values方法内部将ENUM$VALUES拷贝了一份，返回了拷贝出来的枚举数组。

       好吧，原来是编译器做了手脚，这样就可以解答前面的第一个关于关于getUniverse方法的疑问了。而且也可以理解为什么EnumSet中的universe做缓存用了吧。

 

       再来看第二个问题，在noneOf方法中，如果枚举数组的长度小于等于64，那么会构造一个RegularEnumSet实例。

       首先看下RegularEnumSet：

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;
    RegularEnumSet(Class<E>elementType, Enum[] universe) {
        super(elementType, universe);
    }

       看来和我们猜的一样，里面就是用一个long作为bit数组来表示集合内部数据的。

       下面利用我们上面定义的枚举，写个例子：

	public static void main(String[] args) {
		try {
			EnumSet<Laugh> laughs = EnumSet.noneOf(Laugh.class);
			/*
			 *  0...0     0    0    0    0    0    0    0    0
			 *   56个                                  
			 */
			Field elementsField = laughs.getClass().getDeclaredField("elements");
			elementsField.setAccessible(true);
			laughs.add(Laugh.HEHE);
			/*
			 *  0...0     0    0    0    0    0    0    1    0
			 *   56个                                  HEHE
			 */
			long elements = elementsField.getLong(laughs);
			System.out.println(Long.toBinaryString(elements));
			laughs.add(Laugh.HAHA);
			/*
			 *  0...0     0    0    0    0    0    0    1    1
			 *   56个                                  HEHE HAHA
			 */
			elements = elementsField.getLong(laughs);
			System.out.println(Long.toBinaryString(elements));
			laughs.add(Laugh.HEIHEI);
			/*
			 *  0...0     0    0    0    0    0    1    1    1
			 *   56个                           HEIHEI HEHE HAHA
			 */
			elements = elementsField.getLong(laughs);
			System.out.println(Long.toBinaryString(elements));
		} catch (Exception e) {
			e.printStackTrace();
		} 
	}

     

       输出如下：

10
11
111

       也就是说，内部的elements中，从右往左，第一个bit表示有没有HAHA，第二个bit表示有没有HEHE...以此类推。

       顺便看下add方法的实现：

    public boolean add(E e) {
        typeCheck(e);
        long oldElements = elements;
        elements |= (1L << ((Enum)e).ordinal());
        return elements != oldElements;
    }

       实现很简单，先看看e是不是给定的Enum类型，然后找到e对应的那个bit位置，将其置为1，最后比较操作前后的elements来判断是否插入成功(如果e已经存在，就相当于插入失败)。

       注意这里运算是通过enum中的ordinal来移位的，ordinal从0开始，详细过程可以从前面反编译的Laugh静态块儿中看下。

 

       再看一个EnumSet的方法-allOf的实现：

    public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) {
        EnumSet<E> result = noneOf(elementType);
        result.addAll();
        return result;
    }

       首先调用了noneOf，得到一个空的EnumSet集合，然后调用addAll方法添加所有元素，看看RegularEnumSet中addAll的实现细节：

    void addAll() {
        if (universe.length != 0)
            elements = -1L >>> -universe.length;
    }

       可知-1的位模式就是64个1，然后逻辑右移-3，相当于逻辑右移61，所以结果就是7，也就是二进制的111。

       其他的方法就不看了，都是一些位操作。

 

       再看下JumboEnumSet： 

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];
    }

       没错！我们又猜对了~  内部是一个long数组来保存元素。

       注意：这里为了提高性能，加了一个size域来保存元素个数；看到构造方法里面有个逻辑右移6位的运算，想一下，现在是long数组，也就是每64个元素用一个long，那么在确定数组长度的时候需要用元素个数除64吧，就相当于是逻辑右移6位，但是直接除64还不对，比如现在有129个元素，除以64等于2，但实际应该使用3个long来保存，所以要补63，来算出正确的数组长度。其他操作中还有很多>>>6的操作，注意一下。

 

       剩下的代码不看了，都是位操作，就不在这里啰嗦了，EnumSet的源码解析就到这里！有不对的地方请指正！