java集合之：EnumMap

江南一阵风

一般来说，我们保存key-value格式的数据时，首先会想到的是HashMap。枚举是我们开发中经常使用到的类型，假如保存的key-value中的key都是某一个类型的枚举时，有没有更好的集合用来存储和访问数据呢？接下来我们就来谈谈java中的EnumMap。

有道无术，术尚可求；有术无道，则止于术。对于软件编程，比了解一套技术具体实现更重要的是领会它背后的算法思想，只要领会了它背后的算法思想，自己也可以实现一套类似的功能。现在我们拿HashMap做对比，谈谈EnumMap背后的算法思想。

作为java中最常用的集合之一——HashMap，每一位同学都曾使用过它，但不见得所有人都对它内部的思想认真思考过。

对于一个集合(key-value能看做一个整体，作为集合中的一个元素)，我们首先想到的是可以把它保存到数组或者链表中。但保存在数组(或者链表)中的话，查询速度就慢了。如果你要查询数组中的某一个元素时，只能从数组头部开始，对数组中元素一个个遍历比对，判断是否等于要查的元素。比如有一个班级总共50名同学，有一个数组保存了全班所有同学的信息(key：同学名。value:同学的其它信息)，那么你要查询xiaoming同学的信息时，只能从数组开始，一条条遍历比对该元素的key是否等于xiaoming。那么每次查询平均需要遍历25条数据，时间复杂度为O(n)，这种查询速度是很慢的。

那么针对上面所说的查询速度慢的问题，有没有什么办法解决呢？我们知道通过数组下标对数组元素的查找，速度是极快的。如果我们对上面元素的查找，能转换成通过数组下标进行查找，该是多么完美啊。完美是难以达到的，但我们可以想法设法的去向完美靠近。

如果我们能通过元素对象直接映射到数组下标，那么就能实现上面所说的通过数组下标进行对数组查找的完美实现。那么就需要某种机制把元素对象映射成整数数字，如果映射到的整数数字能够是连续的、且是唯一的，那是再好不过了，不过各个无关联的元素对象想做到那样是实现不了的。如果实现不了映射到的数字的连续唯一性，那么如果能让它们映射到的整数尽量均匀的分布，那也挺好啊。这里就出现了hash的思想，每个元素对象的hash值代表着元素对象到整数的映射值。现在有了对象到整数的映射值——hash值，新的问题又来了：比如数组长度是1万，但对象的hash值可能是19999，也就是超过了一万，这该怎么办呢？熟悉数学的都知道，这个问题可以通过对hash值对数组长度取模获得，也就是：hash值 % 数组长度 = 数组元素对应的数组下标。

通过上面的逻辑实现了数组对象到数组下标的映射，不过又出现了新的问题：不同对象的hash值可能相同，即使hash值不同，取模后也可能相同。那就出现了一种情况：不同的对象，映射到的数组下标相同了。这些不同的元素在数组中的位置相同，我们称为hash冲突，那就把这些元素用链表链接起来（这篇文章暂不讨论java8中的红黑树）。我们是不希望hash冲突的，为了使每个元素所在的数组位置都不相同，此时可以适当扩大数组的长度，也就是让数组元素根据hash分布在更大的空间。比如当元素个数达到数组总长度的0.75时，就扩大数组长度，这样可以减少hash冲突的概率。如此以来，根据泊松分布理论，hash冲突的元素比较多的情况仅是小概率事件。

通过上面的实现，我们每次对元素进行查询时，就可以通过元素直接获取到它的hash值，再通过hash值直接计算出它对应的数组下标位置，如果没有hash冲突，这样就直接做下equal比对就查到元素了，此时时间复杂度为O(1)。因为有hash冲突的存在，总体时间复杂度略大于O(1)。虽然hash冲突的元素比较多的情况仅是小概率事件，但小概率事件也有发生的可能性。极端情况是所有元素的hash值都一样，那么这时对元素的查询就变成了单纯的对链表的查询，此时时间复杂度为O(n)。

上面的探讨过程就代表了HashMap的内部实现（数组+链表）的原理。大体上可以把HashMap看成为了在查询速度上能尽量接近于通过数组下标对数组的查询，通过元素的hash值映射成数组下标，接着为了兼容下hash冲突的情况又被迫对相同hash值的元素采用链表链接。

上面咱们探讨了HashMap的实现原理，接下来回到最初的话题：EnumMap。如果HashMap中的所有key都是某一个类型的枚举呢？上面对HashMap的讨论，首先需要一种机制：元素对象到整数值的映射机制，这个整数值最终会转化为数组下标。上面也说了，这里映射到的整数值最好是连续的、且是唯一的，普通的元素对象做不到这一点，所以被迫采用对象的hash散列值。但如果都是某一个类型的枚举，那就不一样了！

经常使用枚举的同学都知道，每个枚举值都有属性ordinal，该属性代表枚举值在枚举类型中的从0开始的序号。ordinal是连续的、且是唯一的，那么拿ordinal作为元素到整数值的映射，岂不是再好不过了。而且ordinal是从0开始的，且是有界的（枚举类型的对象个数），那么直接拿ordinal作为数组下标，连取模操作都不需要了！且因为ordinal的唯一性，也不会再存在上面hash冲突的问题，链表根本就不需要，仅用一个数组就可以了！因为没有hash冲突问题，也不需要通过扩大数组长度防止hash冲突过多的问题，数组长度直接固定等于枚举元素个数就行了，空间存储也更紧凑。

通过上面讨论，针对所有key都是某一个类型的枚举时，查询元素，直接通过枚举元素的ordinal，该值代表着数组下标，通过数组下标，直接就定位到了数组中的元素，也没有了HashMap中对hash值的计算和不厌其烦的equals判断。这查询速度就是通过数组下标查询数组元素的完美速度，速度是极快的。

上面就是EnumMap内部的实现套路。EnumMap是一种特殊的Map，它的所有key都属于某一种枚举类型，更关注元素的查询性能。接下来我们通过对EnumMap的使用示例和源码分析，进行进一步的讲解。

//ProductName代表银行的产品名。Loan、Stock、Bond都是银行产品的一种。下面通过EnumMap实现了获取银行产品的工厂模式
public static final Map<ProductName, Supplier<Product>> productFactory = new EnumMap<>(ProductName.class);
productFactory.put(ProductName.LOAN, Loan:new);
productFactory.put(ProductName.STOCK, Stock:new);
productFactory.put(ProductName.BOND, Bond:new);
public static Product createProduct(ProductName productName){
  return Optional.ofNullable(productName.get(productName))
                  .map(Supplier::get)
                  .orThrow(() -> new IllegalArgumentException("No such product " + productName));
}

下面进行对EnumMap的源码分析。

类层次结构。 通过下面源码可以看出EnumMap的类层次结构和HashMap完全一样，一样继承类AbstractMap、一样实现了接口Map。所以可以像平时使用其它Map一样使用EnumMap，唯一不同的是：如EnumMap定义中的K extends Enum<K>，该Map的key必须都是同一种枚举类型。

public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
    implements java.io.Serializable, Cloneable

构造函数。 通过下面源码可以看出EnumMap采用了数组(vals)保存值，且数组长度等于枚举常量的总数。

    /**
     * 根据枚举类型的Class构建EnumMap
    public EnumMap(Class<K> keyType) {
        //EnumMap中key的Class类型
        this.keyType = keyType;
        //获取枚举K中的所有枚举常量。从下面方法getKeyUniverse的方法声明<K extends Enum<K>>可以看出，K必须是枚举类型
        keyUniverse = getKeyUniverse(keyType);
        //初始化数组。和上面分析一样，EnumMap中的元素是直接放入数组中的，数组长度等于枚举类型中枚举常量的总数。
        vals = new Object[keyUniverse.length];
    private static <K extends Enum<K>> K[] getKeyUniverse(Class<K> keyType) {
        return SharedSecrets.getJavaLangAccess()
                                        .getEnumConstantsShared(keyType);
    }

添加元素put方法。 通过下面源码可以看出EnumMap中，枚举的ordinal代表着元素在数组中的位置。

public V put(K key, V value) {
        //检查key是否是创建EnumMap时指定的枚举类型
        typeCheck(key);
        //key的枚举ordinal，这代表着这次插入的元素放到数组中的位置。
        int index = key.ordinal();
        Object oldValue = vals[index];
        //在数组中的ordinal位置放入元素value
        vals[index] = maskNull(value);
        if (oldValue == null)
            size++;