Java 문법을 복습하며 Collection 구현체들을 정리하던 중 Set의 구현체 다수에서 Map을 사용하는 것을 확인하였습니다.
Map에 대한 지식없이 Set 구현체를 이해하는 것에 어려움이 있어 관련내용을 공부하며 정리하였습니다.
Naver D2 Helloworld의 글
테드의 기술블로그
Key-Value 쌍으로 이루어진 자료형
Map은 Key와 Value를 각각 한쌍으로 묶어 데이터를 저장하는 Java 자료형을 의미합니다.
자세한 내용은 이 글을 참고해주세요
전체적인 상속관계는 다음과 같습니다
- AbstractMap (implements Map) [Class(Abstract)]
- HashMap (implements Clonable, java.io.Serializable) [Class]
읽기/쓰기작업을 자주 진행하고, 삽입순서가 고려되지 않아도 되는경우 사용
HashMap의 구현체는 다른 자료구조에 비해 구현이 복잡하여, 별도로 정리해보았습니다.
HashMap은 내부에서 Map.Entry를 extend하는 Node 객체 배열을 통해 데이터를 관리합니다. (이 배열을 앞으로 bucket이라 부르고, Node를 담는 각 칸을 slot이라 합니다)
이 배열에 최대한 많은 데이터를 담고 빠르게 접근하기 위해, HashMap은 각 slot에 최대 8개의 값을 LinkedList구조로 담고, 이후부터는 TreeMap 형식으로 변경하여 관리합니다. (성능저하 문제로 인한 Java8 이후 조치사항)
HashMap을 constructor로 생성하면, 인자로 받는 loadFactor를 통해 treshold를 설정합니다.
이 2개의 값은 각각 필드에 저장되어, 나중에 데이터추가 시 bucket의 크기를 재설정하는 기준이 됩니다.
HashMap.put()을 통해 데이터를 추가하게 되면, 내부의 HashMap.putVal() 메서드를 호출하여 아래와 같이 데이터 추가작업을 수행합니다.
이중 2번 과정에서 다양한 조건별 동작방식이 달라지는데, 조건 별 동작방식은 다음과 같다:
| 조건1 (slot 내 Node 개수) | 조건2 (Node 저장방식) | 동작 | 소요시간 |
|---|---|---|---|
| 0개 | LinkedList | Node에 감싸 데이터 저장 | O(1) |
| 1~8개 | LinkedList | LinkedList 형태로 데이터 추가 | O(1) |
| 9개~ | LinkedList | TreeMap으로 내부데이터 저장형식 전환 후 데이터 추가 | O(1) |
| 9개~ | TreeMap | 저장위치 연산 후 접근하여 데이터 추가 | O(n) |
HashMap.get()를 통해 데이터 접근 시, 내부의 HashMap.getNode() 메서드를 호출하여 데이터를 가져오게 됩니다.
실제 데이터 접근시 저장형태에 따라 소요시간이 달라지는데, 저장형태 별 소요시간은 다음과 같습니다:
| Node 저장방식 | 동작 | 소요시간 |
|---|---|---|
| LinkedList | 일치하는 key값을 찾을 때 까지 do-while문으로 순회하며 탐색 | O(1) |
| TreeMap | TreeMap의 getTreeNode() 메서드 호출하여 탐색 | O(n) |
+) LinkedList방식으로 저장 시 소요시간이 O(1)인 이유는 do-while 문을 사용하더라도 저장개수 제한되어 있어 최대 8회만 동작하기 때문이다.
최종적으로 동작 별 소요되는 시간복잡도는 다음과 같습니다:
| 동작유형 | 시간복잡도 | 설명 |
|---|---|---|
| 추가 | O(1) / O(n) | TreeMap 사용 시 최대 O(n) |
| 조회 - get | O(1) / O(n) | TreeMap 사용 시 최대 O(n) |
| 조회 - contains | O(n) | for문으로 순회하며 데이터 존재여부 확인 |
| 삭제 | O(1) / O(n) | TreeMap 사용 시 최대 O(n) |
Set을 더 정확히 이해하기 위해 본 HashMap의 양이 생각보다 많았습니다.
그래도 이왕 시작한만큼 제대로 정리해서 이해할 수 있도록 노력해야겠습니다.