[JAVA] 컬렉션 프레임워크

• 컬렉션(collection): 여러 객체 모아놓은 것 → R, W, 검색, 정렬
• 프레임워크(framework): 정해진 틀에 맞춰 프로그래밍 하는 것
  • 표준화, 정형화된 체계적인 프로그래밍 방식
  • 비슷하니까 이해도 잘 되고 작업 생산성 높음
  • 유지 보수하기도 좋음
  • cf. library - 다른 사람들이 만들어 놓은 기능 모아놓은 것

 

자료 구조라는 것은 데이터들의 구조를 나타낸 것으로 어떻게 하면 데이터를 효율적으로 읽고 저장할 수 있을까를 고민한 것이다. 결국 배열이라는 일체형과 연결형의 모습으로 정리할 수 있다. 트리는 연결형에서 파생된 모습이고 맵은 배열과 연결형을 조합하여 만든 구조이다. 그렇기에 자료구조는 배열이라는 일체형과 연결형이라는 두 가지로 크게 나눌 수 있다. 

배열	연결형
데이터 접근 시간이 짧다	링크를 따라가며 하나하나 탐색해야 한다
크기 변경을 할 수 없다	크기 변경을 할 수 있다
데이터를 중간에 추가/삭제할 시 이동 연산이 크다  (끝은 빠르다)	.

 

배열과 연결형 중 어느 것이 절대적으로 좋다, 나쁘다 하는 건 없다. 현재 상황을 살펴보고 어떤 것이 적합할 지 생각하면 된다.  그리고 컬렉션 프레임워크의 핵심 인터페이스는 다음과 같이 분류할 수 있다. 

List	순서 O, 중복 O	ArrayList(신), LinkedList, Vector(구)
Set	순서 X, 중복 X	HashSet, TreeSet
Map	(K, V) 쌍, 순서 X	HashMap, TreeMap

• List와 Set을 묶어 Collection 인터페이스를 만들었다. (Collections는 유틸 클래스다.)
• Set의 경우 중복 검사를 할 때 값을 있는지 없는지 다 비교해야 하기 때문에 O(n) 시간 복잡도를 가진다. 
• Map의 key-value 쌍을 Entry라고 한다.
• HashMap은 대용량 데이터에 유리하고 TreeMap은 정렬과 범위 검색에 적합하다. 
• size는 저장된 객체의 개수, length(capacity)는 배열의 길이를 나타낸다. 

list.add(1); >> list.add(new Integer(1));

// remove(***) index와 Object 모두 가능
list.remove(1); // index가 1인 객체 삭제
list.remove(new Integer(1)); // 객체가 1인 것 삭제

 

성능을 표시하는 Big-O 표기법은 다음과 같다. 

• O(1) - 상수
• O(n) - for 문 x 1개 ≫ O(log n)으로 줄이도록
• O(n^2) - for 문 x 2개, 정렬 ≫ O(nlog n)으로 줄이도록

데이터량이 증가해도 그에 대한 성능이 일정하게 나오면 좋겠지만 현실적으로 연산량이 느리게 증가하도록 하는 것이 최선이다. 그래서 O(n)을 O(log n)으로, O(n^2)을 O(nlog n)으로 줄이는 것이 좋다. 그림에서처럼 기울기를 넓게, 완만하게 만들어야 한다. 

• 가능하면 참조변수의 타입도 조상으로 좁혀주는 것이 좋다. (추상화)
• 컬렉션들마다 구조가 다 달라서 읽어오는 방법도 다 다르다. 이것을 표준화한 것이 Iterator다.
  • Iterator는 일회용으로 한번 읽고 나면 포인터가 끝을 가리켜 다시 읽으려면 다시 생성해야 한다.
  • public Iterator<T> iterator() { ... }  컬렉션 인터페이스에 정의되어 있다. 하지만 Map은 컬렉션 인터페이스가 아니기 때문에 keySet(), entrySet(), values()의 반환값으로 컬렉션을 받고 거기에 iterator() 메서드를 활용한다. 
  • hasNext(), next()
• 탐색은 순차탐색, 이진탐색으로 나눌 수 있다.
• 트리는 전위, 중위, 후위, 레벨 순회 4가지 방법으로 탐색할 수 있고 중위 탐색은 오름차순으로 정렬된다. 
• Properties는 내부적으로 HashTable을 사용하고 <String, String> 쌍을 가진다. 파일을 읽고 쓰는 데 유용하다.

Collections