[JAVA Collections API] 자료구조 요약: 구조/성능/용도

개요

이 포스팅에서는 자바 Collections API로 표현되는 자료구조들의 성능에 대해서 이야기하고자 한다. 성능은 시간 복잡도(Time Complexity)를 기준으로 하며, 발생할 수 있는 최대 복잡도를 가리키는 Big-O 노테이션으로 정의한다.

 

1. 자료 구조 성능 요약

2. 리스트

3. 셋

4. 맵

 

---

 

자료 구조 성능 요약

자료 구조의 오퍼레이션에 따른 시간복잡도 테이블. 

평균값인 빅-세타-노테이션과 최악의 경우인 빅-오-노테이션을 혼용해 표현하고 있으나 보통은 빅-오-노테이션이 보편적으로 사용된다.

 

---

 

리스트

 

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이 되고, 이 해쉬값에 따른 위치에 저장한다. 즉, 123은 3에, 84는 4에, 27은 7에  저장된다. 

 

해시함수에 의해 해시로 변환됨

그런데, input은 거의 무한대의 가변값인데 반해 hash는 고정값을 가지므로, 중복 hash값이 발생할 수 있다. 가령 위의 해시함수에 223이라는 값을 input으로 넣어도 123을 넣었을 때와 같은 hash값(3)을 얻게 된다. 이러한 현상을 해시 충돌(hash collision)이라고 하는데, 이때에는 동일한 해쉬값에 대해 LinkedList로 저장된다.

해시 충돌에 의해 88이 538 뒤에 저장되었다

 

---

 

트리셋은 이진 탐색 트리에 자료를 저장하는 트리구조의 셋이다. 트리셋은, 내부의 로직에 맞게 데이터를 정렬하여 저장한다. 이 말인즉슨, 1,2,3,4,5,6,7,8,9 의 순서대로 데이터를 트리셋에 삽입하면 아래와 같이 정렬되어 저장된다. 순서를 바꾸어서 7,1,4,2,6,8,9,5 의 순서대로 데이터의 트리셋에 삽입하면? 그래도 똑같이 아래와 같이 저장된다. 내부 정렬을 요구하는 자료형을 저장할 수 있는 세트이다.

 

Treeset: 이진 트리 구조

 

---

 

링크드 해시셋은 저장된 데이터에 앞 뒤 포인터 정보를 포함하여 저장하는 선형구조의 셋이다. 저장되는 순서를 보장하지만, 점유하는 메모리가 더 많다.

---

 

성능

 

	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) 페어 구조의 엔트리(Entry) 데이터를 저장할 때에 쓰이는 자료구조이다. Key 값이 유일값이라면 Value 값은 중복이 되어도 상관없다. 저장 순서는 Map의 구현 방법에 따라 유지될 수도 있고, 유지되지 않을 수도 있다.

 

---

 

 

구조

 

리스트, 셋, 큐 등의 인터페이스들이 Collection 인터페이스를 상속하는 것과 달리, 맵 인터페이스는 Collection 인터페이스를 상속하지 않는다. K-V 페어 형태를 가지는 맵의 구조가 다른 자료구조들과 다르기 때문이다. (엔트리라고 부른다.)

 

Collection 인터페이스를 상속하는 Set, List, Queue

 

---

 

성능

 

	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에 의해 원소들을 정렬하고 싶다면 선택

 

---

 

 

Reference

http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

Java Collections – Performance (Time Complexity)

https://javaconceptoftheday.com

Java Concept of the Day