컬렉션이란?(Collection)[List, set, map]

 

* Collection?

사전적 의미 : 요소를 수집해서 저장하는 것.

 

자바에서 컬렉션 프레임워크란,

다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미한다.

즉, 데이터를 저장하는 자료구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해놓은 것.

 

* 자바에서의 자료구조 유형은 다음과 같다.
- 순서가 있는 목록인 List형
- 순서가 중요하지 않은 목록인 Set형
- 먼저 들어온 것이 먼저 나가는 Queue형
- KEY-VALUE의 형태로 저장되는 Map형

자바 컬렉션은 객체를 수집해서 저장하는 역할을 한다.

자바 컬렉션 프레임워크는 몇 가지 인터페이스를 통해 다양한 컬렉션을 이용할 수 있도록 한다.

그중 크게 3가지 타입으로 나누어 핵심이 되는 주요 인터페이스를 정의하였다.

 

• List 인터페이스
• Set 인터페이스
• Map 인터페이스

인터페이스로 가능한 컬렉션 클래스를 나타내는 그림

 

인터페이스	특징
List	순서가 있는 데이터의 집합, 데이터의 중복을 허용한다. ex) 대기자 명단 구현클래스 : ArrayList, LinkedList, Stack, Vector 등
Set	순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않는다.  예) 양의 정수집합, 소수의 집합  구현클래스 : HashSet, TreeSet 등
Map	키(Key)와 값(Value)의 쌍(Pair)으로 이루어진 데이터의 집합  순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다.  예) 우편번호, 지역번호(전화번호)  구현클래스 : HashMap, TreeMap, Hashtable, Properties 등

List 인터페이스

순서가 있는 목록인 List 인터페이스는 Collection의 다른 인터페이스들과 가장 큰 차이는 배열처럼 순서가 있다는 것이다.

List 컬렉션은 객체를 일렬로 늘어놓은 구조를 가지고 있다. 객체를 인덱스로 관리하기 때문에 객체를 저장하면

자동 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있는 기능을 제공한다.

List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 참조한다.

즉, 인덱스마다 객체의 번지주소가 들어있다. 동일한 객체를 중복 저장할 수 있는데, 이 경우 동일한 번지가 참조되고

null이 저장될 경우에는 해당 인덱스는 객체를 참조하지 않는다.

다음 List의 대표적인 구현클래스 ArrayList와 비교대상 Vector, LinkedList를 보자.

우선 ArrayList와 Vector 클래스는 거의 동일하지만

ArrayList는 Thread safe 하지 않고, Vector는 Thread safe 하다

(Thread safe하지 않다는 것은 객체에 여러 명이 달려들어 값을 변경하려고 하면 문제가 발생할 수 있다는 것)

Vector

List<E> list = new Vector<E>();

JDK.1.0부터 사용해온 ArrayList와 같은 동작을 수행하는 클래스이다. 하지만 현재에는 기존 코드와의 호환성을 위해서만 남아있으므로, Vector 클래스보다는 ArrayList 클래스를 사용하는 것이 좋다.

특히 쓰레드의 개수와 상관없이 동기화(synchronize) 처리를 하므로 Thread-safe 하지만 싱글쓰레드 환경이어도 동기화처리를 하므로 성능이 좋지 않아 쓰이지 않는다.

 

ArrayList와 다른점은 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드가 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있다.

 

ArrayList

List<String> list = new ArrayList<String>(30);

ArrayList는 List 인터페이스의 구현 클래스로, 컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스일 것이다.

ArrayList에 객체를 추가하면 객체가 인덱스로 관리된다. 일반배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서는 유사하지만, 큰차이점을 가지고 있다.

ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장하게 되는데 배열에 더 이상 저장할 공간이 없으면

보다 큰 새로운 배열을 생성해 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장한다.

 

즉, 배열은 생성할 때 크기가 고정되고 사용 중에 크기를 변경할 수 없지만 ArrayList는 저장 용량(capacity)을 초과한 객체들이 들어오면 자동적으로 저장 용량이 늘어난다는 것이다. 

ArrayList에서 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다는 것을 보여준다.

ArrayList는 Vector와 같은 추가/삭제 기능을 가지고 있고 자동 동기화 처리가 되지 않기 때문에

빠르게 처리가 가능하다.

대신 내부적으로 배열(array) 구조를 이용하기때문에 데이터 추가/제거를 배열을 복사하는 방법으로 처리하기 때문에 추가/제거가 많을 경우 오버헤드가 많이 발생함. 특히 중간에 삽입될 때 데이터들이 뒤로 밀리면서 성능저하가 큼.

대신! 인덱스를 가지로 있어서 조회할 때 한 번에 접근이 가능하기 때문에 대용량 데이터를 한 번에 가져와서 여러번 참조해 사용할 때 최상의 성능을 내는 객체다. (+크기 조절이 마음대로..)

Collections.synchronizedList, Collections.synchronizedMap, Collections.synchronizedCollection 등으로 동기화처리가 되는 컬렉션 생성하면 멀티쓰레드환경에서 쓸 수 있음.

 

LinkedList

LinkedList는 List 구현 클래스이므로 ArrayList와 사용방법은 똑같지만 내부 구조는 완전 다르다.

ArrayList는 내부 배열 객체를 저장해서 인덱스로 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.

 

연결된 자료의 정보만 담고 있기 때문에 중간 노드에 추가/삭제시 다른 데이터의 위치를 변경시킬 필요없이 간단하게 추가/삭제할 수 있다.

따라서 추가/삭제가 빈번하게 일어나는 대용량 데이터 처리가 필요할 때 사용하면 성능이 좋다.

대신 어디에 어떤 데이터가 있는지는 첫 노드부터 정보를 타고가면서 찾아야 하므로 검색에 있어서 성능이 좋지 않다. (ArrayList와 장단점이 반대다.)

스택, 큐, 양방향 큐등을 만들 때 사용한다.

* Question
-> 랜덤액세스할 때 ArrayList와 LinkedList 중에 어떤 것이 유리한가?

이에 대답은 ArrayList다. 랜덤 액세스 말 그대로 임의의 값에 접근하는데 ArrayList는 인덱스(0,1,2,...)로 한 번에 접근하기 때문에 유리하다. 반면 노드를 head나 tail부터 이동하며 접근하는 LinkedList는 성능상 불리하다.

 

-> 만약 추가/삭제도 많고 조회도 많으면 어떤 자료를 써야하나요?
확실한 정답은 모르겠지만 둘 중에 굳이 고르자면 ArrayList를 고른다.

또는 다른 자료구조 (ex.HashMap)을 사용하는 것이다.

첫 번째 근거는 LinkedList가 삽입/삭제에서 이 점을 갖는다고 했는데 결국은 어떤 값을 삭제할 때 존재하는지 확인해야한다는 것이다.

즉, 조회를 해야 삭제가 가능한 것이 아닌가 하는 의문이다. 정확하게 소스를 까서 보면 알 수 있겠지만 정확한 데이터는 아니니까 오해는 안했으면 한다.

 

ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
 
// ArrayList add
long startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
    arrayList.add(i); 
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);
 
// LinkedList add
startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);
 
// ArrayList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);
 
// LinkedList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
    linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);
// ArrayList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
    arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);
 
// LinkedList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
    linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

위의 테스트소스 출처는 https://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/ 이다.

결과는 아래와 같다! (openjdk11, 메모리8GB, i5-6200U, win10 기준)

나노초로 찍었으니까 밀리로 환산하면 아래와 같다.

ArrayList add = 약 6ms , LinkedList add = 약 3ms

ArrayList get = 약 0.01ms , LinkedList get = 약 157ms

ArrayList remove = 약 135ms, LinkedList remove = 약 126ms

결과적으로 조회에서는 ArrayList가 압도하지만 취약하다던 add, remove에서는 크게 차이나지 않는다!

ArrayList와 LinkedList의 차이

ArrayList 객체를 추가하면 인덱스 0부터 차례대로 저장된다. ArrayList에서 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다. 마찬가지로 특정 인덱스에 객체를 삽입하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 밀려난다. 

 

따라서 빈번한 객체 삭제와 삽입이 일어나는 곳에는 ArrayList를 사용하는 것이 바람직하지 않다. 이런 경우라면 LinkedList를 사용하는 것이 좋다. 그러나 인덱스 검색이나, 맨 마지막에 객체를 추가하는 경우에는 ArrayList가 더 좋은 성능을 발휘한다. ,즉 LinkedList는 중간에 데이터를 추가 하거나 삭제할때 ArrayList보다 빠르다. 그러나 데이터를 순차적으로 추가삭제 검색하는 것은 ArrayList가 더 빠르다.

---

정리

위의 Vector, ArrayList, LinkedList는 List인터페이스의 구현 클래스다.

공통점 : 순서가 있는 데이터 집합이고 데이터 중복을 허용한다.

Vector : 과거에 사용하던 대용량 처리 컬렉션, 잘 사용 안하고 동기화처리가 자동적으로 내부에서 일어나므로 비교적 성능이 좋지 않고 무겁다.

ArrayList : 배열의 복사에 의한 데이터 저장처리를 내부적으로 수행하므로 많은 데이터의 추가/삭제시에는 성능이 떨어지나 각 데이터에 대한 인덱스를 가지고 있기 때문에 조회(검색)에 있어서 빠르다. (성능이 좋다)

특히 순차 접근이 필요할 때 인덱스가 있으므로 유용하다!

LinkedList : 다음 자료의 위치 정보를 가지며, 인덱스는 가지고 있지 않다. 데이터의 추가/삭제는 다음 데이터 위치정보만 수정하면 되므로 많은 정보의 추가/삭제가 일어날 때 유용하다. 대신 데이터 조회(검색)시 처음 자료부터 찾아 나가야 하므로 느려지는 단점이 있다.

---

Set 인터페이스

순서가 없는 데이터 집합이고 데이터 중복을 허용하지 않는다.

Set은 ArrayList처럼 인덱스가 따로 존재하지 않아 iterator(반복자)를 사용해야한다.

LinkedList도 순서는 있지만 인덱스가 없으므로 iterator를 사용해야 함.

Set<String> set = ...;
 
Iterator<String> iterator = set.iterator();

Set 컬렉션에는 HashSet, LinkedHashSet, TreeSet등이 있는데, 다음은 Set 컬렉션에 공통적으로 사용 가능한 Set 인터페이스의 메소드들이다.

 

* HashSet 

HashSet은 Set 인터페이스의 구현클래스이다. HashSet을 생성하기 위해서는 다음과 같이 기본생성자를 

호출하면 된다.

Set<E> set = new HashSet<E>();

- 빠른 접근속도를 가지고 있음 단, 순서를 알 수 없음

- 동일한 객체는 중복 저장하지 않는다.

- 객체를 저장하기 전에 객체의 hash Code() 메소드를 호출하여 해시코드를 얻어낸다.

 

문자열을 HashSet에 저장할 경우, 깊은 문자열을 갖는 String 객체는 동등한 객체로 간주되고 다른 문자열을 갖는 String 객체는 다른 객체로 간주되는데, 그 이유는 String 클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열일 경우 hashCode()의 리턴값을 같게, equals()의 리턴값은 true가 나오도록 오버라이딩이 되있기 때문이다. 

 

* LinkedHashSet : 추가된 순서대로 접근 가능

* TreeSet : 정렬방법을 지정할 수 있음

 

Map 인터페이스

Map 컬렉션은 키(key)와 값(value) 쌍(pair) 으로 구성된 Entry 객체를 저장하는 구조를 가지고 있다. 여기서 키와 값은 모두 객체이다. 키는 중복 저장될 수 없지만 값은 중복 저장될 수 있다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다.

 

 

* Map의 주요 특징

- 모든 데이터는 키와 값이 존재한다.
- 키가 없이 값만 저장할 수는 없다.
- 값이 없이 키만 저장할 수도 없다.
- 키는 해당 Map에서 고유해야만 한다.
- 값은 Map에서 중복되어도 전혀 상관 없다.
- 데이터 추가 순서는 중요하지 않다(데이터를 저장한 순서대로 결과가 출력되지 않는다).

 

Map 컬렉션에는 HashMap, Hashtable, LinkedHashMap, Properties, TreeMap 등이 있다. 다음 대표적인 HashMap을 보자

1. HashMap

HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션이다. HashMap의 키로 사용할 객체는 hashCode()와 equals() 메소드를 재정의해서 동등 객체가 될 조건을 정해야 한다. 동등 객체, 즉 동일한 키가 될 조건은 hashCode()의 리턴값이 같아야 하고, equals() 메소드가 true를 리턴해야 한다. 주로 키타입은 String을 많이 사용하는데, String은 문자열이 같을 경우 동등 객체가 될 수 있도록 hashCode()와 equals() 메소드가 재정의되어 있다.

대부분 HashMap 객체를 생성할 때에는 매개 변수가 없는 생성자를 사용한다. 하지만 HashMap에 담을 데이터의 개수가 많은 경우에는 초기 크기를 지정해주는 것을 권장한다.

HashMap<String,String> map=new HashMap<String,String>();

 

2. TreeMap

TreeMap은 이진 트리를 기반으로 한 Map 컬렉션이다. TreeSet 과의 차이점은 키와 값이 저장된 MapEntry를 저장한다는 점이다. 
TreeMap 클래스는 키와 값을 저장하는 동시에 키를 정렬한다. 정렬되는 순서는 숫자 > 알파벳 대문자 > 알파벳 소문자 > 한글 순이다. 따라서, 정렬을 해야 할 필요가 있다면 HashMap 보다는 TreeMap을 사용하는 것이 더 유리하다.

TreeMap<String, String> treeMap = new TreeMap<String, String>();

참고자료

https://steady-snail.tistory.com/74

http://blog.breakingthat.com/2018/05/07/java-collection-%EA%B0%9C%EC%9A%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/

https://jeong-pro.tistory.com/18