Почему EnumSet или EnumMap могут быть более производительными, чем их хешированные аналоги?
Ниже приведен раздел " Замечания по реализации " документа Java в EnumMap:
Примечание по реализации: Все основные операции выполняются в постоянное время. Вероятно, они (хотя и не гарантированы) будут быстрее, чем их аналоги из HashMap.
Я видел похожую строку в документе Java для EnumSet также. Я хочу знать, почему это более вероятно, что EnumSets а также EnumMaps будет быстрее, чем их хешированные аналоги?
1 ответ
EnumSet поддерживается битовым массивом. Так как количество различных предметов вы можете положить в EnumSet заранее известно, мы можем просто зарезервировать один бит для каждого значения перечисления. Вы можете представить себе подобную оптимизацию для Set<Byte> или же Set<Short>, но это нереально для Set<Integer> (вам потребуется 0,5 ГБ памяти для 2^32 бит) или вообще.
Таким образом, основные операции, такие как exists или же add постоянное время (так же, как HashSet) но они просто должны изучить или установить один бит. нет hashCode() вычисление. Вот почему EnumSet быстрее. Также более сложные операции, такие как объединение или легко реализуемые с использованием методов манипуляции битами.
В OpenJDK есть две реализации EnumSet: RegularEnumSet способен обрабатывать enum до 64 значений в long а также JumboEnumSet для больших перечислений (используя long[]). Но это просто деталь реализации.
EnumMap работает по аналогичным принципам, но использует Object[] хранить значения, в то время как ключ (индекс) неявно выводится из Enum.ordinal(),
EnumSet использует array[] внутри и естественный порядок с вытекающими отсюда последствиями:
- быстро: get/set вызывается постоянным временем O(1),
hashCode()не используется, чтобы найти нужное ведро - эффективность памяти: размер массива предопределен размером Enum и не является динамическим
EnumMap использует Enum в качестве ключа на основе тех же принципов, что и EnumSet где коллизия хэш-кода невозможна