on
JCF
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 인터페이스를 상속받지 않음
참고 자료
from http://newwisdom.tistory.com/111 by ccl(A) rewrite - 2021-12-08 15:26:34