[Java] Map 인터페이스와 그 구현체들에 대해 알아보자.

Map 자료구조의 특징

• Key Value로 구성된다. Key는 Value를 찾는 일종의 열쇠로 데이터마다 하나씩 부여되어야 한다.
• 즉, 키를 사용하여 데이터를 처리하므로 중복된 키가 존재하면 안 된다.
• 따라서 이미 존재하는 키값과 동일 키값으로 데이터를 넣는다면 해당 키값에 대응되는 값이 새로 넣은 값 데이터로 갱신된다.
• 키를 통해 값에 접근할 수 있기 때문에 데이터의 검색 속도가 빠르다.
• 순서를 보장하지 않는다.

그럼 Map의 구현체들에 대해 알아보자

---

HashMap

특징 

• 가장 일반적인 Map 구현체로서 내부적으로 해시 함수를 사용하여 키와 값을 저장한다.

데이터를 추가하는 put 메서드

hash 메서드 내부

• 평균적으로 O(1)의 검색 시간을 갖는다.
• Map 내의 키는 중복될 수 없고, 값은 중복될 수 있다.
• Key와 Value 값으로 NULL을 허용한다.

장점

• 검색 , 삽입, 삭제 연산의 경우 평균 시간 복잡도가 O(1)로 매우 빠르다.

단점

• 저장 순서가 유지되지 않는다. 삽입한 순서와 상관없이 키와 값은 무작위로 저장된다.
• 동시성 문제가 발생할 수 있다. 동기화를 지원하지 않기 때문에 멀티쓰레드 환경에서는 주의해서 사용해야 한다.

 

TreeMap

특징

• 이진 검색 트리를 사용하여 키와 값을 저장한다.
• 키를 기준으로 정렬된 순서로 저장된다.
• 검색, 삽입, 삭제 연산의 시간 복잡도는 O(logn)이다.
• 키와 값은 null이 될 수 있다.

장점

• 이미 정렬되어 있는 상태이기에 검색이나 범위 검색에 있어 성능이 뛰어나다.
• 데이터의 크기에 상관없이 일정한 성능을 보장한다.

단점

• 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제에 대한 연산이 HashMap보다 느리다.
• 또한 검색도 이진검색트리를 타고 내려가야 하기에 HashMap에 비해 상대적으로 느리다.
• 저장된 데이터가 많을 경우, 이진 검색 트리의 깊이가 검색 성능이 저하될 수 있다.

따라서 데이터를 정렬된 상태로 사용하고자할 때면 TreeMap을 고려해야한다.

 

LinkedHashMap

HashMap과 비슷하지만 삽입 순서를 보장한다.

특징

• HashMap과의 차이점이라고는 LinkedHashMap은 데이터의 삽입 순서를 보장한다.

장점

• Map을 사용하는데 입력순서가 중요한 경우 사용할 수 있다.

아래의 예시를 보면 LinkedHashMap에 데이터를 넣었을 때 순서가 유지되는 것을 볼 수 있다.

ConcurrentHashMap

특징

• 멀티스레드 환경에서 안전하게 사용할 수 있다.
• ConcurrentHashMap은 내부적으로 세그먼트라는 동시성 레벨을 가진 부분으로 분할하여 동시성을 보장한다.

장점

• 멀티스레드 환경에서 안전하게 사용할 수 있다.
• 전체 맵을 락하지 않고도 부분적으로 락을 걸 수 있어서, 성능을 향상시킬 수 있다.

단점

• 동기화를 지원하기에 HashMap보다는 성능이 떨어질 수 있다.

HashTable과의 차이

동기화를 지원하는 HashTable이라는 자료구조가 존재한다. HashTable은 모두 메서드에 synchronized 키워드가 존재하여 동시성 처리가 상대적으로 느리다. 이를 개선한 것이 ConcurrentHashMap인데 해시 버킷을 분할하고, 각각 분할한 것에 대해 별도의 동기화 기법을 사용하여 동시성 처리를 하여 성능을 개선했다.

동시에 업데이트를 수행하는 쓰레드

EnumMap

enum 타입을 키로 사용할 때 최적화된 자료구조이다.

특징

• 검색, 삽입, 삭제 연산의 시간 복잡도가 O(1)이다.
• EnumMap은 enum 타입을 키로 사용할 때 최적화된 자료구조이다.
• keySet()과 entrySet() 메서드를 사용해서 Map 내의 키나 값에 접근할 수 있다.

장점

• enum타입을 키로 사용하는 경우, EnumMap은 가장 적합한 Map의 구현체이다.

단점

• enum 타입을 사용하지 않는 경우, EnumMap을 사용할 수 없다.
• EnumMap은 순서가 보장되지 않으며, 키와 값에 null이 들어갈 수 없다.

 

WeakHashMap

특징

• 키에 대한 참조가 더 이상 존재하지 않으면, 자동으로 메모리에서 제거된다.
• Map 인터페이스를 구현한 클래스 중에서 유일하게 GC에 영향을 받는다.

장점

• 메모리 누수를 방지할 수 있다.
• 메모리를 보다 효율적으로 사용할 수 있다.
• 캐시와 같은 용도로 사용될 때 적합나다.