[Data Structure] Map, Set, List의 차이

L-j-h-c commented 2 years ago

Java Collection FrameWork의 기본 구조

Java Collection FrameWork를 사용하는 이유?

많은 수의 데이터를 처리하기 위해서, 가장 기본적인 방법으로 배열을 사용할 수 있다. 그러나 배열은, 크기를 자유롭게 늘릴 수 없으며 삽입, 삭제에 오랜 시간이 걸리기 때문에 이와 같은 일들을 효율적으로 처리하기 위해 동적 배열 개념인 컬렉션 프레임워크가 제공된다.

컬렉션 프레임워크의 종류의 대표격으로 List, Map, Set이 있는데, 이들 인터페이스를 구분하는 가장 큰 차이점은 순서 또는 데이터의 중복 여부이다. 각각의 기능과 장단점을 알아보자.

List

List는 가장 기본적인 인터페이스로, 각 원소들에 순서가 존재하며 같은 데이터가 중복되어 들어갈 수 있다.

공통적 특징

순서가 있음
중복을 허용함
인덱스로 원소에 접근 가능
크기가 변할 수 있음

List의 종류별 특징

LinkedList
- 원소의 앞뒤로 참조가 가능하며, 삽입과 삭제가 빠르다.
- ArrayList에 비해 검색이 느리다.
ArrayList
- 단방향 참조만 가능하여, 순차적으로 접근할 경우 강점을 가진다.
- 배열을 기반으로 데이터를 저장한다.
- 삽입과 삭제가 느린 대신 검색이 빠르다.

ArrayList의 경우 중간에 원소를 삽입 또는 삭제할 때, 뒤에 존재하는 원소들의 index를 수정해야 하기 때문에 시간이 오래 걸린다. 그러나 LinkedList의 경우 모든 원소의 index를 수정할 필요가 없어 중간 원소의 삽입과 삭제는 효율적이지만, 더 많은 메모리 영역을 차지하게 된다.

Map

Map은 key와 value의 쌍으로 존재하는 데이터의 집합이며, key는 중복될 수 없으며 순서가 보장되지 않는다. 따라서 key를 기반으로 출력할 경우 항상 순서가 바뀌는 모습을 확인할 수 있다. 또한 검색 속도가 빠르고, 인덱스가 따로 존재하지 않기 때문에 iterator를 사용해야 한다.

Map의 종류별 특징

HashMap
- HashTable을 이용하여 Map 인터페이스를 구현했다.
- 키와 값으로 null이 허용된다.
- 검색 성능이 가장 뛰어나다.
HashTable
- HashMap보다는 느리지만, 동기화가 가능하다(== 병렬 프로그래밍이 가능해진다)
- 키와 값으로 null이 허용되지 않는다.
LinkedHashMap
- HashMap을 상속받아 HashMap의 특징과 비슷하다.
- entry들의 입력 순서를 유지하므로 순서가 존재한다.
TreeMap
- 이진 검색 트리(RB Tree)의 형태로 key와 value의 쌍을 저장하고 있다.
- Tree 구조이기 때문에 빠른 검색이 가능하다.
- 저장시 정렬(오름차순)이 수행되기 때문에 저장 시간이 오래 걸린다.

Set

순서가 없고, 중복된 데이터를 허용하지 않는 데이터의 집합이다. 중복되지 않는 데이터를 만들고 싶을 때 유용하다. Map과 마찬가지로 Index가 존재하지 않기 때문에 Iterator를 사용해야 한다.

Set의 종류별 특징

HashSet
- 인스턴스의 Hash값을 기준으로 저장하기 때문에 순서가 보장되지 않는다.
- 임의 접근 속도가 가장 빠르다.
- Null 값을 허용한다.
- TreeSet보다 삽입, 삭제가 빠르다.
LinkedHashSet
- 입력된 순서를 보장한다.
TreeSet
- 이진 탐색 트리(RB Tree)를 기반으로 한다.
- 데이터들이 오름차순 정렬된다.
- 삽입, 삭제에는 시간이 오래 걸리지만 검색, 정렬이 빠르다.

L-j-h-c commented 2 years ago

https://cocoon1787.tistory.com/527 https://brunch.co.kr/@springboot/57

L-j-h-c commented 2 years ago

더 공부할 부분

HashTable의 동기화와 병렬 프로그래밍에 대해 살짝 찾아봤다. 동일한 데이터에 여러 스레드에서 접근을 시도할 때 생기는 문제를 동시성의 문제라고 하는데, 이 부분에 대해서 공부하려면 시간이 더 걸릴 것 같아서 일단 남겨뒀다. 나중에 공부해보자! 일단 각 자료형의 특징에 대해서만 알아봤는데, 이를 더 깊이 이해하려면 자료구조를 디자인한 방법을 알아보는 것이 더 깊은 이해에 도움이 될 것이다. 또한 각각의 자료구조 별로 존재하는 메서드들을 언제 어떻게 활용하는 것이 효율적인지에 대한 공부도 필요해 보인다.

L-j-h-c / TIL