List, Map, Set 배경

기존에는 많은 데이터들을 삽입, 삭제, 검색을 하기 위해 배열을 사용했다. 하지만 이 배열은 크기가 고정되어 있고 삽입, 삭제가 오래 걸린다는 단점을 가지게 된다.
따라서 자바는 이것을 보완하기 위해 1)동적배열 개념인 Collection Framework를 제공하게 되는데 대표적인 종류가 List, Set, Map이다. 자바의 Collection Framework는 자료의 삽입, 삭제, 검색이 용이해지고 어떤 자료형이라도 담을 수 있고 크기가 자유롭게 늘어나기 때문에 많은 사람들이 사용하고 있다.

Collection Framework은 데이터 집합(Collection)을 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 것을 의미한다

List, Map, Set 간단 비교

	종류	순서	데이터 중복
List	ArrayList	o	o
	LinkedList	o	o
Map	HashMap	x	Key: x / Value: o
	LinkedHashMap	o	Key: x / Value: o
	TreeMap	x 입력순서는 유지하지 않으나, 입력된 key의 데이터에 따라 정렬되어 저장	Key: x / Value: o
set	HashSet	x	x
	LinkedHashSet	o	x
	TreeSet	x 입력순서는 유지하지 않으나, 입력된 데이터에 따라 정렬되어 저장	x

List

순서가 존재하고, 데이터 중복이 허용된다!

ArrayList

• ArrayList는 기본적으로 Array(배열)을 사용한다.
• 하지만 일반 배열은 크기를 지정해주어야 하지만,
  ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입, 삭제할 수 있다.

조회
ArrayList는 조회가 빠르다. ArrayList는 각각의 데이터들이 index를 가지고 있기 때문에 각 index의 데이터를 가져오면 된다.
삽입
ArrayList는 삽입, 삭제가 느리다. 만약 중간에 2개의 삭제가 일어났다면 나머지가 앞으로 이동해야한다.
그리고 데이터 추가가 일어날 때 배열보다 데이터의 크기가 커지면, 더 큰 배열을 만든 후 데이터를 옮기고 예전 배열을 삭제하는 방식으로 진행된다.

LinkedList

• LinkedList는 내부적으로 양방향으로 이루어져있기 때문에 정방향이나 역순으로 조회가 가능하다.
• 배열의 단점을 보안하기 위해 LinkedList가 탄생했다.

조회
LinkedList는 순차적 접근이기 때문에 ArrayList보다 검색의 속도가 느리다
삽입
LinkedList는 데이터의 추가, 삭제가 빠르다.
데이터의 삭제와 삽입이 일어나면, LinkedList는 주소값만 바꾸어주면 된다.

Map

Key 값과 Value 값을 관리해주는 컬렉션이다.
Key값은 데이터 중복을 허용하지 않지만, Value 값은 데이터 중복을 허용한다.

Map<String, String> map = new HashMap<String, String>();

map.put("key1", "value1");
map.put("key2", "value2");

System.out.println(map.get("key1"));

"key1"이라는 Key 값과 "value1"이라는 Value 값을 갖는 Entry가 HashMap 내부에 put() 메소드를 통해 저장된다. 해당 값을 가져올 때에는 get() 메소드를 활용해서 Key 값인 "key1"라는 문자열만 넘겨주면 Value 값을 얻어올 수 있는 형태의 컬렉션이다.

HashMap

Map<String, String> map = new HashMap<String, String>();

map.put("Daum", "Korea");
map.put("Naver", "Korea");
map.put("Facebook", "USA");

for(Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());

// 출력 값
// Naver:Korea
// Facebook:USA
// Daum:Korea
>>순서대로 출력x, 무작위

• Map 중 가장 많이 쓰인다.
• 입력된 순서나 Key 값의 정렬 순서는 지켜지지 않는다.
• HashMap은 자바 내부에 Entry 배열을 만들어 관리한다.
• Key 값을 해싱하여 Entty 배열의 인덱스 값으로 활용한다. 만약 Key 값을 해시 값으로 만든 값이 10이라면, 배열의 10번째 값에 해당 value값을 저장한다.
• 해시충돌을 막기 위해 equal()이라는 함수를 사용해서 key값까지 같을 경우에만 value를 리턴해준다.
• 해시값을 이용하기 때문에 정렬 순서가 뒤섞이게 된다.
  
  

LinkedHashMap

Map<String, String> map = new LinkedHashMap<String, String>();

map.put("Daum", "Korea");
map.put("Naver", "Korea");
map.put("Facebook", "USA");

for(Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
  
// 출력 값
// Daum:Korea
// Naver:Korea
// Facebook:USA
>>순서대로 출력o

• LinkedHashMap은 데이터의 입력된 순서를 기억한다.
• 내부에 before, after 멤버를 갖는 연결리스트 구조를 가지고 있다.
• LinkedHashMap은 HashMap을 확장한 클래스이다.
• 데이터의 삽입 삭제가 빠르다.
  
  

TreeMap

Map<String, String> map = new TreeMap<String, String>();

map.put("Daum", "Korea");
map.put("Naver", "Korea");
map.put("Facebook", "USA");

for(Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
  
// 출력 값
// Daum:Korea
// Facebook:USA
// Naver:Korea
>> 사전순으로 정렬

• HashMap과 다르게 TreeMap은 Key - Value 쌍을 내부적으로 RedBlack Tree로 저장하여 관리한다.
• 따라서 Key값을 기준으로 정렬하여 사용할 수 있다.
• Key 값으로 사용할 클래스에 Comparator 인터페이스를 구현하면 사용자가 정렬된 순서를 조정할 수 있다.
• 내부적으로 RedBlack Tree 형태로 관리하기 때문에 데이터를 탐색하는데 O(log N)의 시간이 걸린다. 또 한, 엘리먼트의 추가/삭제 역시 O(log N) 시간이 걸린다. HashMap과 비교해보면 속도가 느리다.
  
  
  
  

Set

• 데이터 중복을 허용하지 않는다.
  => 중복을 자동으로 제거해준다.
  ex)12번째 손님이 여러 번 방문해도 한 번으로 처리한다,
• 하나의 null만 저장 할 수 있다.
• HashSet이 TreeSet이나 LinkedHashSet보다 성능이 더 빠르고, 메모리를 적게 사용한다.
• Set은 사실 Map에서 key 값만 사용한 컬렉션이라고 보면 된다. 따라서, Map에 대한 지식이 우선적으로 있어야 하는 컬렉션이다.

HashSet

• 처리 속도가 빠르다.
• 동일 객체 뿐만 아니라, 동등 객체의 중복도 허용하지 않는다.

LinkedHashSet

• 데이터의 입력된 순서를 기억한다.
• Set은 일반 배열로 변환 할 수 있다.

TreeSet

• TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장한다.
• 오름차순 정렬 기준(정규식 0-9, A-Z, a-z 순)으로 정렬한다.
• 역순 정렬이 가능하다.( NavigableSet descendingSet() )
• TreeSet은 이진검색트리 구조(root와 node)이기 때문에 HashSet과는 다르게 추가된 메서드들이 존재한다.

용어 정리

1)동적배열 : 배열이라고 하면 보통 정적 배열을 뜻한다. 동적배열은 저장공간이 꽉 차면 자동적으로 사이즈를 늘려 데이터를 삽입/저장할 수 있는 유동적인 자료구조이다.

참고자료

1) JAVA Collection Framework의 상속 기본 구조
https://cocoon1787.tistory.com/527
2) https://velog.io/@esun1903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-List-Map-Set%EC%9D%98-%ED%8A%B9%EC%A7%95%EA%B3%BC-%EC%B0%A8%EC%9D%B4%EC%A0%90
3) https://dev-coco.tistory.com/19
4) Map
https://soft.plusblog.co.kr/70
5) Set
https://doompok.tistory.com/6
https://bepoz-study-diary.tistory.com/246