EnumMap.java

/*
 * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package java.util;

import java.io.Serializable;
import java.lang.reflect.Array;
import jdk.internal.misc.SharedSecrets;

/**
 * A specialized {@link Map} implementation for use with enum type keys.  All
 * of the keys in an enum map must come from a single enum type that is
 * specified, explicitly or implicitly, when the map is created.  Enum maps
 * are represented internally as arrays.  This representation is extremely
 * compact and efficient.
 *
 * <p>Enum maps are maintained in the <i>natural order</i> of their keys
 * (the order in which the enum constants are declared).  This is reflected
 * in the iterators returned by the collections views ({@link #keySet()},
 * {@link #entrySet()}, and {@link #values()}).
 *
 * <p>Iterators returned by the collection views are <i>weakly consistent</i>:
 * they will never throw {@link ConcurrentModificationException} and they may
 * or may not show the effects of any modifications to the map that occur while
 * the iteration is in progress.
 *
 * <p>Null keys are not permitted.  Attempts to insert a null key will
 * throw {@link NullPointerException}.  Attempts to test for the
 * presence of a null key or to remove one will, however, function properly.
 * Null values are permitted.
 *
 * <P>Like most collection implementations {@code EnumMap} is not
 * synchronized. If multiple threads access an enum map concurrently, and at
 * least one of the threads modifies the map, it should be synchronized
 * externally.  This is typically accomplished by synchronizing on some
 * object that naturally encapsulates the enum map.  If no such object exists,
 * the map should be "wrapped" using the {@link Collections#synchronizedMap}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access:
 *
 * <pre>
 *     Map&lt;EnumKey, V&gt; m
 *         = Collections.synchronizedMap(new EnumMap&lt;EnumKey, V&gt;(...));
 * </pre>
 *
 * <p>Implementation note: All basic operations execute in constant time.
 * They are likely (though not guaranteed) to be faster than their
 * {@link HashMap} counterparts.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @author Josh Bloch
 * @see EnumSet
 * @since 1.5
 */

/*
 * EnumMap结构：数组(不可扩容)。key不能为null，但value可以为null
 *
 * 注：key必须为Enum类型或其子类
 */
public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V> implements Serializable, Cloneable {
    
    /**
     * Distinguished non-null value for representing null values.
     */
    private static final Object NULL = new Object() {
        public int hashCode() {
            return 0;
        }
        
        public String toString() {
            return "java.util.EnumMap.NULL";
        }
    };  // 专用空值
    
    /**
     * The {@code Class} object for the enum type of all the keys of this map.
     *
     * @serial
     */
    private final Class<K> keyType;     // key的类型，必须是枚举类型。该类型(包含的枚举常量的数量)决定了哈希数组的容量
    
    /**
     * All of the values comprising K.  (Cached for performance.)
     */
    private transient K[] keyUniverse;  // key的集合
    
    /**
     * Array representation of this map.  The ith element is the value
     * to which universe[i] is currently mapped, or null if it isn't
     * mapped to anything, or NULL if it's mapped to null.
     */
    private transient Object[] vals;    // value的集合
    
    /**
     * This field is initialized to contain an instance of the entry set
     * view the first time this view is requested.  The view is stateless,
     * so there's no reason to create more than one.
     */
    private transient Set<Map.Entry<K, V>> entrySet;    // entry的集合
    
    /**
     * The number of mappings in this map.
     */
    private transient int size = 0;     // 当前Map中元素的数量
    
    
    
    /*▼ 构造器 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Creates an empty enum map with the specified key type.
     *
     * @param keyType the class object of the key type for this enum map
     *
     * @throws NullPointerException if {@code keyType} is null
     */
    public EnumMap(Class<K> keyType) {
        this.keyType = keyType;
        // 获取枚举类keyType中所有常量元素的集合（将作为EnumMap的key使用）
        keyUniverse = getKeyUniverse(keyType);
        vals = new Object[keyUniverse.length];
    }
    
    /**
     * Creates an enum map with the same key type as the specified enum
     * map, initially containing the same mappings (if any).
     *
     * @param m the enum map from which to initialize this enum map
     *
     * @throws NullPointerException if {@code m} is null
     */
    public EnumMap(EnumMap<K, ? extends V> m) {
        keyType = m.keyType;
        keyUniverse = m.keyUniverse;
        vals = m.vals.clone();
        size = m.size;
    }
    
    /**
     * Creates an enum map initialized from the specified map.  If the
     * specified map is an {@code EnumMap} instance, this constructor behaves
     * identically to {@link #EnumMap(EnumMap)}.  Otherwise, the specified map
     * must contain at least one mapping (in order to determine the new
     * enum map's key type).
     *
     * @param m the map from which to initialize this enum map
     *
     * @throws IllegalArgumentException if {@code m} is not an
     *                                  {@code EnumMap} instance and contains no mappings
     * @throws NullPointerException     if {@code m} is null
     */
    public EnumMap(Map<K, ? extends V> m) {
        if(m instanceof EnumMap) {
            EnumMap<K, ? extends V> em = (EnumMap<K, ? extends V>) m;
            keyType = em.keyType;
            keyUniverse = em.keyUniverse;
            vals = em.vals.clone();
            size = em.size;
        } else {
            if(m.isEmpty()) {
                throw new IllegalArgumentException("Specified map is empty");
            }
            
            keyType = m.keySet().iterator().next().getDeclaringClass();
            
            // 获取枚举类keyType中所有常量元素的集合（将作为EnumMap的key使用）
            keyUniverse = getKeyUniverse(keyType);
            
            vals = new Object[keyUniverse.length];
            
            putAll(m);
        }
    }
    
    /*▲ 构造器 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 存值 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for this key, the old
     * value is replaced.
     *
     * @param key   the key with which the specified value is to be associated
     * @param value the value to be associated with the specified key
     *
     * @return the previous value associated with specified key, or
     * {@code null} if there was no mapping for key.  (A {@code null}
     * return can also indicate that the map previously associated
     * {@code null} with the specified key.)
     *
     * @throws NullPointerException if the specified key is null
     */
    // 将指定的元素（key-value）存入EnumMap，并返回旧值，允许覆盖
    public V put(K key, V value) {
        typeCheck(key);
        
        // 获取枚举实例的值（索引）
        int index = key.ordinal();
        
        // 获取旧值
        Object oldValue = vals[index];
        
        // (包装空值)如果value是null，返回一个专用空值。否则，原样返回
        vals[index] = maskNull(value);
        
        // 如果此处没有元素，则计数增一(刚刚插入了新元素)
        if(oldValue == null) {
            size++;
        }
        
        // (解析空值)如果oldValue是一个专用空值，返回null。否则，原样返回
        return unmaskNull(oldValue);
    }
    
    /**
     * Copies all of the mappings from the specified map to this map.
     * These mappings will replace any mappings that this map had for
     * any of the keys currently in the specified map.
     *
     * @param m the mappings to be stored in this map
     *
     * @throws NullPointerException the specified map is null, or if
     *                              one or more keys in the specified map are null
     */
    // 将指定Map中的元素存入到当前Map（允许覆盖）
    public void putAll(Map<? extends K, ? extends V> m) {
        if(m instanceof EnumMap) {
            EnumMap<?, ?> em = (EnumMap<?, ?>) m;
            
            if(em.keyType != keyType) {
                // 虽然key的类型不一致，但给定的Map为空，所以直接返回
                if(em.isEmpty()) {
                    return;
                }
                
                // 类型不同，抛异常
                throw new ClassCastException(em.keyType + " != " + keyType);
            }
            
            // 将指定Map中的键值对复制到当前Map中
            for(int i = 0; i<keyUniverse.length; i++) {
                Object emValue = em.vals[i];
                if(emValue != null) {
                    if(vals[i] == null) {
                        size++;
                    }
                    
                    vals[i] = emValue;
                }
            }
        } else {
            // 对于普通的Map，需要使用普通的put方式
            super.putAll(m);
        }
    }
    
    /*▲ 存值 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 取值 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key == k)},
     * then this method returns {@code v}; otherwise it returns
     * {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     */
    // 根据指定的key获取对应的value，如果不存在，则返回null
    public V get(Object key) {
        // 如果key不合规，返回null
        if(!isValidKey(key)) {
            return null;
        }
        
        // 获取枚举实例的值（索引）
        int index = ((Enum<?>) key).ordinal();
        
        // 获取key对应的value
        Object value = vals[index];
        
        // (解析空值)如果value是一个专用空值，返回null。否则，原样返回
        return unmaskNull(value);
    }
    
    /*▲ 取值 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 移除 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Removes the mapping for this key from this map if present.
     *
     * @param key the key whose mapping is to be removed from the map
     *
     * @return the previous value associated with specified key, or
     * {@code null} if there was no entry for key.  (A {@code null}
     * return can also indicate that the map previously associated
     * {@code null} with the specified key.)
     */
    // 移除拥有指定key的元素，并返回刚刚移除的元素的值
    public V remove(Object key) {
        // 如果key不合规，返回null
        if(!isValidKey(key)) {
            return null;
        }
        
        // 获取枚举实例的值（索引）
        int index = ((Enum<?>) key).ordinal();
        
        // 获取key对应的value
        Object oldValue = vals[index];
        
        // 置空当前位置
        vals[index] = null;
        
        // 计数递减
        if(oldValue != null) {
            size--;
        }
        
        return unmaskNull(oldValue);
    }
    
    
    /**
     * Removes all mappings from this map.
     */
    // 清空EnumMap中所有元素
    public void clear() {
        Arrays.fill(vals, null);
        size = 0;
    }
    
    /*▲ 移除 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 替换 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /*▲ 替换 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 包含查询 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Returns {@code true} if this map contains a mapping for the specified
     * key.
     *
     * @param key the key whose presence in this map is to be tested
     *
     * @return {@code true} if this map contains a mapping for the specified
     * key
     */
    // 判断EnumMap中是否存在指定key的元素
    public boolean containsKey(Object key) {
        // 如果key不合规，返回false
        if(!isValidKey(key)) {
            return false;
        }
        
        // 获取枚举实例的值（索引）
        int index = ((Enum<?>) key).ordinal();
        
        return vals[index] != null;
    }
    
    /**
     * Returns {@code true} if this map maps one or more keys to the
     * specified value.
     *
     * @param value the value whose presence in this map is to be tested
     *
     * @return {@code true} if this map maps one or more keys to this value
     */
    // 判断EnumMap中是否存在指定value的元素
    public boolean containsValue(Object value) {
        // (包装空值)如果value是null，返回一个专用空值。否则，原样返回
        value = maskNull(value);
        
        // 遍历所有值
        for(Object val : vals) {
            if(value.equals(val)) {
                return true;
            }
        }
        
        return false;
    }
    
    /*▲ 包含查询 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 视图 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Returns a {@link Set} view of the keys contained in this map.
     * The returned set obeys the general contract outlined in
     * {@link Map#keySet()}.  The set's iterator will return the keys
     * in their natural order (the order in which the enum constants
     * are declared).
     *
     * @return a set view of the keys contained in this enum map
     */
    // 获取EnumMap中key的集合
    public Set<K> keySet() {
        Set<K> ks = keySet;
        return ks!=null ? ks : (keySet= new KeySet());
    }
    
    /**
     * Returns a {@link Collection} view of the values contained in this map.
     * The returned collection obeys the general contract outlined in
     * {@link Map#values()}.  The collection's iterator will return the
     * values in the order their corresponding keys appear in map,
     * which is their natural order (the order in which the enum constants
     * are declared).
     *
     * @return a collection view of the values contained in this map
     */
    // 获取EnumMap中value的集合
    public Collection<V> values() {
        Collection<V> vs = values;
        return vs!=null ? vs : (values= new Values());
    }
    
    /**
     * Returns a {@link Set} view of the mappings contained in this map.
     * The returned set obeys the general contract outlined in
     * {@link Map#keySet()}.  The set's iterator will return the
     * mappings in the order their keys appear in map, which is their
     * natural order (the order in which the enum constants are declared).
     *
     * @return a set view of the mappings contained in this enum map
     */
    // 获取EnumMap中key-value对的集合
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }
    
    /*▲ 视图 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 遍历 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /*▲ 遍历 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 重新映射 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /*▲ 重新映射 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 杂项 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    // 获取EnumMap中的元素数量
    public int size() {
        return size;
    }
    
    /*▲ 杂项 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /*▼ 序列化 ████████████████████████████████████████████████████████████████████████████████┓ */
    
    private static final long serialVersionUID = 458661240069192865L;
    
    /**
     * Save the state of the {@code EnumMap} instance to a stream (i.e.,
     * serialize it).
     *
     * @serialData The <i>size</i> of the enum map (the number of key-value
     * mappings) is emitted (int), followed by the key (Object)
     * and value (Object) for each key-value mapping represented
     * by the enum map.
     */
    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
        // Write out the key type and any hidden stuff
        s.defaultWriteObject();
        
        // Write out size (number of Mappings)
        s.writeInt(size);
        
        // Write out keys and values (alternating)
        int entriesToBeWritten = size;
        for(int i = 0; entriesToBeWritten>0; i++) {
            if(null != vals[i]) {
                s.writeObject(keyUniverse[i]);
                s.writeObject(unmaskNull(vals[i]));
                entriesToBeWritten--;
            }
        }
    }
    
    /**
     * Reconstitute the {@code EnumMap} instance from a stream (i.e.,
     * deserialize it).
     */
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        // Read in the key type and any hidden stuff
        s.defaultReadObject();
        
        keyUniverse = getKeyUniverse(keyType);
        vals = new Object[keyUniverse.length];
        
        // Read in size (number of Mappings)
        int size = s.readInt();
        
        // Read the keys and values, and put the mappings in the HashMap
        for(int i = 0; i<size; i++) {
            K key = (K) s.readObject();
            V value = (V) s.readObject();
            put(key, value);
        }
    }
    
    /*▲ 序列化 ████████████████████████████████████████████████████████████████████████████████┛ */
    
    
    
    /**
     * Compares the specified object with this map for equality.  Returns
     * {@code true} if the given object is also a map and the two maps
     * represent the same mappings, as specified in the {@link
     * Map#equals(Object)} contract.
     *
     * @param o the object to be compared for equality with this map
     *
     * @return {@code true} if the specified object is equal to this map
     */
    public boolean equals(Object o) {
        if(this == o) {
            return true;
        }
        
        if(o instanceof EnumMap) {
            return equals((EnumMap<?, ?>) o);
        }
        
        if(!(o instanceof Map)) {
            return false;
        }
        
        Map<?, ?> m = (Map<?, ?>) o;
        if(size != m.size()) {
            return false;
        }
        
        for(int i = 0; i<keyUniverse.length; i++) {
            if(null != vals[i]) {
                K key = keyUniverse[i];
                V value = unmaskNull(vals[i]);
                if(null == value) {
                    if(!((null == m.get(key)) && m.containsKey(key))) {
                        return false;
                    }
                } else {
                    if(!value.equals(m.get(key))) {
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
    
    /**
     * Returns the hash code value for this map.  The hash code of a map is
     * defined to be the sum of the hash codes of each entry in the map.
     */
    public int hashCode() {
        int h = 0;
        
        for(int i = 0; i<keyUniverse.length; i++) {
            if(null != vals[i]) {
                h += entryHashCode(i);
            }
        }
        
        return h;
    }
    
    /**
     * Returns a shallow copy of this enum map. The values themselves
     * are not cloned.
     *
     * @return a shallow copy of this enum map
     */
    @SuppressWarnings("unchecked")
    public EnumMap<K, V> clone() {
        EnumMap<K, V> result = null;
        try {
            result = (EnumMap<K, V>) super.clone();
        } catch(CloneNotSupportedException e) {
            throw new AssertionError();
        }
        result.vals = result.vals.clone();
        result.entrySet = null;
        return result;
    }
    
    
    
    /**
     * Returns all of the values comprising K.
     * The result is uncloned, cached, and shared by all callers.
     */
    // 获取枚举类keyType中所有常量元素的集合（将作为EnumMap的key使用）
    private static <K extends Enum<K>> K[] getKeyUniverse(Class<K> keyType) {
        return SharedSecrets.getJavaLangAccess().getEnumConstantsShared(keyType);
    }
    
    // (包装空值)如果value是null，返回一个专用空值。否则，原样返回
    private Object maskNull(Object value) {
        return (value == null ? NULL : value);
    }
    
    // (解析空值)如果value是一个专用空值，返回null。否则，原样返回
    @SuppressWarnings("unchecked")
    private V unmaskNull(Object value) {
        return (V) (value == NULL ? null : value);
    }
    
    // 判断当前Map中是否包含指定的键值对
    private boolean containsMapping(Object key, Object value) {
        if(!isValidKey(key)) {
            return false;
        }
        
        // 获取枚举实例的值（索引）
        int index = ((Enum<?>) key).ordinal();
        
        // 获取key对应的value
        Object oldValue = vals[index];
        
        return maskNull(value).equals(oldValue);
    }
    
    // 移除指定的键值对，返回值指示是否成功移除
    private boolean removeMapping(Object key, Object value) {
        if(!isValidKey(key)) {
            return false;
        }
        
        // 获取枚举实例的值（索引）
        int index = ((Enum<?>) key).ordinal();
        
        // 如果当前Map中包含指定的键值对，则将其移除
        if(maskNull(value).equals(vals[index])) {
            vals[index] = null;
            size--;
            return true;
        }
        
        return false;
    }
    
    /**
     * Returns true if key is of the proper type to be a key in this
     * enum map.
     */
    // 验证key是否有效
    private boolean isValidKey(Object key) {
        if(key == null) {
            return false;
        }
        
        // Cheaper than instanceof Enum followed by getDeclaringClass
        Class<?> keyClass = key.getClass();
        return keyClass == keyType || keyClass.getSuperclass() == keyType;
    }
    
    private boolean equals(EnumMap<?, ?> em) {
        if(em.size != size)
            return false;
        
        if(em.keyType != keyType)
            return size == 0;
        
        // Key types match, compare each value
        for(int i = 0; i<keyUniverse.length; i++) {
            Object ourValue = vals[i];
            Object hisValue = em.vals[i];
            if(hisValue != ourValue && (hisValue == null || !hisValue.equals(ourValue)))
                return false;
        }
        return true;
    }
    
    private int entryHashCode(int index) {
        return (keyUniverse[index].hashCode() ^ vals[index].hashCode());
    }
    
    /**
     * Throws an exception if e is not of the correct type for this enum set.
     */
    private void typeCheck(K key) {
        Class<?> keyClass = key.getClass();
        if(keyClass != keyType && keyClass.getSuperclass() != keyType) {
            throw new ClassCastException(keyClass + " != " + keyType);
        }
    }
    
    
    
    
    
    
    // key的集合
    private class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
            return new KeyIterator();
        }
        
        public int size() {
            return size;
        }
        
        public boolean contains(Object o) {
            return containsKey(o);
        }
        
        public boolean remove(Object o) {
            int oldSize = size;
            EnumMap.this.remove(o);
            return size != oldSize;
        }
        
        public void clear() {
            EnumMap.this.clear();
        }
    }
    
    // value的集合
    private class Values extends AbstractCollection<V> {
        public Iterator<V> iterator() {
            return new ValueIterator();
        }
        
        public int size() {
            return size;
        }
        
        public boolean contains(Object o) {
            return containsValue(o);
        }
        
        public boolean remove(Object o) {
            o = maskNull(o);
            
            for(int i = 0; i<vals.length; i++) {
                if(o.equals(vals[i])) {
                    vals[i] = null;
                    size--;
                    return true;
                }
            }
            return false;
        }
        
        public void clear() {
            EnumMap.this.clear();
        }
    }
    
    // key-value的集合
    private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
        public Iterator<Map.Entry<K, V>> iterator() {
            return new EntryIterator();
        }
        
        public boolean contains(Object o) {
            if(!(o instanceof Map.Entry)) {
                return false;
            }
            
            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
            
            // 判断当前Map中是否包含指定的键值对
            return containsMapping(entry.getKey(), entry.getValue());
        }
        
        public boolean remove(Object o) {
            if(!(o instanceof Map.Entry)) {
                return false;
            }
            
            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
            
            // 移除指定的键值对，返回值指示是否成功移除
            return removeMapping(entry.getKey(), entry.getValue());
        }
        
        public int size() {
            return size;
        }
        
        public void clear() {
            EnumMap.this.clear();
        }
        
        public Object[] toArray() {
            return fillEntryArray(new Object[size]);
        }
        
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            
            if(a.length<size) {
                a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
            }
            
            if(a.length>size) {
                a[size] = null;
            }
            
            return (T[]) fillEntryArray(a);
        }
        
        private Object[] fillEntryArray(Object[] a) {
            int j = 0;
            
            for(int i = 0; i<vals.length; i++) {
                if(vals[i] != null) {
                    a[j++] = new SimpleEntry<>(keyUniverse[i], unmaskNull(vals[i]));
                }
            }
            
            return a;
        }
    }
    
    
    
    // 迭代器，用来遍历EnumMap中的key、value、entry
    private abstract class EnumMapIterator<T> implements Iterator<T> {
        // Lower bound on index of next element to return
        int index = 0;  // 指向下一个未遍历元素(可能指向空槽)
        
        // Index of last returned element, or -1 if none
        int lastReturnedIndex = -1;     // 记录上次遍历命中的元素
        
        // 是否存在下一个未遍历元素
        public boolean hasNext() {
            // 跳过没有值的空槽
            while(index<vals.length && vals[index] == null) {
                index++;
            }
            
            return index != vals.length;
        }
        
        // 移除上一个遍历的元素
        public void remove() {
            checkLastReturnedIndex();
            
            if(vals[lastReturnedIndex] != null) {
                vals[lastReturnedIndex] = null;
                size--;
            }
            
            lastReturnedIndex = -1;
        }
        
        private void checkLastReturnedIndex() {
            if(lastReturnedIndex<0) {
                throw new IllegalStateException();
            }
        }
    }
    
    // key的迭代器
    private class KeyIterator extends EnumMapIterator<K> {
        // 返回下一个key
        public K next() {
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
            
            lastReturnedIndex = index++;
            return keyUniverse[lastReturnedIndex];
        }
    }
    
    // value的迭代器
    private class ValueIterator extends EnumMapIterator<V> {
        // 返回下一个value
        public V next() {
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
            
            lastReturnedIndex = index++;
            return unmaskNull(vals[lastReturnedIndex]);
        }
    }
    
    // entry的迭代器
    private class EntryIterator extends EnumMapIterator<Map.Entry<K, V>> {
        private Entry lastReturnedEntry;
        
        // 返回下一个entry
        public Map.Entry<K, V> next() {
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
            
            lastReturnedEntry = new Entry(index++);
            return lastReturnedEntry;
        }
        
        // 移除上一个遍历的元素
        public void remove() {
            lastReturnedIndex = ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
            super.remove();
            lastReturnedEntry.index = lastReturnedIndex;
            lastReturnedEntry = null;
        }
        
        private class Entry implements Map.Entry<K, V> {
            private int index;
            
            private Entry(int index) {
                this.index = index;
            }
            
            public K getKey() {
                checkIndexForEntryUse();
                return keyUniverse[index];
            }
            
            public V getValue() {
                checkIndexForEntryUse();
                return unmaskNull(vals[index]);
            }
            
            public V setValue(V value) {
                checkIndexForEntryUse();
                V oldValue = unmaskNull(vals[index]);
                vals[index] = maskNull(value);
                return oldValue;
            }
            
            public boolean equals(Object o) {
                if(index<0) {
                    return o == this;
                }
                
                if(!(o instanceof Map.Entry)) {
                    return false;
                }
                
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                V ourValue = unmaskNull(vals[index]);
                Object hisValue = e.getValue();
                return (e.getKey() == keyUniverse[index] && (ourValue == hisValue || (ourValue != null && ourValue.equals(hisValue))));
            }
            
            public int hashCode() {
                if(index<0) {
                    return super.hashCode();
                }
                
                return entryHashCode(index);
            }
            
            public String toString() {
                if(index<0) {
                    return super.toString();
                }
                
                return keyUniverse[index] + "=" + unmaskNull(vals[index]);
            }
            
            private void checkIndexForEntryUse() {
                if(index<0) {
                    throw new IllegalStateException("Entry was removed");
                }
            }
        }
    }
    
}