7.[과제] Enum을 키로 사용하는 Map을 쓸 때 EnumMap을 쓰는게 더 효율적인 이유

EnumMap과 HashMap의 기반

EnumMap은 enum constants(이늄 상수)로 이루어진 자연스러운 순서에 기반을 두고있는 반면, HashMap은 Hash Table을 기반으로 구현되어 있다.

 

EnumMap의 생성자

EnumMap은 생성될 때 지정된 이늄상수를 사용하여 비어있는 맵을 만든다. keyUniverse가 이늄상수를 배열로 가지고 있고, keyUniverse의 배열의 길이로 값이 들어갈 비어있는 배열(vals)을 만든다.

// EnumMap.class
  public EnumMap(Class<K> keyType) {
    this.keyType = keyType;
    keyUniverse = getKeyUniverse(keyType);
    vals = new Object[keyUniverse.length];
  }

 

EnumMap의 put메소드

EnumMap이 구현한 put메소드를 보면, key값에 ordinal이라는 메소드를 통해 index정보를 가져오는데, 이 ordinal은 Enum 타입이 제공하는 메소드로, 이늄상수가 선언된 순서로 매겨진 index정보를 리턴한다.

vals[index]로 key와 매핑되는 value의 위치를 바로 찾아서, value를 업데이트 할 수 있다.

// EnumMap.class
  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);
   }

 

Hash Table

HashMap은 Hash Table 기반으로 구현되어있다는데, Hash Table은 뭘까?

 

유튜브에서 이해가 가는 설명을 찾았다.

"Hash Table은 검색하고자 하는 key값을 입력받아서, 해시함수를 돌려서 반환받은 HashCode를 배열의 Index로 환산을 해서, 데이터에 접근하는 방식의 자료구조입니다. 여기서 사용하는 키값은 문자열, 숫자, 파일도 될 수 있습니다. 해시 함수는 어떤 특정한 규칙을 이용해서, 입력받은 키 값으로 그 키값이 얼마나 큰지에 상관없이 동일한 해시코드를 만들어줍니다." (출처: https://youtu.be/Vi0hauJemxA)

 

이해한 바로는, key값을 넣으면 hash함수를 사용해서 key값을 숫자로 변환한다. hash함수로 변환한 값을 index로 사용하기 때문에, 동일한 key값을 넣으면 hash함수는 항상 동일한 값을 리턴한다. 배열의 처음부터 끝까지 검사하는 방식이 아니라, 배열의 인덱스값을 찾아서 꺼내오는 방식이기 때문에, 매우 많은 데이터를 넣어도 성능이 일정하다. 

 

버킷, 부하계수와 용량의 resize, Node와 Tree, Linked List 같은 키워드들이 더 있지만, 일단계로는 여기까지만 이해하도록 하겠다.

 

HashMap의 put메소드

코드로 가서, HashMap의 put메소드를 보면, 받은 key값을 hash()메소드로 해시값으로 변환해서 putVal매소드의 아규먼트로 사용하는 것을 볼 수 있다.

  public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
  }

 

putVal 메소드가 복잡해서 더 이상 코드를 보지 않고, 왜 대부분의 경우 EnumMap이 HashMap보다 빠를지에 대해 정리해 보자.

 

✔ EnumMap이 HashMap보다 성능상 효율적인 이유

1. EnumMap은 값을 찾을 때, 이늄상수가 index정보를 ordinal메소드로 제공하고 있기 때문에, 바로 찾을 수 있다. 

2. 반면, HashMap은 찾을 때, key값을 hash메소드로 index로 변환하고 찾아야 한다.

3. 값을 넣을 때, EumMap은 key의 index정보로 값이 저장된 위치를 찾아서 바로 값을 넣는다.

4. 하지만, HashMap은 key값을 hash로 만들고, 배열의 크기를 조절하는 등의 일이 추가로 필요하다.

5. 때문에, 배열의 크기가 고정되고 바로 찾을 수 있는 EnumMap이 성능상 훨씬 더 효율적이다.