Why an EnumSet or an EnumMap is likely to be more performant than their hashed counterparts?

Question

The following is from the Implementation Note section of Java doc of EnumMap :

Implementation note: All basic operations execute in constant time. They are likely (though not guaranteed) to be faster than their HashMap counterparts.

I have seen a similar line in the java doc for EnumSet also . I want to know why is it more likely that EnumSets and EnumMaps will be more faster than their hashed counterparts ?

Answer 1

EnumSet is backed by a bit array. Since the number of different items you can put in EnumSet is known in advance, we can simply reserve one bit for each enum value. You can imagine similar optimization for Set<Byte> or Set<Short>, but it's not feasible for Set<Integer> (you'd need 0.5 GiB of memory for 2^32 bits) or in general.

Thus basic operations like exists or add ar constant time (just like HashSet) but they simply need to examine or set one bit. No hashCode() computation. This is why EnumSet is faster. Also more complex operations like union or easily implemented using bit manipulation techniques.

In OpenJDK there are two implementations of EnumSet: RegularEnumSet capable of handling enum with up to 64 values in long and JumboEnumSet for bigger enums (using long[]). But it's just an implementation detail.

EnumMap works on similar principles, but it uses Object[] to store values while key (index) is implicitly inferred from Enum.ordinal().

Answer 2

EnumSet uses array[] inside and a natural order with consequent consequences:

• fast: get/set is called by constant time O(1), hashCode() is not used to find a right bucket
• memory efficiency: the size of array is predefined by Enum size and is not dynamic

EnumMap uses Enum as a key based on the same principals as EnumSet where hash code collision is not possible