[JAVA] Collection Framework (컬렉션 프레임워크)

Collection Framework란?

배열의 크기는 고정적이라는 문제가 있습니다. 크기는 생성할 때 결정되며 그 크기를 넘어가면 더 이상 데이터를 저장할 수 없습니다. 또한 데이터를 삭제하면 해당 인덱스의 데이터는 비어있기 때문에 메모리가 낭비 되는 문제가 발생합니다. 자바는 배열의 이런 문제점을 해결하기 위해, 자료구조를 바탕으로 객체나 데이터들을 효율적으로 관리(추가, 삭제, 검색, 저장)할 수 있는 자료구조를 만들었습니다. 이러한 자료구조들이 있는 라이브러리를 컬렉션 프레임워크라고 한다. 대표적으로 List, Set, Map 등이 있다.

Collection Framework의 이점

• List, Set, Map 등의 인터페이스를 제공하고, 이를 구현하는 클래스를 제공하여 일관된 API를 사용할 수 있다.
• 가변적인 공간 제공한다.
• 자료구조, 알고리즘을 구현하기 위해 코드를 직접 작성할 필요 없이, 이미 구현된 컬렉션 클래스를 목적에 맞게 선택하여 사용하면 된다.
• 제공되는 API의 코드는 검증되었으며, 최적화 되어있다.

구성요소

1. Interface: 각 컬렉션을 나타내는 추상 데이터에 대한 인터페이스. 클래스는 이 인터페이스를 구현하는 방식으로 작성되었다.
2. Class: 컬렉션 별 인터페이스의 구현. 같은 List 컬렉션이더라도 목적에 따라 ArrayList, LinkedList 등으로 상세 구현이 달라 질 수 있다.
3. Algorithms: 컬렉션이 제공하는 연산, 검색, 정렬, 셔플 등에 대한 메소드

List 컬렉션

• 중복 허용
• 인덱스 순서로 저장

List 컬렉션은 객체를 일렬로 늘어놓은 구조이다. 객체를 인덱스로 관리하기 때문에 List 컬렉션에 객체를 추가하면 자동 인덱스가 부여된다. 인덱스는 객체를 검색, 삭제할 때 사용한다. List 컬렉션은 객체 자체를 저장하는 것이 아닌 객체의 번지를 참조한다.

List 컬렉션 클래스에 속하는 대표적인 클래스

• ArrayList
• LikedList
• Vector

List 주요 메소드

메소드	설명
boolean add(E e)	해당 리스트에 전달된 요소를 추가
void add(int index, E e)	해당 리스트의 특정 위치에 전달된 요소를 추가
void clear()	해당 리스트의 모든 요소를 제거
boolean contains(Object o)	해당 리스트가 전달된 객체를 포함하고 있는지 확인
boolean equals(Object o)	해당 리스트와 전달된 객체가 같은지 확인
E get(int index)	해당 리스트의 특정 위치에 존재하는 요소를 반환
boolean isEmpty()	해당 리스트가 비어있는지 확인
Iterator iterator()	해당 리스트의 반복자(iterator)를 반환
boolean remove(Object o)	해당 리스트에서 잔달된 객체를 제거
boolean remove(int index)	해당 리스트의 특정 위치에 존재하는 요소를 제거
E set(int index, E e)	해당 리스트의 특정 위치에 존재하는 요소를 전달받은 객체로 대체
int size()	해당 리스트의 요소의 총 개수를 반환
Object[] toArray()	해당 리스트의 모든 요소를 Object 타입의 배열로 반환

ArrayList

• List 인터페이스를 상속 받은 클래스로 크기가 가변적으로 변하는 선형리스트
• 순차리스트이며 인덱스로 내부의 객체를 관리
• 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량이 늘어남

LinkedList

• LinkedList는 양방향 연결 리스트로 구현 되어 있음
• 각각의 노드를 연결하는 방식
• 각각의 데이터가 노드(Node)로 구성되어 연결 되는 구조
• 각각의 노드는 데이터와 함께 next(다음 노드), prev(이전 노드) 값을 내부적으로 가지고 있음
• 어느 위치에서든 추가/삭제를 할 경우 변경 되는 노드 연결
• 데이터 추가, 삭제 빠름
• 인덱스가 없기 때문에 데이터 검색은 느림

Vector

• ArrayList 와 비슷한 기능을 수행하지만 Thread-Safe함
• 동기화 된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드를 실행 할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들을 실행
• 싱글 스레드일 때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어짐
• 사용이 권장되지는 않음

---

Set 컬렉션

• 저장 순서가 유지 되지 않음
• 중복 저장 안됨 (중복이 안되기 때문에 null도 한 번만 저장됨)

순서가 없으므로 인덱스로 객체를 검색해서 가져오는 메소드도 없다. 대신 전체 객체를 대상으로 한 번씩 반복해서 가져오는 Iterator(반복자)를 제공한다.

Set 컬렉션에 속하는 대표적인 클래스

• HashSet
• TreeSet

Set 주요 메소드

메소드	설명
boolean add(E e)	주어진 객체를 저장 후 성공적이면 true, 중복 객체면 false를 리턴
boolean contains(Object o)	주어진 객체가 저장 여부를 리턴
Iterator iterator()	저장된 객체를 한 번씩 가져오는 반복자를 리턴
isEmpty()	컬렉션이 비어있는지 확인
int Size()	저장되어 있는 전체 객체수를 리턴
void clear()	저장된 모든 객체를 삭제
boolean remove(Object o)	주어진 객체를 삭제

HashSet

HashSet 클랙스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관 없이 저장하고 중복된 값을 저장하지 않는다. 만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 된다.

add() 메소드를 사용하여 해당 HashSet에 이미 존재하는 요소를 추가하려고 하면 해동 요소는 저장하지 않고 false를 반환한다. equals()와 hashCode()를 호출하기 때문에 두 메소드를 목적에 맞게 오버라이딩 해야한다.

HashSet에 이미 존재하는 요소인지를 파악하기 위해서 내부적으로 다음과 같은 과정을 거친다.
1. 해당 요소에서 hashCode() 메소드를 호출하여 반환된 해시값으로 검색할 범위를 결정
2. 해당 범위 내의 요소들을 equals() 메소도를 비교

TreeSet

TreeSet 클래스는 이진 탐색 트리의 형태로 데이터가 정렬된 상태(오름차순)로 저장된다. 이진 탐색 트리 중에서도 성능을 향상 시킨 레드-블랙 트리(Red-Black tree)로 구현한다. 데이터 추가, 삭제에는 시간이 더 걸리지만, 검색과 정렬이 더 뛰어나다. Set 인터페이스를 구현하므로, 요소를 순서에 상관 없이 저장하고 중복된 값은 저장하지 않는다.

HashSet의 경우 정렬을 해주지 않지만 TreeSet의 경우 오름차순으로 자동 정렬을 해준다는 차이가 있다. LinkedHashSet은 입력된 순서대로 데이터를 관리한다.

---

Map 컬렉션

Map 인터페이스를 구현한 Map 컬렉션 클래스들은 키와 값을 하나의 쌍으로 저장하는 key-value 방식을 사용한다.

• 요소의 저장 순서를 유지 하지 않음
• 키는 중복을 허용하지 않지만 값의 중복은 허용

Map 컬렉션에 속하는 대표적인 클래스

• HashMap
• TreeMap

HashMap

대표적인 Map 컬렉션이다. 해시 알고리즘을 사용하여 검색 속도가 매우 빠르다. HashMap 클래스는 Map 인터페이스를 구현하므로, 중복된 키로는 값을 저장할 수 없다.

HashMap 주요 메소드

메소드	설명
void clear()	해당 map의 모든 mapping을 제거
boolean containsKey(Object key)	해당 맵이 전달된 키를 포함하고 있는지 확인
boolean containsValue(Object value)	해당 맵이 전달된 값에 해당하는 하나 이상의 키를 포함하고 있는지 확인
V get(Object key)	해당 맵에서 전달된 키에 대응하는 값을 반환
SetkeySet()	해당 맵에 포함되어 있는 모든 키로 만들어진 Set 객체를 반환
V put(K key, V value)	해당 맵에 전달된 키에 대응하는 값으로 특정 값을 매핑
V remove	해당 맵에서 전달된 키에 대응하는 매핑을 제거
boolean remove(Object key, Object value)	해당 맵에서 특정 값에 대응하는 특정 키의 매핑을 제거
V replace(K key, V value)	해당 맵에서 전달된 키에 대응하는 값을 특정 값으로 대체
boolean replace(K key, V oldValue, V newValue)	해당 맵에서 특정 값에 대응하는 전달된 키의 값을 새로운 값으로 대체
int size()	해당 맵의 매핑의 총 개수를 반환

TreeMap

TreeMap은 이진트리를 기반으로 한 Map 컬렉션이다. 같은 Tree구조로 이루어진 TreeSet과 차이점은 TreeSet은 값만 저장한다면, TreeMap은 키와 값이 저장도니 Map, Entry를 저장한다는 점이다. TreeMap에 객체를 저장하면 자동 정렬 되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 타입이 숫자일 경우 값으로, 문자열일 경우 유니코드로 정렬한다. 정렬 순서는 기본적으로 부모 키값과 비교해서 키값이 낮은 것이 왼쪽 자식 노드에 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장한다.

TreeMap은 일반적으로 Map으로써 성능이 HashMap보다 떨어진다. 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸린다. 하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다.

Red-Black Tree

TreeMap은 이진 탐색 트리의 문제점을 보완한 레드-블랙 트리로 이루어져있다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요하다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 낸다. 이 문제를 보완하기 위해 레드 블랙 트리가 등장하였다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어준다.

TreeMap 주요 메소드

메소드	설명
Map.Entry< K,V> ceilingEntry(K key)	해당 맵에서 전달된 키와 같거나, 전달된 키보다 큰 키 중에서 가장 작은 키와 그에 대응하는 값의 엔트리를 반환, 해당하는 키가 없으면 null 반환
K ceilingKey(K key)	해당 맵에서 전달된 키와 같거나, 전달된 키보다 큰 키 중에서 가장 작은 키를 반환, 해당하는 키가 없으면 null 반환
void clear()	해당 맵의 모든 매핑을 제거
boolean containsKey(Object key)	해당 맵이 전달된 키를 포함하고 있는지 확인
boolean containsValue(Object value)	해당 맵이 전달된 값에 해당하는 하나 아싱의 키를 포함하고 있는지 확인
NavigableMap< K,V> descendingMap()	해당 맵에 포함된 모든 매핑을 역순으로 반환
Set< Map.Entry< K,V>> entrySet()	해당 맵에 포함된 모든 매핑을 Set 객체로 반환
Map.Entry< K,V> firstEntry()	해당 맵에서 현재 가장 작은(첫 번째) 키와 그에 대응하는 값의 엔트리를 반환
K firstKey()	해당 맵에서 현재 가장 작은(첫 번째) 키를 반환
Map.Entry< K,V> floorEntry(K key)	해당 맵에서 전달된 키와 같거나, 전달된 키보다 작은 키 중에서 가장 큰 키와 그에 대응하는 값의 엔트리를 반환, 해당 하는 키가 없으면 null 반환
K floorKey(K key)	해당 맵에서 전달도니 키와 같거나, 전달된 키보다 작은 키 중에서 가장 큰 키를 반환, 해당하는 키가 없으면 null 반환
V get(Object key)	해당 맵에서 전달된 키에 대응하는 값을 반환
SortedMap< K,V> headMap(K toKey)	해당 맵에서 전달된 키보다 작은 키로 구성된 부분만 반환
Map.Entry< K, V> higherEntry	해당 맵에서 전달된 키보다 작은 키 중에서 가장 큰 키와 그에 대응하는 값의 엔트리를 반환, 해당하는 키가 없으면 null 반환
K higherKey(K key)	해당 맵에서 전달된 키보다 작은 키 중에서 가장 큰 키를 반환, 해당하는 키가 없으면 null 반환
Set< K> keySet()	해당 맵에 포함되어 있는 모든 키로 만들어진 Set 객체를 반환
Map.Entry< K,V> lastEntry()	해당 맵에서 현재 가장 큰(마지막) 키와 그에 대응하는 값의 엔트리 반환
K lastKey()	해당 맵에서 현재 가장 큰(마지막) 키를 반환
Map.Entry< K,V> lowerEntry(K key)	해당 맵에서 전달된 키보다 큰 키 중에서 가장 작은 키와 그에 대응하는 값의 엔트리를 반환, 없다면 null
K lowerKey(K key)	해당 맵에서 전달된 키보다 큰 키 중에서 가장 작은 키를 반호나, 없다면 null
Map.Entry< K,V> pollFirstEntry()	해당 맵에서 현재 가장 작은(첫 번째) 키와 그에 대응하는 값의 엔트리를 반환하고, 해당 엔트리를 맵에서 제거
Map.Entry< K,V> pllLastEntry()	해당 맵에서 현재 가장 큰(마지막) 키와 그에 대응하는 값의 엔트리를 반환하고, 해당 엔트리를 맵에서 제거
V put(K key, V value)	해당 맵에서 전달된 키에 대응하는 값으로 특정 값을 매핑
V remove(Object key)	해당 맵에서 전달된 키에 대응하는 매핑을 제거
boolean remove(K key, V value)	해당 맵에서 특정 값에 대응하는 특정 키의 매핑을 제거
V replace(K key, V value)	해당 맵에서 전달된 키에 대응하는 값을 특정 값으로 대체
boolean replace(K key, V oldValue, V newValue)	해당 맵에서 특정 값에 대응하는 전달된 키의 값을 새로운 값으로 대체
int size()	해당 맵의 매핑의 총 개수를 반환
SortedMap< K,V> subMap(K fromKey, K toKey)	해당 맵에서 fromKey부터 toKey까지로 구성된 부분만들 반환, 이때 fromKey는 포함되나 toKey는 포함되지 않음
SortedMap< K,V> tailMap(K fromKey)	해당 맵에서 fromKey와 같거나 formKey보다 큰키로 구성된 부분만을 반환

참고 사이트

https://coding-factory.tistory.com/550

https://jobjava00.github.io/language/java/basic/collections/

https://hudi.blog/java-collection-framework-1/

http://www.tcpschool.com/java/java_collectionFramework_list