자바에서 알고리즘 문제풀때 꼭 알아야하는 프레임워크인 듯. 확실히 파이썬하고 많이 다르다. 다른 점이 재밌기도 하다.

프레임워크의 정의

사용방법을 미리 정해놓은 라이브러리

컬렉션의 정의

객체를 수집해서 저장하는 역할을 해준다.

컬렉션 프레임워크는 배열의 문제점을 보완한 프레임워크이다. 배열의 문제점은 다음과 같다.

배열의 문제점

저장할 수 있는 객체 수가 배열을 생성할 때 결정되기 때문에 불특정 다수의 객체를 저장하기에는 불안정하다.

객체를 삭제했을 때 해당 인덱스가 비게되어 낱알이 듬성듬성 빠진 옥수수가 될 수 있다. 그래서 어디가 비어있는지 확인하는 코드가 있어야 한다.

컬렉션 프레임워크의 주요 인터페이스로는 List, Set, Map이 있다.

ArrayList, Vector, LinkedList는 List interface를 구현한 Class이다.

HashSet, TreeSet, LinkedHashSet은 Set interface를 구현한 Class이다.

HashMap, HashTable, TreeMap, Properties는 Map interface를 구현한 Class이다.

객체를 일렬로 늘어놓은 구조를 가지고 있다.

객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있는 기능을 제공한다.

객체 자체를 저장하는 것이 아니라 객체의 번지를 참조하기 때문에 종일한 객체를 중복저장할 수 있는데, 이 경우 동일한 번지가 참조된다. 그리고, null 도 저장 가능한데, 이 경우 해당 인덱스는 객체를 참조하지 않는다.

*E 라는 타입 파라미터는 List 인터페이스가 제네릭 타입이기 때문이다.

ArrayList는 List interface의 구현 class로, 객체를 추가하면 객체가 인덱스로 관리된다.

배열과는 달리 저장용량을 초과한 객체들이 들어오면 자동적으로 저장용량이 늘어난다.

ArrayList 생성

// 저장할 객체 타입을 타입 파라미터로 표기하고, 기본 생성자 호출
List<String> list = ArrayList<String>();

// 기본적으로 내부에 객체를 10개 저장할 수 있는 초기 용량이 있지만,
// 처음부터 초기용량을 정하고 싶다면, 용량 크기를 매개값으로 적어준다.
List<String> list = ArrayList<String>(30);

객체를 추가(add)시 인덱스 0부터 차례대로 저장된다.

특정 인덱스의 객체를 제거(remove)하면 바로 뒤 인덱스부터 마지막 인덱스까지 1씩 당겨진다.

특정 인덱스에 객체를 삽입(set)하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 밀려난다.

고정된 객체들로 구성된 List 생성하기

List<T> list = Arrays.asList(T... a);

List<String> list = Arrays.asList("a", "b", "c");
List<Integer> list = Arrays.asList(1, 2, 3);

Vector 생성

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

Vector을 사용하면 *스레드가 안전(Thread Safe)*하게할 수 있다. 즉, 동기화된 메소드로 구성되어있어서 멀티스레드가 동시에 이 메소드를 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드를 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제 할 수 있다.

인접 참조를 링크해서 체인처럼 관리한다.

특정 인덱스의 객체를 제거하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 이는 특정 인덱스에 객체를 삽입할때도 마찬가지다.

LinkedList 생성

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

저장 순서가 유지되지 않는다.

객체를 중복해서 저장할 수 없다. (하나의 null만 저장할 수 있다.)

*인덱스로 관리하지 않아서 인덱스를 매개값으로 갖는 메소드가 없다.

Set 생성

Set<String> set = ...;

// Set컬렉션은 인덱스로 가져오는 반복자가 없어서
// 전체 객체를 대상으로 한번씩 반복해서 가져오는 반복자를 제공
Iterator<String> iterator = set.iterator();

Iterator 인터페이스를 구현한 객체에서 사용할 수 있는 메소드들이다.

Set을 looping하는 여러가지 방법

Set<String> set = new HashSet<String>();
set.add("A");
set.add("B");
set.add("C");
Iterator<String> iterator = set.iterator();

// Iterator을 사용하고 looping
while (iterator.hasNext()) { // true 라면 looping
    String str = iterator.next();
    System.out.println(str);
}

// Iterator을 사용하지 않고 looping
for(String str:set) {
    System.out.println(str);
}

Set interface의 구현 class이다

Hashset 생성

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

HashCode가 공일한 객체를 중복 저장하지 않는 내부 동작방식

(1)HashSet은 객체를 저장하기 이전에 먼저 객체의 hashCode() 메소드를 호출해서 해시코드를 얻는다.

(2)이미 저장되어있는 객체들의 해시코드와 비교한다. 만약 동일한 해시코드가 있다면 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.

key와 value로 구성된 entry객체를 저장하는 구조이다. 여기서 key와 value는 모두 객체이다. key는 중복될 수 없지만, value는 중복될 수 있다. 만약 기존에 저장된 key와 동일한 key로 value를 저장하면 기존의 value는 없어지고, 새로운 value로 대체된다.

*키로 객체들을 관리하기 때문에 키를 매개값으로 갖는 메소드가 많다.

객체를 찾아오는 3가지 방법

// (1) 키를 알고있는 경우, get() 메소드로 간단하게 객체를 찾아오기
Map<String, Integer> map = ...;
map.put("A", 1);
int score = map.get("A");

// (2) KeySet() 메소드로 모든 키를 Set 컬렉션으로 얻은 다음, 
// 반복자를 통해 키를 하나씩 얻고 get() 메소드를 통해 값을 얻기
Map<K, V> map = ...;
Set<K> KeySet = map.KeySet();
Iterator<K> keyIterator = KeySet.iterator();
while (keyIterator.hasNext()) {
  K key = keyIterator.next();
  V value = map.get(key);
}

// (3) entrySet()메소드로 모든 Map.Entry 를 Set컬렉션으로 얻은 다음, 
// 반복자를 통해 Map.Entry를 하나씩 얻고 getKey()와 getValue() 메소드를 이용해 키와 값을 얻기
Set<Map.Entry<K,V>> entrySet = map.entrySet();
Iterator<Map.Entry<K,V>> entryIterator = entrySet.iterator();
while(entryIterator.hasNext()) {
  Map.Entry<K,V> entry = entryIterator.next();
  K key = entry.getKey();
  V value = entry.getValue();
}

HashMap 생성

// 키 타입과 값 타입을 파라미터로 주고 기본 생성자로 호출하면된다.
Map<K, V> map = new HashMap<K, V>();

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

*키와 값의 타입은 기본 타입(byte, short, int, float, double, boolean, char)을 사용할 수 없고, 클래스 및 인터페이스 타입만 가능

*Vector와 유사하다.

Hashtable을 사용하면 *스레드가 안전(Thread Safe)*하게할 수 있다. 즉, 동기화된 메소드로 구성되어있어서 멀티스레드가 동시에 이 메소드를 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드를 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제 할 수 있다.

Hashtable 생성

// 키 타입과 값 타입을 파라미터로 주고 기본 생성자로 호출하면된다.
Map<K, V> map = new Hashtable<K, V>();

Map<String, Integer> map = new Hashtable<String, Integer>();

Properties는 Hashtable의 하위 클래스이기 때문에 Hashtable의 모든 특징을 그대로 가지고 있다.

Properties는 키와 값을 String만 지정 가능하다.

Set - TreeSet

Map - TreeMap

이진트리를 이용해서 계층적구조를 가지면서 객체에 저장한다.

후입선출 - Stack

선입선출 - Queue

나중에 넣은 객체가 먼저 빠져나가는 자료구조

Stack 생성

Stack<E> stack = new Stack<E>();

Stack<String> stack = new Stack<>();

stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");

System.out.println(stack); // [A, B, C, D]
String out = stack.pop();
System.out.println(out); // D
String last = stack.peek();
System.out.println(last); // C
System.out.println(stack); // [A, B, C]

먼저 넣은 객체가 먼저 빠져나가는 자료구조

Stack 생성

Queue<E> queue = new LinkedList<E>();

*LinkedList 타입 객체를 Queue 인터페이스 타입으로 변환

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
queue.offer("D");

System.out.println(queue); // [A, B, C, D]
String outQ = queue.poll();
System.out.println(outQ); // A
String frontQ = queue.peek();
System.out.println(frontQ); // B
System.out.println(queue); // [B, C, D]

Vector와 Hashtable은 동기화된 메소드로 구성되어있어서 멀티쓰레드 환경에서도 안전하게 요소를 처리할 수 있지만 ArrayList, HashSet, HashMap의 경우에는 그렇지 않다.

이러한 점을 Collection의 synchronizedXXX()메소드를 사용해서 맵핑하면 동기화된 컬렉션을 리턴한다.