[JAVA] Collections Framework란?

자바 컬랙션 프레임워크는 list, set, map, stack 그리고 queue와 같은 collection 사용을 돕기 위한 인터페이스와 클래스들로 구성되어 있다.

1. java Collections Hierarchy

• Collection

  Collection 인터페이스는 가장 상위 계층이며, 컬랙션 클래스들이 필요한 기능을 제공한다.

  또한 for-each loop문을 사용하기 위해 Iterable 인터페이스를 확장합니다.

• List

  리스트는 정렬된 요소 집합을 나타낸다. 여기서 정렬이란 sort를 의미하는 것이 아닌 개발자에 의해 다뤄진 순서를 의미한다. 리스트를 통해 각각의 요소에 대해 인덱스를 통해 접근이 가능하다.

  리스트 인터페이스를 구현한 주요 클래스로는 ArrayList, CopyOnWriteArrayList, LinkedList, Stack, Vector 등이 있다.

• Set

  set는 중복된 값을 갖을 수 없습니다. 또한 set 인터페이스는 예측하는 순서대로 값을 반환하는것을 보장하지 않습니다. 즉 set에 추가되는 값이 일정한 순서를 갖지 않습니다.

  그럼 set은 내부적으로 무슨 순서를 사용해서 저장되는가? (natural ordering?)

  주요 클래스로는ConcurrentSkipListSet, CopyOnWriteArraySet,EnumSet, HashSet, LinkedHashSet and TreeSet.

• Map

  Map 인터페이스는 데이터를 key-value 형태로 저장한다. key 값은 변할 수 없고 중복된 값을 갖을 수 없다. 또한 각각의 키는 하나의 값을 갖을 수 있다. keySet, valueSet, key-value Set을 set 형태로 제공한다. TreeMap의 경우는 순서에 대해 보장을 하지만 HashMap과 같은 클래스들은 보장하지 않는다.

  TreeMap이 순서를 보장하는 방법은?, TreeMap, HashMap 데이터 저장 방법은?

• Stack

  LIFO 형태의 자료 구조이다.

• Queue

  두개의 스택을 이용해 queue를 구현하는 방법은?

  큐는 일반적으로 FIFO 형태를 갖는다. Priority Queue는 이러한 경우의 예외인데 이것은 Comparator나 natural ordering 에 의해 요소들을 순서대로 정렬하기 때문이다.

  In general, queues do not support blocking insertion or retrieval operations. Blocking queue implementations classes implement BlockingQueue interface.

• Dequeue

  양끝에 종료지점이 있는 queue이다. insertion과 removal을 양쪽 끝에서 사용할 수 있다. 따라서 FIFO의 queue와 LIFO의 stack처럼 사용할 수 있다.

2. ArrayList

List 인터페이스의 구현 클래스이다.

사용자가 추가한 순서대로 순서를 유지, 인덱스를 사용해서 접근 가능, 길이 조절이 가능함, 동기화를 제공하지 않는다. synchronized 키워드를 사용하거나 Vector를 사용해서 동기화 문제를 해결해야한다. 중복 허용

3. LinkedList

List와 Deque를 구현한 클래스이다. 따라서 queue, deque, stack으로 사용이 가능하다.

추가된 요소들의 순서를 유지한다. 동기화를 지원하지 않기 때문에 외부적으로 처리가 필요하다.

ListIterator을 사용해 요소들에 접근이 가능하다.

LinkedList는 ArrayList에 비해 add 와 remove 는 빠르지만 get은 느리다. 또한 메모리 오버헤드가 더 크다. ArrayList는 각각의 인덱스는 실제 객체만 갖고 있으면 되지만 LinkedList는 전후 node에 대한 주소를 갖고 있어야하기 때문이다.

4. HashMap

Map을 구현한 객체이다. key-value 쌍을 갖고 데이터를 저장한다.

HashMap은오로지 객체 참조만 저장하기 때문에 primitive 타입은 wrapper 클래스를 사용해야한다. ex) int

HashMap은 해싱의 원리에 따라 작동한다. 해싱은 어떤 공식/알고리즘을 그것의 속성에 적용한 후에 어떤 변수/개체에 대해 고유한 코드를 할당하는 방법이다. 자바의 각 개체는 동일한 두 개체가 동일한 해시 코드를 일관되게 생성하도록 해시 코드를 가지고 있다.

관련 면접 질문

https://howtodoinjava.com/interview-questions/hashmap-concurrenthashmap-interview-questions/

• HashMap 동작원리

  https://firework-ham.tistory.com/11

5. Hashtable

Hash table 자료구조를 구현한 클래스이며 자바 HashMap과 매우 유사하다. 하지만 가장 큰 차이점은 Hashtable은 Synchronized를 제공한다.

6. LinkedHashMap

HashMap과 유사하지만 추가된 요소들에 대해 순서를 유지한다는 점이 다르다.

HashMap을 상속 받고 Map을 구현한 클래스 이다.

doubly-linked list(이중연결리스트) 를 통해 순서 보장이 이뤄진다.

생성자의 3번째 파라미터를 true로 지정하면 데이터 access에 따라 순서가 변경된다. 이때 변경되는 순서는 LRU 캐시에 따라 변경된다.

LinkedHashMap vs HashMap

• add, remove 메소드의 경우 링크드 해시맵의 성능이 더 나쁘다. 해시맵은 링크드 리스트를 유지하면 되지만 링크드해시맵은 순서를 유지하기 위해 이중연결리스트를 유지해야하기 때문이다.
• looping의 경우 링크드해시맵은 약간 빠르다. 링크드해시맵의 경우 ‘size’에만 비례하기 때문에 ‘해시맵’보다 약간 빠른 루프 오버 맵을 사용한다. HashMap의 경우 ‘size+capacity’에 비례하는 반복성능을 보였다.

7. TreeMap

해시맵과 유사하지만 red-black tree 기반인 NavigableMap을 구현하여 키벨류 쌍을 정렬하여 저장하는 효과적인 방법을 제공한다.

키를 자연적인 순서로 저장하거나 Comparator를 통해 정렬하여 저장한다.

containKey,get,put,remove 메소드의 log(n) 시간을 보장한다.

해시맵의 경우 O(1)의 성능을 보여주지만 메모리 관리 차원에서는 TreeMap은 내부적으로 키벨류 쌍을 저장할 array를 관리할 필요가 없기 때문에 더 유리하다.

• red-black tree

8. HashSet

Hashing을 이용해서 구현한 컬렉션이다. 데이터를 중복 저장할 수 없고, 순서를 보장하지 않는다. equals()나 hashCode()를 오버라이딩해서, 인스턴스가 달라도 동일 객체를 구분해 중복 저장을 막을 수 있다.

9. LinkedHashSet

HashSet 클래스를 상속받은 LinkedList이다. 데이터에 삽입된 순서대로 데이터를 관리한다.

10. TreeSet

이진탐색트리(Red-Black Tree)의 형태로 데이터를 저장한다. 데이터 추가, 삭제에는 시간이 더 걸리지만, 검색과 정렬이 더 뛰어나다. 기본적으로 오름차순으로 데이터를 정렬한다.