Java로 개발을 할 때 가장 많이 쓰이는 자료구조는 List, Set과 Map이며 이들은 모두 interface로 여러 구현체들을 제공한다.
하지만 대부분 관성적으로 ArrayList, HashSet, HashMap을 주로 사용한다.
각 자료 구조의 대표적인 기능은 구현체마다 모두 동일하기 단순히 자료를 담는 역할로써 단순히 위 구현체들을 쓰는건 크게 문제가 되지 않지만, 각 구현체는 엄연히 다른 기능을 한다.
이번 포스팅에서는 java.util 에서 기본적으로 제공해주는 List, Set, Map의 구현체들을 몇가지를 살펴보도록 하겠다.
List
List는 중복을 허용하는 데이터를 담는 역할을 한다.
ArrayList
ArrayList는 클래스 명에서도 나타내듯 List 내부에 Array를 두고, 이 Array에 데이터를 저장한다.
(데이터가 추가되어 Array의 사이즈를 증가가 필요할 때는 새로운 Array는 사이즈는 기존 Array 사이즈의 1.5배이다 - 참고)
@Test
void ArrayList_() {
final var list = new ArrayList<String>();
list.add("bbb");
list.add("ddd");
list.add("aaa");
list.add("ccc");
list.add("aaa");
assertEquals(list.get(0), "bbb");
assertEquals(list.get(1), "ddd");
assertEquals(list.get(2), "aaa");
assertEquals(list.get(3), "ccc");
assertEquals(list.get(4), "aaa");
}
LinkedList
ArrayList와 기능적으로는 동일하지만 내부적으로 Node가 다음 Node를 가리키는 형태로 연결된 형태로 구현된 List이다.
앞서 말했듯 기본적인 기능은 동일하지만 getFirst, getLast와 같이 LinkedList 특성화된 메서드도 제공한다.
@Test
void LinkedList_() {
final var list = new LinkedList<String>();
list.add("bbb");
list.add("ddd");
list.add("aaa");
list.add("ccc");
list.add("aaa");
assertEquals(list.get(0), "bbb");
assertEquals(list.get(1), "ddd");
assertEquals(list.get(2), "aaa");
assertEquals(list.get(3), "ccc");
assertEquals(list.get(4), "aaa");
System.out.println("list.getFirst() = " + list.getFirst()); // bbb
System.out.println("list.getLast() = " + list.getLast()); // aaa
}
Vector
Java 1.2 이전 구세대의 유물로, 현재는 List와 호환이 되도록 진화되었고 ArrayList와 거의 동일한 동작을 수행 한다.
하지만 javadoc에서 볼 수 있듯 Vector 대신 ArrayList 사용을 추천하고 있다.
추가적으로 Vector는 thread-safe 하다는 특성이 있다.
@Test
void Vector_thread_safe() {
final var list = new Vector<String>();
list.add("bbb");
list.add("ddd");
list.add("aaa");
list.add("ccc");
list.add("aaa");
assertEquals(list.get(0), "bbb");
assertEquals(list.get(1), "ddd");
assertEquals(list.get(2), "aaa");
assertEquals(list.get(3), "ccc");
assertEquals(list.get(4), "aaa");
}
Stack
Stack은 LIFO(last-in-first-out)를 따르는 자료구조로 Java에서 List interface의 구현체 중 하나이다.
(하지만 FIFO(first-in-first-out)를 따르는 Queue는 Collection의 구현체이다)
List의 구현체이기 때문에 기본적인 List의 기능은 그대로 제공하며,
Stack으로써 가장 마지막에 쌓인 데이터를 가져오기 위해 peek, pop 메서드를 제공한다.
@Test
void Stack_() {
final var list = new Stack<String>();
list.add("bbb");
list.add("ddd");
list.add("aaa");
list.add("ccc");
list.add("aaa");
assertEquals(list.get(0), "bbb");
assertEquals(list.get(1), "ddd");
assertEquals(list.get(2), "aaa");
assertEquals(list.get(3), "ccc");
assertEquals(list.get(4), "aaa");
System.out.println("list.peek() = " + list.peek()); // last in 값 확인 - aaa
System.out.println("list.pop() = " + list.pop()); // last in 값 빼오기 - aaa
}
사실 Stack은 Vector의 서브 클래스로, Stack 고유의 기능을 제외하고는 List로써의 기능은 슈퍼 클래스인 Vector를 그대로 사용하고 있다.
Map
Map은 key, value 기반으로 데이터를 저장하여, 특정 key의 value를 쉽게 탐색할 수 있도록 하는 자료구조이다.
Set은 주로 Map을 기반으로 구현되어 있기 때문에 Set의 구현체를 살펴보기 전에 먼저 Map에 대해 살펴보도록 한다.
HashMap
HashMap은 hash table 기반의 Map 구현체이다.
HashMap 내부에 저장된 데이터는 특정한 순서를 보장하지 않는다.
@Test
void HashMap_순서_보장_X() {
final var map = new HashMap<String, String>();
map.put("bbb", "2");
map.put("ddd", "4");
map.put("aaa", "1");
map.put("ccc", "3");
for (final var entry : map.entrySet()) {
System.out.println(entry);
}
}
※ HashMap 내부 구현 관련
hash table을 구현할 때 서로 다른 key에 대해 hash 충돌을 피하기 위해 내부적으로 bucket에 linked list를 사용하는 chaining 방식을 사용할 수 있다.
HashMap의 경우 기본적으로 bucket에 linked list와 같은 구조를 사용하다가, key가 다르지만 동일한 hash의 데이터가 많아지면 탐색 성능을 위해 tree 형태로 변경한다.
(tree는 linked list에 비해 탐색에 있어서 시간 복잡도가 낮기 때문에)
TreeMap
TreeMap은 Red-Black tree 기반으로, key를 기준으로 데이터를 정렬한다는 특징이 있다.
아래 예제의 경우 key로 String을 사용하였기 때문에 abc 순으로 데이터가 정렬된 것을 확인할 수 있다.
@Test
void TreeMap_key를_기준으로_정렬() {
final var map = new TreeMap<String, String>();
map.put("bbb", "2");
map.put("ddd", "4");
map.put("aaa", "1");
map.put("ccc", "3");
final var keys = map.keySet().stream().toList();
assertEquals(keys.get(0), "aaa");
assertEquals(keys.get(1), "bbb");
assertEquals(keys.get(2), "ccc");
assertEquals(keys.get(3), "ddd");
}
LinkedHashMap
LinkedHashMap은 데이터 입력 순서를 보장하는 Map 구현체이다.
다만 여기서 한가지 주의할 점은 동일한 key로 값을 덮어씌우는 경우에, 기존에 있던 key의 순서를 그대로 사용한다는 것이다.
@Test
void LinkedHashMap_입력_순서_보장() {
final var map = new LinkedHashMap<String, String>();
map.put("bbb", "2");
map.put("ddd", "4");
map.put("aaa", "1");
map.put("ccc", "3");
map.put("aaa", "1X");
final var keys = map.keySet().stream().toList();
assertEquals(keys.get(0), "bbb");
assertEquals(keys.get(1), "ddd");
assertEquals(keys.get(2), "aaa");
assertEquals(keys.get(3), "ccc");
}
EnumMap
Java에 특화된 자료구조로 enum을 key로하는 Map을 사용할 때 사용할 수 있는 구현체이다.
@Test
void EnumMap_enum을_key로_사용() {
final var map = new EnumMap<DayOfWeek, String>(DayOfWeek.class);
map.put(DayOfWeek.SATURDAY, DayOfWeek.SATURDAY.name());
map.put(DayOfWeek.SUNDAY, DayOfWeek.SUNDAY.name());
map.put(DayOfWeek.MONDAY, DayOfWeek.MONDAY.name());
map.put(DayOfWeek.TUESDAY, DayOfWeek.TUESDAY.name());
map.put(DayOfWeek.WEDNESDAY, DayOfWeek.WEDNESDAY.name());
map.put(DayOfWeek.THURSDAY, DayOfWeek.THURSDAY.name());
map.put(DayOfWeek.FRIDAY, DayOfWeek.FRIDAY.name());
final var keys = map.keySet().stream().toList();
assertEquals(keys.get(0), DayOfWeek.MONDAY);
assertEquals(keys.get(1), DayOfWeek.TUESDAY);
assertEquals(keys.get(2), DayOfWeek.WEDNESDAY);
assertEquals(keys.get(3), DayOfWeek.THURSDAY);
assertEquals(keys.get(4), DayOfWeek.FRIDAY);
assertEquals(keys.get(5), DayOfWeek.SATURDAY);
assertEquals(keys.get(6), DayOfWeek.SUNDAY);
}
내부적으로 enum key와 그에 대응하는 value를 Array로 관리하기 때문에 빠르게 데이터 처리를 할 수 있다는 특징이 있다.
Set
Set은 중복된 데이터를 허용하지 않는 자료구조이다.
HashSet
HashSet은 hash table 기반으로 중복된 데이터를 허용하지 않는 Set 구현체이다.
그리고 저장된 데이터는 특정한 순서를 보장하지 않는다.
@Test
void HashSet_순서_보장_X() {
final var set = new HashSet<String>();
set.add("bbb");
set.add("ddd");
set.add("aaa");
set.add("ccc");
set.add("aaa");
for (final var element : set) {
System.out.println(element);
}
}
앞서 hash table 기반이라고 하였는데 내부적으로 HashMap을 필드로 갖고 있고, Set의 기능을 구현할 때 이 HashMap을 사용한다.
TreeSet
TreeSet은 내부적으로 Tree를 사용하여 데이터를 관리하는 Set으로, 이 Tree를 통해 데이터를 정렬한다는 특징이 있다.
아래 예제의 경우 String을 사용하였기 때문에 abc 순으로 데이터가 정렬된 것을 확인할 수 있다.
@Test
void TreeMap_element를_기준으로_정렬() {
final var set = new TreeSet<String>();
set.add("bbb");
set.add("ddd");
set.add("aaa");
set.add("ccc");
final var elements = set.stream().toList();
assertEquals(elements.get(0), "aaa");
assertEquals(elements.get(1), "bbb");
assertEquals(elements.get(2), "ccc");
assertEquals(elements.get(3), "ddd");
}
TreeSet에서 TreeMap을 Tree로 사용한다.
LinkedHashSet
LinkedHashSet은 데이터 입력 순서를 보장하는 Set 구현체이다.
여기서 주의할 점은 동일한 값을 추가하는 경우, 기존에 있던 값의 순서를 그대로 사용한다는 것이다.
@Test
void LinkedHashSet_입력_순서_보장() {
final var set = new LinkedHashSet<String>();
set.add("bbb");
set.add("ddd");
set.add("aaa");
set.add("ccc");
set.add("aaa");
final var elements = set.stream().toList();
assertEquals(elements.get(0), "bbb");
assertEquals(elements.get(1), "ddd");
assertEquals(elements.get(2), "aaa");
assertEquals(elements.get(3), "ccc");
}
LinkedHashSet은 HashSet의 서브 클래스로 내부적으로 LinkedHashMap을 사용하여 데이터의 입력 순서를 보장한다.
EnumSet
Java에 특화된 자료구조로 enum을 element로 Set을 사용할 때 사용할 수 있는 Set 구현체이다.
@Test
void EnumSet_enum을_element로_사용() {
final var set = EnumSet.noneOf(DayOfWeek.class);
set.add(DayOfWeek.SATURDAY);
set.add(DayOfWeek.SUNDAY);
set.add(DayOfWeek.MONDAY);
set.add(DayOfWeek.TUESDAY);
set.add(DayOfWeek.WEDNESDAY);
set.add(DayOfWeek.THURSDAY);
set.add(DayOfWeek.FRIDAY);
final var elements = set.stream().toList();
assertEquals(elements.get(0), DayOfWeek.MONDAY);
assertEquals(elements.get(1), DayOfWeek.TUESDAY);
assertEquals(elements.get(2), DayOfWeek.WEDNESDAY);
assertEquals(elements.get(3), DayOfWeek.THURSDAY);
assertEquals(elements.get(4), DayOfWeek.FRIDAY);
assertEquals(elements.get(5), DayOfWeek.SATURDAY);
assertEquals(elements.get(6), DayOfWeek.SUNDAY);
}'Java & Kotlin > Java' 카테고리의 다른 글
| BigDecimal이 소수를 다루는 방법 (0) | 2022.12.08 |
|---|---|
| jabba global JDK 설정하기 (0) | 2022.04.09 |
| gradle multi module test 속도를 높여보자 (with parallel) (1) | 2021.07.29 |
| JUnit5 - @TestInstance에 대해 알아보자 (0) | 2021.07.25 |
| Servlet Filter의 response의 PrintWriter를 close 해야할까? (0) | 2021.02.24 |
댓글