컬렉션 프레임워크

 

List

데이터의 집합인데, 순서가 있다. 순서가 있으므로 데이터를 중복해서 넣을 수도 있다.

ArrayList

요소를 저장하는데 배열을 사용하는 리스트. 순차적으로 요소를 처리해야 할 일이 있을 경우에 좋다.
요소를 계속 넣어서 배열의 길이를 넘어가게 되면, 리스트 내부적으로 길이가 늘어난 배열을 만든 뒤에 요소를 다시 담는다. 반대의 경우에도 길이를 줄인 배열을 만들어서 다시 담는다.
배열의 중간에서 요소를 넣고 빼는 경우 그 뒤에 있는 요소들의 위치까지 전부 바꿔야 하기 때문에 성능면에서 나쁘다.
멀티스레드 환경에서는 동기화에 신경써야 한다.

LinkedList

노드를 사용하는 리스트. 노드는 [이전 요소로 가는 링크] - [데이터] - [다음 요소로 가는 링크] 로 구성되어 있다.
그래서 마치 열차 같은 구조를 띄게 되는데, 이런 특징으로 인해 열차 칸을 더하는 것처럼 리스트의 앞이나 뒤, 혹은 중간에 다른 요소를 추가하고 빼는 것이 배열 리스트보다 훨씬 빠르게 이루어진다.
열차 같다고 말은 했지만, 요소들이 열차처럼 올곧게 정렬되어 있지는 않다. 어떤 건 서울에 있고, 어떤 건 목포, 어떤 건 부산에 있는 식이다(포인터와 주소에 대해 알면 좋다!). 그래서 순차적으로 요소를 처리하는 것에는 약하다.

Vector

멀티스레드에 안정적인 ArrayList. 초창기 때부터 존재했던 클래스다. C++ STL에서도 똑같은 게 있었던 것 같은데...
스레드 안정적이라는 것만 빼면 ArrayList가 훨씬 낫다는 듯.

Set

리스트와 달리 순서가 없다. 정말 마구잡이로 넣는 느낌. 중복되는 값을 넣어도 추가되지 않는다.

HashSet

 해시 테이블을 사용하는 셋. 그렇기에 정말 정말 빠르다. 요소를 넣으면 해당 요소에 대한 해시코드를 만들고, 내부 배열(이것을 버킷이라고 한다)에서 코드가 가리키는 곳에 요소를 저장하거나 불러온다. 순차적으로 검색하는 과정조차도 생략되므로 시간 복잡도가 O(1)이다. 어마어마하게 빠른 것.
 null 도 넣을 수 있다.
 그럼 두 요소의 해시코드가 똑같으면 중복으로 처리되는건가요? 내부 값이 달라도???
 해시코드가 똑같아서 요소가 들어갈 자리에 이미 다른 요소가 있는 경우, 완전한 중복인지 확인하기 위해 equals() 메소드가 사용된다. 해당 메소드로 두 요소가 완전히 같지는 않다고 판별되는 경우, 내부 배열에서 남는 자리를 찾아 그곳에 대신 넣게 된다. 이를 선형 탐색이라고 한다.

TreeSet

 이진 탐색 트리(red-black tree) 구조를 따르는 셋. 트리라는 자료구조의 특성 상 순서가 정렬되게 된다.
 셋은 순서 의미가 없는 거 아니었나요?
 이진 탐색 트리라는 구조를 사용해 셋을 구현하게 되면서 순서가 정렬되는 것이 덤으로 붙은 느낌. 아무튼 셋의 인터페이스를 구현했으므로 셋이라고 불러야 한다. 중복을 허용할 수 없기도 하고.
 아무튼 트리 구조를 띄어 순서가 생기다보니 first, last, lower, higher 같은 메소드를 사용해 트리의 특정 위치에 있는 데이터를 읽거나, 특정 값보다 적거나 많은 데이터를 읽을 수 있다.
 요소의 높고 낮음을 알아야하므로, null은 넣을 수 없다.
 HashSet보다 못할 뿐, 검색은 이쪽도 빠른 편이다.
 

Map

 키-값 쌍으로 이루어진다. 알맞은 키를 입력하면 그에 맞는 값을 내놓는 식이다. 셋과 비슷한데 값을 입력하면 전혀 다른 게 튀어나온다는 느낌...?

HashMap

 HashSet과 동일하게 해시 테이블을 사용하는 맵. 똑같이 해시코드 중복이 발생할 가능성이 있는데, HashSet과 달리 여기서는 선형 탐색(개방주소법)이 아닌 체이닝을 사용한다.
 선형 탐색 -> 배열의 인덱스를 고정된 수만큼 건너뛰면서 빈 자리를 찾아 넣는다.
 체이닝 -> 배열에 바로 요소를 넣지 않고, 연결 리스트를 넣은 뒤 그곳에다 요소를 나열한다.
 체이닝 기법으로 연결 리스트를 만들었는데도 노드가 계속해서 많아지는 경우가 있다. 이 땐 검색에 드는 시간을 최적화하기 위해 트리로 변경된다.

TreeMap

 TreeSet과 동일하게 이진 탐색 트리를 사용하는 맵. 특징조차도 똑같으므로, 키의 순서가 중요할 경우에 사용한다.