Enumeration에 대한 관찰에서 Enum에 대해 알아보았다. 이번에는 Enum을 효율적으로 사용 하는 방법 중 하나인 EnumMap을 살펴보자.
EnumMap
EnumMap은 Enum을 키로 사용하는 Map이다.
EnumMap 사용법
간단한 Enum
enum DayOfWeek {
MON, TUE, WED, THU, FRI, SAT, SUN
}EnumMap 생성 코드
Map<DayOfWeek, String> scheduleMap = new EnumMap<>(DayOfWeek.class);EnumMap은 AbstractMap의 구현체이기 때문에, 일반적으로 알고있는 Map의 기능들을 모두 사용 할 수 있다.
scheduleMap.put(DayOfWeek.MON, "Study");
scheduleMap.get(DayOfWeek.MON);실질적인 사용법은 일반적인 HashMap등의 다른 Map 구현체와 큰 차이가 없다.
EnumMap의 특징
- EnumMap은 내부적으로 데이터를 저장할 때 배열을 사용한다.
- 기본 연산들이 모두 상수 시간 안에 실행된다.
- 캐싱을 통한 성능 향상을 위해 키 배열 또한 가지고 있다.
- equals 연산을 할 때 내부의 key와 value가 모두 일치하는지 전체 순회를 통해 확인한다.
- AbsratctMap 클래스를 상속받으므로, Map 인터페이스 또한 상속 받는다.
- Thread-safe하지 않다. (필요하다면 Collections.synchronizedMap으로 wrap하는것을 권장한다.)
EnumMap vs HashMap
모든 연산을 다루기에는 내용이 많으니, put과 get 연산만 비교해보도록 하자.
Put 메서드 비교
EnumMap
public V put(K key, V value) {
typeCheck(key);
int index = key.ordinal();
Object oldValue = vals[index];
vals[index] = maskNull(value);
if (oldValue == null)
size++;
return unmaskNull(oldValue);
}EnumMap의 put 연산은 해당 enum의 "선언순서"를 인덱스로 사용해 배열에 저장하는 방식으로 동작한다.
만약 동일한 키로 다른 값을 삽입한다면, 이전 데이터는 제거된다.
HashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}코드의 길이부터 확연하게 차이나는것을 알 수 있다.
HashMap 또한 내부적으로 배열인 HashTable이 있다. 키의 hash값을 계산해서 테이블의 인덱스로 사용한다. 만약 해당 인덱스가 비어있다면, 그대로 값을 추가하고, 비어있지 않다면 연결리스트처럼 다음 노드로 연결하여 저장한다.
만약 이렇게 연결된 노드의 갯수가 TREEIFY_THRESHOLD(8로 지정되어있다.)를 넘어서게 되면, 연결리스트가 아닌 Tree형태로 변경되어 저장된다.
이보다 자세한 내용은 추후 HashMap 관련 글에서 다루도록 하겠다.
Put 메서드 비교 정리
- EnumMap은 키의 선언순서인 ordinal을 인덱스로 사용한다.
- HashMap은 키의 해시값을 인덱스로 사용한다.
- EnumMap과 달리 HashMap은 해시 충돌이 발생할 확률이 있으므로, 동일한 Hash값을 가지는 다른 Key를 삽입할때는 단방향 연결리스트처럼 동작한다.
- EnumMap의 삽입연산은 항상 O(1)이며, HashMap은 해시 충돌이 자주 발생한다면 O(logN)에 근접하게 된다.
Get 메서드 비교
EnumMap
public V get(Object key) {
return (isValidKey(key) ? unmaskNull(vals[((Enum<?>)key).ordinal()]) : null);
}단순히 해당 키의 ordinal을 인덱스로 사용해 배열에서 값을 꺼내 리턴한다.
HashMap
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}Put 연산에서 살펴보았듯이, 테이블에서 해시값을 인덱스로 노드를 가져오고, 노드의 키가 일치할때까지 연결리스트 또는 트리를 탐색한다.
Get 메서드 비교 정리
- EnumMap의 Get연산은 항상 O(1)을 보장하지만, HashMap은 해시 충돌이 잦으면 O(logN)에 근접한다.
바이트 코드 관련
EnumMap을 보면 Map 인터페이스를 직접 상속 받지 않지만, 생성할 때는 EnumMap 타입과 Map 타입 두가지로 생성 할 수 있다.
EnumMap<DayOfWeek ,String> scheduleMap = new EnumMap<>(DayOfWeek .class);
scheduleMap.put(DayOfWeek.MON, "Study");
scheduleMap.get(DayOfWeek.MON);
Map<DayOfWeek ,String> scheduleMap2 = new EnumMap<>(DayOfWeek .class);
scheduleMap2.put(DayOfWeek.MON, "Study");
scheduleMap2.get(DayOfWeek.MON);EnumMap으로 생성한 경우는 put과 get연산이 invokevirtual로, Map으로 생성한 경우는 invokeinterface로 호출된다.
그 이유는 EnumMap의 조상인 AbstractMap이 Map 인터페이스를 상속받기 때문이다. 따라서 Map으로 만들어도 EnumMap의 put, get 연산이 호출되니 걱정할 필요는 없다.
정리
Enum은 컴파일 시점에 전체 요소의 개수를 계산할 수 있고, 생성자를 제공하지 않으므로, 이 개수가 변경되지 않는다.
따라서 EnumMap은 데이터의 관리에 배열을 사용할 수 있고, 부수적인 자료형 또한 필요하지 않으므로 메모리를 효율적으로 사용 할 수 있다.
값에 접근할때 인덱스로 직접 배열에 접근하므로 CRUD 모두 O(1)의 시간 복잡도를 가지므로 매우 효율적인 자료구조라 볼 수 있다.
Map을 사용하는데 Key가 Enum이라면 EnumMap의 도입을 반드시 고려해보자
