Collections (List, Set, Queue, Map)

* Collection

> 가장 상위 interface

* List

> 순서있는 집합 처리를 위한 interface

> index 가 있어 위치를 지정하며 값을 찾을 수 있다

> 중복을 허용하며, List 를 이용하는 대표적인 클래스로 Vector 가 있다

* Vector

> 크기를 객체 생성시 지정할 필요없는 배열 클래스

> 동기화 기능이 포함되어 있다

> 내부적으로 배열 사용

: 저장할 공간이 없으면 보다 큰 새로운 배열을 생성하여 기존의 배열에 저장된 내용을 새로운 배열로 복사한다

> trimToSize()

: 객체가 존재하지 않는 할당된 공간을 GC를 통해 해제한다

> ensureCapacity(n)

: 할당된 공간이 최소 n 이 되도록 만든다. 이미 n 이상인 경우에는 아무런 동작을 하지 않는다

> setSize(n)

: 할당된 공간이 n 이 되도록 만든다. n보다 큰 경우에는 할당을 해제하고, 작은 경우에는 새로운 인스턴스를 생성한다

> clear()

: 모든 요소를 삭제한다

* Stack

> Vector 클래스를 상속 받아 구현됨

* ArrayList

> Vector 와 비슷한 동기화 처리가 되어있지 않다
> 내부적으로 배열 사용

: 저장할 공간이 없으면 보다 큰 새로운 배열을 생성하여 기존의 배열에 저장된 내용을 새로운 배열로 복사한다

> 데이터 추가 삭제에 불리하지만, 임의의 요소에 대한 접근성이 뛰어나다

* LinkedList

> ArrayList 와 비슷하지만 Queue interface 를 구현했기 때문에 FIFO 큐 작업을 수행

> Vector 와 ArrayList 에 비해 추가, 삭제 기능이 향상되었지만, 임의의 요소에 대한 접근성이 좋지 않다

* List 성능 비교

> Add (Sequential)

: (fast) ArrayList < Vector < LinkedList (Slow)

> Get (Sequential)

: (Fast) LinkedList (Peak(), poll()) < ArrayList < Vector < LinkedList (Slow)

: 동기화 때문에 Vector 가 ArrayList 보다 느리다

* List 의 Element 삭제

> 앞에서부터 삭제하면 자리 이동이 일어나기 때문에 원하는 결과를 얻지 못할 수 있다. 따라서, index를 뒤에서부터 확인하고 삭제 해야한다

---

* Set

> 순서가 없으며, 중복 허용하지 않는 집합 처리를 위한 interface

* SortedSet

> 오름차순을 갖는 Set interface

* HashSet

> HashMap 을 이용해서 구현

> Data 를 HashTable 에 담는 클래스로 순서없이 저장

> equals() 와 hashCode() 를 사용하여, 이미 포함되어 있는 객체인지 확인. 따라서, 2개의 메소드를 override 하여 사용하면 용도에 맞게 구현 가능

* TreeSet

> TreeMap 을 이용해서 구현

> Red-Black Tree 에 data 를 담음

> 값에 따라서 정렬된 순서로 저장됨 (즉, 저장 순서를 유지 하지 않음)

> Hash Set 보다 느리다

> 데이터를 담으면서 동시에 정렬할 때 유용

* LinkedHashSet

> HashTable 에 데이터를 담음

> 저장된 순서에 따라서 순서가 결정됨 (HashSet 과의 차이점)

* Set 성능 비교

> Add (Sequential)

: (Fast) HashSet = LinkedHashSet < TreeSet (Slow)
    - TreeSet 은 순서에 따라 삽입 동작을 수행

> Get (Sequential)

: (Fast) LinkedHashSet < HashSet < TreeSet (Slow)

> Get (Random)

: (Fast) HashSet = LinkedHashSet < TreeSet (Slow)

> 참고로, Size 설정 후 HashSet 의 add() 를 이용하는 경우가, 그렇지 않은 경우보다 빠르다

---

* Queue

> 여러 객체를 처리하기 전에 담아서 처리할 때 사용하기 위한 interface

* PriorityQueue

> Queue 에 추가된 순서와 상관없이 먼저 생성한 객체가 먼저 나온다

* BlockingQueue

> 크기가 지정되어 있는 Queue 에 공간이 더 이상 없을 때, 공간이 생길 때까지 대기하도록 만들어진 Queue 를 의미

* LinkedBlockingQueue

> 크기를 정할 수 있는 FIFO 기반의 Link Node 를 사용하는 Blocking Queue

* ArrayBlockingQueue

> 크기가 정해져 있는 FIFO 기반의 Blocking Queue

* PriorityBlockingQueue

> 크기가 정해져 있지 않고, 객체의 생성 순서에 따라 순서가 저장되는 Blocking Queue

* DelayQueue

> Queue 가 대기하는 시간을 지정하여 처리하도록 되어있는 Queue

* SynchronousQueue

> put() 을 호출하면 다른 Thread 에서 take() 를 호출할때 까지 대기하도록 되어있는 Queue

---

* Map

> Key, Value 쌍으로 구성된 객체의 집합을 처리하기 위한 interface

> 중복된 Value 는 허용하지만,  Key 는 허용하지 않는다

* SortedMap

> Key 를 오름차순으로 정렬하는 Map interface

* HashTable

> 동기화 기능이 포함되어 있다

> key, value 의 값으로 null 을 허용하지 않는다

> ArrayList 와 Vector 에 비해 검색 기능이 향상되었다

* HashMap

> HashTable 에 Data 를 담는다

> HashTable 과 달리 null 값을 허용하며, 동기화 기능이 없다

> 배열과 연결이 결합된 형태로, ArrayList 와 Vector 에 비해 검색 기능이 향상되었으며 추가, 삭제, 검색, 접근성이 모두 뛰어나다

* TreeMap

> Red-Black Tree 에 Data 를 담는다

: LinkedList 에 비해 검색, 범위 검색, 정렬기능이 향상되었다

> TreeSet 과 달리 Key 에 의해 순서가 정해지며, 정렬이 필요한 경우에 사용한다

> 연결 기반의 구조로 범위 검색에 적합하며, 검색 성능은 HashMap 보다 느리다

* LinkedHashMap

> HashMap 과 다른 점은 Doubly-linked List 를 이용해 Data 담는다

: (HashMap 과 Hashtable 에 비해) 순서 유지 기능이 향상되었다

* Map 성능 비교

> Add

: 모두 비슷하다

> Get

: (Fast) HashMap (Seq) = HashMap (Random) = LinkedHashMap (Seq) = LinkedHashMap (Random) < HashTable (Seq) = HashTable (Random)

  < TreeMap (Seq) < TreeMap (Random) (Slow)

---

* Collections 클래스의 동기화

> 자체적으로 아래와 같은 동기화 메서드를 제공한다

Collections.synchronizedList(new ArrayList<>());

Collections.synchronizedMap(new HashMap<>());

Collections.synchronizedSet(new HashSet<>());

Collections.synchronizedCollection(new ArrayList<>());

* Array vs LinkedList

> Array

: 장점

- 구조가 간단하다

- 사용하기 쉽다

- Access time 이 빠르다

: 단점

- Size 변경이 불가하다

- 비순차적인 데이터 추가, 삭제가 느리다

> LinkedList

: 장점

- 비순차적인 데이터 추가, 삭제가 빠르다

: 단점

- Access time 이 느리다 (Data가 많을수록 접근성이 떨어진다)

> 성능 비교

: Sequential Add & Delete

- (Fast) ArrayList < LinkedList (Slow)

: Random Add & Delete

- (Fast) LinkedList < ArrayList (Slow)

* Iterator

> list.iterator() 를 통해 읽어오는 결과는 저장 순서와 동일하다

> map.keyset().iterator() 를 통해 읽어오는 결과는 저장 순서와 다르다
    : Set 은 순서를 유지하지 않기 때문이다

* ListIterator

> 양방향으로 이동 가능

* Enumeration

> Iterator 의 구 버전 (Collection Framework 가 만들어지기 이전에 사용)