JCF

[10분 테코톡] ⚾️ 제이온의 JCF을 들으며 정리한 글입니다.

JCF란?

• Java Collections Framework
• 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합
• 데이터를 저장하는 자료구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해놓은 것

도입 배경

JCF가 도입되기 이전에는 데이터를 그룹핑하는 방법으로는 Array, Vector, Hashtable 등이 있었다. 
이 컬렉션들의 사용 목적이 같더라도 각각의 컬렉션에서 사용하는 문법이 다른 문제가 있었다. 

때문에 공통 인터페이스가 필요하다고 판단하였고, 이로인해 탄생한 것이 JCF이다. 

JCF의 계층 구조

크게 Collection 인터페이스와 Map 인터페이스로 나눌 수 있다. 

• Collection 인터페이스는 Iterable 인터페이스를 상속받음 
  • 즉 iterate() 메서드가 존재
• 하지만 Map 인터페이스는 이를 상속받지 않고 있음

List

• 순서가 있는 데이터의 집합
• 데이터의 중복을 허용
• List 인터페이스의 구현 클래스는 ArrayList, LinkedList, Vector, Stack 이 있음

ArrayList

• 크기가 가변적인 선형 리스트
• 저장 용량이라는 것이 존재
• 이 용량을 넘어서면 자동으로 용량을 증가해 추가적인 요소 넣을 수 있도록 함

요소 삽입

• 맨 끝에 요소를 삽입할 때는 시간 복잡도 O(1)
• 중간에 요소를 삽입할 떄는 시간 복잡도 O(N)

요소 삭제

• 중간에 요소를 삭제할 때는 시간 복잡도 O(N)

LinkedList

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조
• 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결 담당

요소 삽입

• 인자로 받은 값을 가지고 노드 생성
• 이전 노드는 새로 생성한 노드를 가리킴
• 새로 생성한 노드는 이전 노드가 가리키고 있던 것을 가리킴
• 맨 끝에 요소를 삽입할 때는 시간 복잡도 O(1)
• 중간에 요소를 삽입할 떄는 시간 복잡도 O(N)

요소 삭제

• 삭제할 노드의 이전 노드가 가리키는 곳을 다음 노드로 가리키게 함
• 중간에 요소를 삭제할 때는 시간 복잡도 O(N)

Vector

• JDK 1.0부터 있었던 자료 구조
• 호환성을 위해 남겨 놓은 레거시 클래스
• ArrayList와 기능상 거의 동일
• 하지만 ArrayList는 비동기, Vector는 동기 방식

Vector는 스레드 안전하고 멀티 스레드 환경에서는 ArrayList를 사용하지 못할까?

비동기와 동기, 스레드 안전

• 동기 방식은 요청을 보낸 후 응답을 받아야 다음 과정 동작
• 비동기 방식은 요청을 보낸 후, 응답과는 상관없이 다음 과정 동작
• 스레드 안전은 멀티 스레드 환경에서 어떤 함수나 변수, 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램 실행에 문제가 없음을 의미
• 비동기 방식은 스레드 안전하지 않고, 동기 방식은 스레드 안전

Vector vs ArrayList

Vector는 ArrayList와 달리 대부분의 메서드에 동기화처리가 돼있지만, 스레드 안전하지는 않다. 

위 코드를 예시로 들면, 다른 스레드에서는 현재 스레드에서 사용하고 있는 Vector의 사이즈와 get() 메서드를 사용하지 못한다. 
하지만, 다른 스레드에서 이 Vector에 remove() 같은 메서드를 사용하면 해당 스레드에서는 예외가 발생하게 된다. 

때문에 Vector는 ArrayList보다 성능도 떨어지고, ,스레드 안전하지 못하므로 사용하지 않는 것이 좋다. 
대신 멀티 스레드 환경에서는 Collections.synchronizedList()를 사용하자!

Stack

• Vector를 상속하여 사용하는 LIFO 방식의 클래스
• Stack 또한 레거시 클래스이므로 Deque를 사용하여 구현하자

Queue

• FIFO 구조를 가진 자료구조
• 주로 LinkedList를 이용해 구현
• 상속으로는 Deque와 Priority Queue가 있음

Priority Queue

• FIFO가 아닌 특정 우선순위에 따라 요소가 먼저 나감
• 우선순위는 Comparator를 통해 정의하거나, Comparable 인터페이스를 상속한 객체를 이용해야 함
• null 요소는 허용하지 않음

Deque

• Double-Ended Queue의 약어
• Queue의 양쪽 끝에서 추가와 삭제가 일어날 수 있는 자료구조
• Stack이 될 수 있고, Queue가 될 수 있음
• 구현 클래스로는 LinkedList와 ArrayDeque

Set

• 중복된 요소를 저장하지 않고, 요소의 저장 순서를 유지하지 않는 특징
• 중복된 요소를 걸러내기 위해 Set 인터페이스 내에 정의된 equals()와 hashCode()를 사용

HashSet

• Set을 이용하기 위해 가장 많이 사용하는 구현 클래스
• 해시 알고리즘을 사용해 검색 속도가 빠르다는 장점
• Set의 다양한 메서드를 정의하기 위해 Map의 메서드를 가져다 씀

LinkedHashSet

• HashSet과 원리는 같으나 입력된 순서를 저장
• HshSet의 상속을 받으며 LinkedHashMap을 통해 구현되어 있음

TreeSet

• 중복된 요소는 저장하지 않지만, 특정 기준에 따라 요소 정렬할 수 있음
• TreeMap 인스턴스를 통해 TreeSet을 구현

Map

• Key와 Value를 쌍으로 저장하는 자료구조
• Key는 중복 X, Value는 중복 허용
• Key를 통해 Value에 바로 접근이 가능하므로 탐색이 빠름
• 데이터의 순서를 보장

Hashtable

• Map 인터페이스의 구현 클래스이며, 자바 초기 버전에 나온 레거시 클래스
• Key와 Value가 null 값이면 안되고 Vector 처럼 대부분의 메서드가 동기화처리 되어있다는 특징

동작 원리

• Key를 특정 해시함수를 통해 해싱한 후 나온 결과를 배열의 인덱스로 사용해 Value를 찾는 방식으로 동작

HashMap

• Map 인터페이스의 구현 클래스이며 Hashtable을 보완
• HashMap은 비동기로 작동
• Hashtable보다 싱글 스레드 환경에서 성능이 좋음
• 멀티 스레드 환경에서는 ConcurrentHashMap을 사용

LinkedHashMap

• Map 인터페이스의 구현 클래스인 동시에 HashMap을 상속받음
• 데이터의 순서 보장
  • 순서를 보장하기 위해 LinkedList의 구조 이용

TreeMap

• Map 인터페이스의 구현 클래스
• Key를 기준으로 원하는 방식으로 정렬할 수 있음

왜 Map은 Collection 인터페이스에 상속을 받지 않았나?

• Map 요소는 무엇인가? Key? Value? Entry?
• Entry라면, Collections.remove(Entry)는 항상 Entry만 지운다. Key를 통해 value를 지울 수 없다. 
• 요소의 모호함과 구조상 맞지 않는 부분 때문에 Collection 인터페이스를 상속받지 않음

참고 자료

• [10분 테코톡] ⚾️ 제이온의 JCF