JCF란?
Java Collections Framework의 약어로, 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미한다.
즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것이다. 여기서 Collections은 데이터의 집합이나 그룹이라고 생각하면 된다.
JCF의 도입 배경
JCF가 도입되기 전, 자바 객체를 그룹핑(Collection)하는 표준화된 방법은 Arrays, Vectors, Hashtables였으며, 이 Collection들에는 어떠한 공통 인터페이스가 존재하지 않았다. 따라서 이 Collection들의 사용 목적이 동일하더라도, 각자 따로 정의해야하는 문제가 있었다. 그리고 각각의 Collection마다 사용하는 메소드, 문법, 생성자가 달랐기에 개발자가 이들을 사용하면서 혼동하기가 쉬웠다.
따라서 자바 개발자들은 이러한 문제를 해결하기 위해 공통의 인터페이스를 설계하였고, 그것이 Java Collections Framework이다. 참고로, JCF가 등장하면서 Vector와 Hashtables은 레거시 클래스가 되어 오늘날에는 더이상 사용하지 않는다.
JCF의 계층 구조
JCF는 크게 Collection 인터페이스와 Map 인터페이스로 나뉜다.
List Interface
순서가 있는 데이터의 집합으로, 데이터의 중복을 허용한다.
ArrayList, LinkedList, Vector 클래스가 이를 구현한다.
ArrayList Class
ArrayList는 크기가 가변적인 선형 리스트로, 인덱스를 이용하여 내부 요소를 관리한다는 점이 일반적인 배열과 유사하다. 하지만, 한 번 사이즈가 정해지면 바꿀 수 없는 배열과 달리, ArrayList는 저장 용량(capacity)이라는 것이 존재하여 이 용량을 넘어서면 자동으로 용량을 증가함으로써 추가적으로 요소를 넣을 수 있도록 해 준다.
ArrayList를 생성할 때 인자로 값을 넘겨주는 것으로 초기 용량을 설정할 수 있으며, 인자를 넘기지 않을 경우 초기 용량은 10으로 설정된다.
ArrayList는 이 초기용량의 크기를 가진 배열을 내부적으로 가지고 있는데, 배열의 용량을 늘려야 하는 상황이 되면 특정 배수만큼 크기가 큰 배열을 새로 할당한 후 기존의 배열 값을 새로운 배열에 복사해 넣는다.
(1) 요소를 추가
요소를 추가하는 방법은 add(object)와 add(index, object)가 있다. 전자는 맨뒤에 요소를 차례차례 추가하는 것이지만, 후자는 원하는 위치에 요소를 끼워 넣을 수 있다.
다만, add(index, object)는 원하는 위치에 요소를 끼워 넣기 위해서 그 위치를 앞뒤로 비집고 들어가야 한다.
위 그림처럼 3번째 인덱스에 요소를 add(index, object)하고 싶다면, 원래의 3번째 인덱스부터 맨뒤까지 요소를 하나씩 다 밀어야 한다. 그리고 add(index, object)하는 과정에서 용량이 꽉차게 된다면, 새롭게 용량도 늘려줘야 하기 때문에 add(index, object)는 시간 복잡도가 O(N)이 된다. add(object)는 시간 복잡도가 O(1)인 것에 비해 성능이 떨어진다.
(2) 요소를 삭제
요소를 삭제할 때는 remove()를 사용하는데, add(index, object)와 비슷한 원리다. i번째 요소를 지우면 그 자리가 비게 되므로 (i + 1)번째부터 마지막 인덱스의 요소를 한 칸씩 왼쪽으로 밀어야 한다. 시간복잡도는 마찬가지로 O(N)이다.
(3) 요소를 탐색
요소가 있는지 없는지 탐색할 때는 contains()를 사용한다. 맨 앞부터 탐색을 하므로 시간복잡도는 O(N)이다.
(4) 요소를 반환
특정 요소를 반환할 때는 get()을 사용하는데, 인덱스를 사용하여 해당 위치를 바로 찾아낼 수 있으므로 시간 복잡도는 O(1)이다.
LinkedList Class
LinkedList는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 자료 구조다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.
(1) 요소를 추가
요소를 추가할 때는 add()를 사용하는데, ArrayList와 마찬가지로 add(obejct)는 맨 뒤에 요소를 추가하는 것이고, add(index, object)는 특정 위치에 요소를 넣는다.
위 사진처럼 먼저, 인자로 받은 값을 가지고 Node를 생성한다. 그리고 이전 노드는 새로 생성한 노드를 가리키고, 생성한 노드는 이전 노드가 가리키고 있던 곳을 가리키게 한다.
중간 위치에 요소를 삽입할 때의 시간 복잡도는 O(N)이 된다.
(2) 요소를 삭제
LinkedList에 요소를 제거하는 방법은 요소를 추가하는 것과 비슷하다. remove(index, value)를 사용하여 특정 index의 값을 제거할 수 있다.
삭제할 노드의 이전 노드가 가리키는 곳을 다음 노드로 가리키게 하면 해당 노드는 삭제가 된다. 이것도 요소 추가와 마찬가지로 시간 복잡도가 O(N)이 된다.
(3) 요소를 탐색
요소가 있는지 없는지 탐색할 때는 contains()를 사용한다. 맨 앞부터 탐색을 하므로 시간복잡도는 O(N)이다.
(4) 요소를 반환
특정 요소를 반환할 때는 get()을 사용하는데, 인덱스 없이 맨 앞부터 탐색해야 하므로 시간복잡도는 ArrayList와 달리 O(N)이다.
ArrayList vs. LinkedList
LinkedList는 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다.
그러므로 탐색을 자주 하는 경우엔 ArrayList를 사용하고 리스트의 시작이나 끝 부분에서 데이터의 추가/삭제가 많은 Queue같은 경우 LinkedList를 사용하는 것이 좋다.
Vector Class
Java 첫 버전부터 있었던 자료 구조로 지금은 쓰지 않지만, 호환성을 위해 남겨 놓은 레거시 클래스라고 할 수 있다. Vector는 ArrayList와 기능 상 거의 동일하지만, 동기화가 되어 있다는 차이점이 있다.
하지만 Vector는 특이하게도 동기화는 되어 있지만 쓰레드에 안전하지는 않다.
Vector는 메소드에 대해서는 동기화 처리가 되어있는 것이 맞지만 Vector 인스턴스에 대해서는 동기화 처리가 되어있지 않다.
Vector 인스턴스에 대해서 동기화 처리가 되어있지 않다면 다음과 같은 상황이 발생한다.
if (vector.size() > 0) {
System.out.println(vector.get(0));
}위의 코드는 Vector의 사이즈가 0보다 크다면 첫 번째 요소를 출력하는 것이다. 다른 쓰레드가 이 쓰레드에서 쓰인 size()와 get()에는 관여를 할 수 없다. Vector 메소드에 대해서는 동기화 처리가 되어있기 때문이다. 하지만 다른 쓰레드에서 Vector의 요소를 삭제해버린다면 여러 프로세스가 한 자원에 동시에 접근하게 되는 race condition이 발생한다. 즉 쓰레드에 안전하지 못하게 되는 것이다.
결국 싱글 쓰레드 환경에서는 모든 메소드가 동기화 처리되어 있는 느린 Vector를 쓸 이유가 없고, 멀티 쓰레드 환경에서도 쓰레드에 안전하지 않기 때문에 Vector를 쓸 이유가 없다. 또한 ArrayList도 Collections.synchronizedlist()를 통해 동기화된 리스트로 만들어줄 수 있다.
Stack Class
스택은 상자를 쌓아 올리는 것처럼 마지막에 들어온 데이터를 가장 먼저 출력하는 LIFO(Last in, First out) 구조이다. Vector 클래스를 상속받았다. 그렇기 때문에 사용하지 않는 것이 좋다.
오라클 문서에도 Stack을 사용할 때는 Deque을 사용하여 구현하라고 명시되어 있다.
Queue Interface
큐는 대기열처럼 가장 먼저 들어온 데이터를 가장 먼저 출력하는 FIFO(First in, First out) 구조이다. 구현체로는 LinkedList Class, PriorityQueue Class가 있다.
Set 인터페이스
Set 자료구조는 중복된 요소를 저장하지 않고, 요소의 저장 순서를 유지하지 않는 특징이 있으며, 주로 HashSet, LinkedHashSet, TreeSet 클래스를 통해 구현한다.
그렇다면, 중복된 요소를 어떻게 걸러낼까? 바로, Set 인터페이스 내의 정의된 equals()와 hashCode()를 사용하는 것이다.
객체를 저장하기 전에 객체의 hashCode()를 호출해서 해시 코드를 얻어낸다. hashCode()는 객체의 주소를 가져와서 두 객체가 같은 객체인지 확인하는 역할을 한다. 저장되어 있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교한다. equals() 메소드는 객체의 내용이 같은지 확인한다. 이때, true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.
HashSet Class
Set을 이용하기 위해 가장 많이 사용하는 구현 클래스이다. HashSet은 해시 알고리즘을 사용하여 검색 속도가 빠르다는 장점이 있다. 그리고 HashSet은 중복된 요소를 저장하지 않고, 요소의 순서도 저장하지 않는다.
다른 Set 구현 클래스들과 마찬가지로 AbstractSet이라는 추상 클래스를 상속받기 때문에 이 클래스에 구현되어 있는 equals(), hashCode(), removeAll()을 구현해줄 필요가 없다.
Map
Key와 Value를 쌍으로 저장하는 자료 구조로, Key는 중복될 수 없고 Value는 중복이 가능하다는 특징이 있다. Key를 통해 Value에 바로 접근이 가능하므로 상수 시간만에 탐색이 가능하다는 장점이 있으나, 데이터의 순서를 보장하지는 않는다.
구현 클래스로는 HashTable, HashMap, TreeMap 등이 있다.
Hashtable Class
Map 인터페이스의 구현 클래스이며, 자바 초기 버전에 나온 레거시 클래스이다. Key와 Value가 null값이면 안 되고, 동기화가 되어있다는 특징이 있다.
해시 테이블은 Key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인덱스로 사용하여 Value를 찾는 방식으로 동작한다. 여기서, 해시 함수는 Key를 Value가 저장되는 주소 값으로 바꾸기 위한 수식을 의미한다.
HashMap Class
Map 인터페이스의 구현 클래스이며, Hashtable을 보완하였다. HashMap은 멀티 쓰레드 환경에서는 어울리지 않지만, 이것도 보완하기 위해 ConcurrentHashMap이 등장하였다.
해시 함수를 이용하여 데이터의 Key 값을 특정 인덱스로 변환하고, 빈 공간 내에 그 인덱스의 위치에 저장한다. 이 인덱스를 해시 값이라고 부른다. 해시 값을 사용하면 저장된 값을 불러올 때 인덱스 값을 참조해서 불러오므로 연산 속도가 매우 빨라진다.
Key 값은 다르지만 해시 함수에 의해 같은 출력 값을 갖는 현상을 해시 충돌이라고 하는데, HashMap은 이를 해시 체이닝을 통해 해결하고 있다.
체이닝 기법은 LinkedList를 활용하여 저장하려는 해시테이블에 이미 같은 key의 데이터가 있다면, 노드를 추가하여 다음 노드를 가리키도록 구현하는 것을 말한다.
Map 인터페이스는 왜 Collection 인터페이스를 상속 받지 않았을까?
Collection은 요소들의 집합이라고 생각하면 되는데, Map은 요소라는 것을 정의하기가 어렵다. Map은 Key와 Value가 필요한데, 요소로 만드려면 Key-Value 쌍을 생각할 수 밖에 없다.
예를 들어, Collections.remove(Object o)를 취한다고 하자. 만약, Map이 Collection에 상속을 받았다면, remove()는 단순히 Key-Value 쌍을 지우게 될 것이다. 하지만, 실제 Map의 remove()의 인자는 key를 받는다. 이것은 번거롭게 인자를 Key-Value 쌍 형태의 객체로 받지 않기 위함이다.
이렇듯 요소라는 것의 모호함과 구조상 상응하지 않는 부분이 많아서 Map은 JCF에 포함하되, Collection 인터페이스에게 상속은 받지 않도록 설계한 것이다.
비슷한 맥락으로, Map 인터페이스는 Iterable 인터페이스를 상속받지 않아서 iterator()가 존재하지않는데, 이것은 iterate할 대상이 key인지 value인지 key-value 쌍인지 알 수 없어서 그런 것이다.
iterable vs. iterator
iterable은 Collection의 상위 인터페이스로 iterator를 반환하는 iterator() 추상 메서드를 가지고 있다. iterator는 컬렉션 클래스의 데이터를 다룰 때 사용되는 인터페이스로, hasNext(), next(), remove() 등의 메서드를 사용할 수 있다.
뿐만 아니라 forEach(), spliterator() 메소드도 있다.
Map 인터페이스는 iterable 인터페이스를 상속받지 않을 뿐만 아니라 iterator()가 구현되어있지 않기 때문에 iterator()가 없다. forEach()는 있고 그 외에 spliterator()도 존재하지 않는다.
Collection vs Collections
Collection은 JCF의 최상위 인터페이스이고, Collections는 Collection 조작을 위한 유틸리티 클래스이며 정적 메서드를 통해 컬렉션을 정렬, 검색, 동기화, 변환하는 등의 작업을 수행할 수 있다.
