[Java] Collections와 Map

코딩 테스트를 풀때 효율성 문제에서 제일 헷갈리는게 Collections 같다.

'자바 성능 튜닝 이야기' 책에 의하면 각 클래스의 효율성 자체는 크게 나지는 않지만...

어느 상황에 어떤 컬렉션을 쓰는 것이 적절한지 헷갈리니까 정리해두겠다.

 

이 글은 컬렉션 프레임워크를 대충 쓰고는 있었지만 서로의 차이점을 확실히 알고 싶은 사람에게 추천한다.

사용법이 아닌 개념과 이해를 위한 설명을 위주로 작성한다.

 

---

 

컬렉션 프레임워크(Collection Framework)란?

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

 

 

Collection Framework의 계층

img: https://www.javatpoint.com/collections-in-java

• Collection framework의 모든 클래스와 인터페이스는 java.util 패키지에 속함
• Map은 구조상 Collection에 포함되지는 않지만, java.util 패키지에 속한 것은 동일

 

 

Collection interface의 메소드

Method	Description
public boolean add(E e)	요소 추가
public boolean addAll(Collection<? extends E> c)	특정 collection의 요소들 추가
public boolean remove(Object element)	요소 제거
public boolean removeAll(Collection<?> c)	collection의 모든 요소 제거
default boolean removeIf(Predicate<? super E> filter)	지정된 조건의 모든 요소 제거
public boolean retainAll (Collection<?> c)	지정된 collection을 제외한 모든 요소 제거
public int size()	요소 개수
public void clear()	collection에서 총 요소 수 제거
public boolean contains(Object elemenet)	요소 찾기
public boolean containsAll (Collection<?> c)	특정 collection 찾기
public Iterator iterator()	iterator로 변환
public Object[] toArray()	collection -> array
public <T> T[] toArray(T[] a)	collection -> array. array의 런타임 타입은 지정된 배열의 런타임 타입.
public boolean isEmpty()	비었는지 검사
default Stream<E> parallelStream()	parallel Stream으로 변환
default Stream<E> stream()	Stream으로 변환
default Spliterator<E> splicteterator()	collection 안의 특정 요소를 Spliterator로 생성
public boolean equals(Object element)	두 collection을 비교
public int hashCode()	collection의 hash code 숫자 반환

 

공통인 메소드는 위와 같고 각 인터페이스마다 추가적인 메소드가 있다.

그렇다면 List, Queue, Set 등 각 인터페이스의 차이점이 뭘까?

 

List

• List는 데이터를 아무 위치에서나 넣었다 뺄 수 있다.
• 데이터를 삽입하면 그 순서를 유지한다.

 

Queue

• Queue는 데이터 삽입이 가장 앞에서만 이루어진다.
• 데이터 삭제는 가장 뒤에서만 이루어진다.
• 제일 오래 전에 삽입된 데이터가 가장 빨리 삭제되는 선입선출 (FIFO; First In First Out) 방식이다.

 

Stack

• Stack은 데이터의 삭제, 삽입이 가장 앞에서만 일어난다.
• 그림의 1, 2 표기는 삭제되는 데이터가 맨 앞에 위치해있어야 하기 때문에 임의로 작업 순서를 나타낸 것이며 반드시 삭제하고 삽입하라는 의미가 아니다.
• 제일 최근에 삽입된 데이터가 가장 빨리 삭제되는 후입선출 (LIFO; Last In First Out) 방식이다.

 

 

Set

• 순서가 없는 데이터 집합으로, 데이터의 중복을 허용하지 않는다.

 

 

셋의 차이점을 알았으니 조금 더 세밀하게 살펴보자.

ArrayList와 LinkedList, HashSet과 TreeSet등의 차이점이 뭘까?

크게는 각 요소의 값의 중복을 허용하거나, 요소가 삽입 순서 또는 값 크기별로 정렬에 따라 순서를 유지하는지의 여부가 가장 다르다.

 

	인덱스	중복	순서	삽입 메소드	삭제 메소드
ArrayList	O	O	O	add()	remove()
LinkedList	X	O	O	add()	remove()
Vector	O	O	O	add()	remove()
Stack	X	O	O	push()	pop()
Queue	X	O	O	add() offer()	remove() poll()
HashSet	X	X	X	add()	remove()
TreeSet	X	X	자동 정렬	add()	remove()

 

표를 보면 두 가지 눈에 띄는 부분이 있다.

1. Queue의 삽입, 삭제 메소드가 2가지
2. TreeSet의 자동 정렬 ?

 

-> Queue에서는 문제 상황에서 예외를 던지느냐 아니면 null이나 false를 반환하느냐에 따라 메소드가 달라진다.

	예외 발생	값 반환
삽입	add()	offer()
삭제	remove()	poll()

 

-> TreeSet에서 자동으로 정렬된다는 말은 레드-블랙 트리를 따르기 때문이다.

이진 탐색 트리인 레드 블랙 트리는 부모 노드보다 작은 값은 왼쪽 자식으로, 큰 값은 오른쪽 자식으로 보내 검색 성능이 뛰어난 트리이다.

(더 자세한 설명: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree ) 

 

---

여기서 Collection을 공부해본 적 있는 사람들은 Map의 설명이 없다는 것을 눈치 챘을거다.

Map은 Collection의 다른 인터페이스들과는 구조가 달라서 따로 존재한다.

(java.util 패키지 내에 존재하는 것은 동일하다.)

 

Map은 데이터가 (키, 값)으로 존재하는 인터페이스다.

• 삽입: put(키, 값)
• 삭제: remove(키)
• 값 검색: get(키)
• 포함 여부: containsKey(), containsValue() 

 

Map 인터페이스에서 흔하게 쓰이고 자주 사용하는건 아래와 같다.

• 하위 인터페이스: ConcurrentMap, SortedMap
• 구현 클래스: HashMap, Hashtable, TreeMap

Collection interface와 유사하게 Hash가 붙으면 중복이 불가능하고,

Tree가 붙으면 레드-블랙 트리의 구조를 따른다.

 

자세한 사용법이나 설명은 참고에 써둔 링크를 확인하길 바란다.

 

 

Collection에 대해 한 가지 더 살펴보자면 동기화 여부를 보면 좋을 것 같다.

코딩 테스트 수준에서는 상관 없지만, 실무에서 사용할 때 스레드 문제는 굉장히 중요하므로...

나는 일단 synchronized 키워드를 언제 쓰는건지도 헷갈려서ㅠㅠ 

이에 대한 학습부터 하고 나중에 새로 글을 작성하도록 하겠다.

 

---

참고

Collection Framework란? http://tcpschool.com/java/java_collectionFramework_concept

Collection Framework Method https://www.javatpoint.com/collections-in-java

Map https://docs.oracle.com/javase/8/docs/api/java/util/Map.html