개요
이 포스팅에서는 자바 Collections API로 표현되는 자료구조들의 성능에 대해서 이야기하고자 한다. 성능은 시간 복잡도(Time Complexity)를 기준으로 하며, 발생할 수 있는 최대 복잡도를 가리키는 Big-O 노테이션으로 정의한다.
자료 구조 성능 요약
평균값인 빅-세타-노테이션과 최악의 경우인 빅-오-노테이션을 혼용해 표현하고 있으나 보통은 빅-오-노테이션이 보편적으로 사용된다.
리스트
List 인터페이스는 Collection 인터페이스를 상속한다. 리스트자료 구조는 삽입 순서(Insertion order)가 유지되며, 동기화 미지원(Non synchronized) 이라는 공통점을 가진다. 또한 리스트는 중복 값을 포함할 수 있고, 복수의 Null 값을 포함할 수 있다. 아래에서 List 인터페이스를 구현하는 ArrayList와 LinkedList에 대해 다루겠다.
구조
어레이 리스트는 RandomAccess 마커 인터페이스를 상속하여 구현된다. 모든 원소는 각자의 인덱스와 실제 데이터 값을 가진다. 이 인덱스를 가지고 해당 데이터로 바로 접근할 수 있다. 그러므로 Get 오퍼레이션 시의 시간 복잡도는 O(1)이 된다.
연결 리스트는 노드값이외에 앞 뒤 포인터 값을 저장하고 있는 자료구조이며, 랜덤 접근(Random Access)이 아닌 순차 접근(Sequential Access) 방식을 따르므로 어레이 리스트처럼 바로 해당 데이터로 접근할 수가 없다. 위의 그림에서 연결 리스트의 가장 말단에 저장된 데이터를 조회하려고 할 때에는 순차적으로 노드의 다음 값을 따라가며 0, 1, 2, 3번째를 거쳐 4번째에서야 해당 데이터를 조회하게 된다. 리스트의 저장 개수인 n에 비례하여 조회해야 하는 데이터 개수도 늘어나게 된다. 따라서 Get 오퍼레이션 시 시간 복잡도는 O(n)이 된다.
메모리 점유율 면에서는 어레이 리스트가 연결 리스트보다 더 효율적이다. 어레이 리스트는 실제 데이터와 인덱스만 저장하는 반면, 연결 리스트의 각각의 노드는 데이터와 앞 뒤의 원소의 포인터값까지 저장함으로써 더 많은 메모리를 점유하기 때문이다.
어레이 리스트는 인덱스가 순차적으로 존재해야하는 구조 특성상, 한 원소를 삽입/삭제 시 배열의 나머지 원소들의 인덱스 참조값을 수정해야 하게 된다. 따라서 추가/삭제 오퍼레이션의 시간 복잡도는 O(n)이 된다. 위의 그림의 어레이 리스트 배열을 보자. 총 6개의 인덱스를 가지던 배열에서 3번 원소를 삭제하면, 4, 5, 6번째 원소는 각각 3, 4, 5번으로 수정되어야 하므로 한 칸씩 당겨진다.
연결 리스트는 노드값이외에 앞 뒤 포인터 값을 저장하고 있는 자료구조이므로, 삭제와 삽입시 해당 노드 앞 뒤의 포인터 값만 수정하여주면 추가/삭제가 완료된다. 따라서 시간 복잡도는 전체 데이터 수에 종속되지 않으므로 O(1)이다. 물론 삭제, 추가할 위치를 알고 있다는 가정하의 효율값이고 모른다면 검색이 필요하므로 시간 복잡도는 O(n)이 된다. (그러나 보통 알고 있다고 가정하여 O(1)으로 정의한다.)
성능
| Add | Remove | Get | Contains | |
| ArrayList | O(n) | O(n) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
사용 용도
데이터 조회가 자주 이루어질 때 ArrayList를 사용하는 것이 유리하다.
데이터의 삽입, 삭제가 빈번히 일어날 때 LinkedList를 사용하는 것이 유리하다.
셋
Set 인터페이스는 Collection 인터페이스를 상속한다. Set은 중복값을 허용하지 않는 선형 콜렉션으로, 이미 셋 안에 존재하는 값을 add() 메소드로 삽입하려고 시도하면 False 값을 리턴시킨다. Set에서 인덱스를 이용한 랜덤 접근은 불가하지만, 원소의 정렬 순서는 Set의 구현방법에 따라 유지될 수도 있고, 유지되지 않을 수도 있다.
구조
해쉬셋은 해시함수를 사용함으로써 뛰어난 성능을 보인다. 해시함수란, 어떤 가변 값의 key를 input으로 해시함수에 넣으면 output으로 고정된 hash값이 나오게 하는 것이다. 예를 들어, 내부 로직이 f(x)= x % 10 인 해시함수가 있다고 가정했을 때 84, 123, 27의 해쉬값은 각각 4, 3, 7이 되고, 이 해쉬값의 값에 따라 정렬하여 저장한다. 즉, 3:123, 4:84, 7:27의 순서대로 저장이 되게 된다.
그런데, input은 거의 무한대의 가변값인데 반해 hash는 고정값을 가지므로, 중복 hash값이 발생할 수 있다. 가령 위의 해시함수에 223이라는 값을 input으로 넣어도 123을 넣었을 때와 같은 hash값(3)을 얻게 된다. 이러한 현상을 해시 충돌(hash collision)이라고 하는데, 이때에는 동일한 해쉬값에 대해 LinkedList로 저장된다.
트리셋은 이진 탐색 트리에 자료를 저장하는 자료구조이다.
성능
| Add/Removal | Contains | Next | |
| HashSet | O(1) | O(1) | O(1) |
| LinkedHashSet | O(1) | O(1) | O(1) |
| TreeSet | O(log(n)) | O(log(n)) | O(log(n)) |
해쉬셋과 연결해쉬셋은 해쉬값으로 호출/삭제/삽입을 하므로 모든 연산에 있어 O(1)의 시간 효율성을 가진다.
트리셋은 이진 탐색 트리를 사용하므로, 검색/삽입/삭제의 시간 효율성은 log(n)을 가지게 된다.
비교
아래에서 Set 인터페이스를 구현하는 HashSet, Linked-HashSet, TreeSet을 비교한다.
| HashSet | LinkedHashSet | TreeSet | |
| 정렬 순서 | 유지되지 않음 | 삽입순서 유지 | Comporator가 정의되지 않을 경우 오름차순에 의해 자동 정렬. |
| 성능 | 가장 좋음 | 삽입순서를 유지하기 위하여 포인터값을 저장하므로 HashSet 보다 약간 느리다. | 삽입과 삭제 오퍼레이션 후 재정렬해야하므로 셋 중에서 가장 느리다. |
| Null Value | 최대 한 개의 Null 허용 | 최대 한 개의 Null 허용 | 허용하지 않음 () |
| 사용 용도 | 순서를 유지할 필요가 없다면 일반적으로 권장된다 | 삽입순서를 유지하고 싶다면 선택 | Comparator에 의해 원소들을 정렬하고 싶다면 선택 |
맵
맵은 (Key, Value) 페어 구조의 데이터를 저장할 때에 쓰이는 자료구조이다. Key 값이 유일값이라면 Value 값은 중복이 되어도 상관없다. 저장 순서는 Map의 구현 방법에 따라 유지될 수도 있고, 유지되지 않을 수도 있다.
구조
리스트, 셋, 큐 등의 인터페이스들이 Collection 인터페이스를 상속하는 것과 달리, 맵 인터페이스는 Collection 인터페이스를 상속하지 않는다. K-V 페어 형태를 가지는 맵의 구조가 다른 자료구조들과 다르기 때문이다.
성능
| Add/Removal | Contains | Next | |
| HashMap | O(1) | O(1) | O(1) |
| LinkedHashMap | O(1) | O(1) | O(1) |
| TreeMap | O(log(n)) | O(log(n)) | O(log(n)) |
비교
Map 인터페이스를 구현하는 HashTable, HashSet, Linked-HashSet, TreeSet의 비교
| HashTable | HashMap | LinkedHashMap | TreeMap | |
| 내부로직 | Hashing | Hashing | Hashing | 이진 탐색 트리 |
| 동기화 | Thread safe | Not Thread safe | Not Thread safe | Not Thread safe |
| 정렬 순서 | 유지되지 않음 | 유지되지 않음 | 삽입순서 유지 | Comporator가 정의되지 않을 경우 오름차순에 의해 자동 정렬. |
| 성능 | 동기화되므로 해쉬맵보다 약간 느리다 | 가장 좋음 | 삽입순서를 유지하기 위하여 포인터값을 저장하므로 HashMap 보다 약간 느리다. | 삽입과 삭제 오퍼레이션 후 재정렬해야하므로 가장 느리다 |
| Null Value | 허용하지 않음 | Key값으로 최대 한 개의 Null 허용, V값으로 복수의 Null 허용 | Key값으로 최대 한 개의 Null 허용, V값으로 복수의 Null 허용 | 허용하지 않음 |
| 사용 용도 | 쓰레드 세이프티가 요구될 때 사용한다 | 가장 좋은 퍼포먼스를 보이므로, 일반적으로 권장된다 | 삽입순서를 유지하고 싶다면 선택 | Comparator에 의해 원소들을 정렬하고 싶다면 선택 |
'☆IT 개발 프로그램☆ > JAVA' 카테고리의 다른 글
| [Terminal] Mac에서 Home Brew로 JAVA 재설치하기 (0) | 2020.06.04 |
|---|---|
| [개발자 면접 질문] JAVA 기초 질문 모음 10개 (0) | 2020.06.04 |
| [개발자 면접 질문] JAVA 기초 질문 모음 Q11~20 (2편) (0) | 2020.06.04 |
| [JAVA 메모리 트러블 슈팅] 콘솔에서 JVM Heap 메모리 추적하기 : jstat, jmap (0) | 2020.06.04 |
| [디자인패턴] 자바 싱글톤 Vs 스프링 싱글톤 패턴의 차이점 (0) | 2020.06.04 |