Collection & Map - 3-0. Set & Map 개요

• 이번 시리즈에서는 Java의 Collection과 Map에 대해 소개합니다.
  • 프레임워크의 기반이 되는 자료구조에 대한 개념은 따로 시리즈로 작성할 것이고, 본 시리즈에서는 Java에서 제공하는 자료구조들과 그에 따른 메서드들을 정리할 것입니다.

0. Java의 Collection Framework와 Map Interface

• Java에서는 데이터 구조와 알고리즘을 지원하는 강력한 표준 라이브러리를 제공하며, 이 중 Collection Framework와 Map은 데이터 관리와 처리의 핵심적인 역할을 합니다.

• 위 이미지는 주로 쓰이는 Collection Framework와 Map Interface의 상속 및 구현 관계를 제가 직접 그려본 것입니다.
  • 회색으로 표시된 Vector, Stack, Hashtable은 Java 초창기에 만들어져서 하위 버전 호환을 위해 남겨진 Legacy Class들입니다.
    • 구조적인 문제들이 있어서 현재는 더이상 업데이트되지 않고 거의 쓰이지 않기 때문에 본 시리즈에서도 따로 정리하진 않을 예정입니다.
  • Collection Framework
    • List 구현체 : ArrayList, LinkedList
    • Queue 구현체 : PriorityQueue, ArrayDeque, LinkedList
    • Deque 구현체 : ArrayDeque, LinkedList
    • Set 구현체 : HashSet, LinkedHashSet, TreeSet
  • Map Interface 구현체 : HashMap, LinkedHashMap, TreeMap

• 이번 포스팅에서는 Collection Framework의 하위 인터페이스인 Set 인터페이스와 Map 인터페이스의 개요를 먼저 살펴보도록하고, 다음 포스팅부터 구체적인 구현체들과 동작 원리를 살펴보도록 하겠습니다.

1. Set 인터페이스

1.1. Set 인터페이스란?

• Set은 중복을 허용하지 않는 요소의 집합을 표현하는 Java의 인터페이스입니다.
  • 수학적 집합과 유사하게, 한 번에 하나의 고유한 인스턴스만 포함할 수 있으며, 중복된 요소는 포함되지 않습니다.
  • Set에 포함된 모든 요소는 고유하며, 요소 간의 중복 여부는 equals()와 hashCode() 메서드를 기준으로 판단됩니다.
• 따라서 Set에 포함되는 요소들은 반드시 equals()와 hashCode()를 오버라이딩하여 그 고유성을 정의해야 합니다.
  • 이 두 메서드를 오버라이딩하지 않으면, 기본적으로 객체의 참조 주소값을 기준으로 중복 여부를 판단하게 되어, 예상치 못한 중복 요소가 포함될 수 있습니다.

Set의 주요 특징

• 중복 허용 안 함: Set의 가장 중요한 특징은 중복 요소를 허용하지 않는 것입니다.
  • 이로 인해, 추가하려는 요소가 이미 존재하는 경우 삽입되지 않으며, 중복 요소의 추가 시도는 무시됩니다.
• 순서 보장 없음: Set은 순서를 보장하지 않는 자료구조입니다. 요소들이 삽입된 순서와 상관없이 저장되며, 정해진 순서 없이 관리됩니다.
  • 하지만, 예외적으로 LinkedHashSet과 같은 구현체는 삽입 순서를 유지하는 특성을 가집니다.
• 효율적인 중복 제거: Set은 내부적으로 중복을 제거하면서 저장하기 때문에, 대규모 데이터 처리 시 중복 요소 제거가 필요한 상황에서 효율적으로 사용할 수 있습니다.

Set 인터페이스의 대표적인 메서드

• add(E e): Set에 요소를 추가합니다.
  • 추가하려는 요소가 중복일 경우 추가되지 않으며, false를 반환합니다.
• contains(Object o): 특정 요소가 Set에 포함되어 있는지 확인합니다.
• remove(Object o): 특정 요소를 Set에서 제거합니다.
• size(): Set에 포함된 요소의 개수를 반환합니다.
• isEmpty(): Set이 비어있는지 확인합니다.

1.2. Set 구현체

• Java에서 Set 인터페이스는 다양한 구현체로 제공되며, 각각의 구현체는 데이터의 저장 방식과 성능에 차이가 있습니다. 주요 구현체는 다음과 같습니다.

1.2.1. HashSet

• HashSet은 가장 일반적인 Set 구현체로, 해시 테이블을 사용하여 요소를 저장하고 관리합니다.
  • 중복을 허용하지 않으며, 순서를 보장하지 않는 Set입니다.
  • 요소들은 해시 값을 기반으로 저장되기 때문에, 삽입 및 검색의 시간 복잡도는 평균적으로 O(1) 입니다.
  • HashSet은 정렬되지 않으며, 요소의 순서는 삽입된 순서와 관계없이 저장됩니다.

1.2.2. LinkedHashSet

• LinkedHashSet은 HashSet의 확장으로, 삽입 순서가 유지되는 Set 구현체입니다.
  • 요소가 삽입된 순서대로 저장되며, 중복을 허용하지 않는 점은 HashSet과 동일합니다.
  • 이중 연결 리스트를 사용해 삽입된 순서를 유지하며, 해시 테이블을 통해 효율적인 검색 성능을 유지합니다.
  • 따라서 순서를 보존하면서도 빠른 검색이 필요한 경우에 적합한 Set 구현체입니다.

1.2.3. TreeSet

• TreeSet은 이진 탐색 트리(레드-블랙 트리)를 기반으로 하는 Set 구현체로, 요소들을 정렬된 순서로 저장합니다.
  • 요소가 삽입되면 오름차순 또는 사용자 정의 정렬 기준에 따라 정렬되어 저장됩니다.
  • 중복을 허용하지 않으며, 요소가 추가될 때마다 자동으로 정렬이 이루어집니다.
  • 삽입, 삭제, 검색의 시간 복잡도는 O(log n) 입니다.
  • 정렬된 데이터를 필요로 하거나, 범위 기반 탐색이 필요한 경우에 사용됩니다.

1.2.4. EnumSet

• EnumSet은 특정 열거형(enum) 타입에 대한 모든 값을 Set으로 관리하는 특수한 Set 구현체입니다.
  • 모든 열거형 값들이 미리 알려져 있기 때문에, 매우 효율적으로 메모리를 사용합니다.
    • 내부적으로 비트 벡터(bit vector)로 구현되어 있어 메모리 소비가 적고 매우 빠릅니다.
  • EnumSet은 순서 보장이 가능하며, 모든 값이 고정된 상수라는 특성 덕분에 매우 빠른 성능을 제공합니다.
  • 주로 enum 타입의 데이터를 처리할 때 사용됩니다.
• EnumSet은 열거형(enum) 타입의 값들을 처리할 때 매우 유용한 자료구조로, 성능이 매우 중요한 경우에 종종 사용됩니다.
  • 하지만 특수한 경우에만 활용되며, 일반적인 프로그래밍에서는 자주 사용되지 않습니다.
  • 따라서 이 시리즈에서는 별도로 다루지 않겠습니다.

1.3. Set 인터페이스 메서드

• Set 인터페이스는 Collection에서 상속받은 메서드들을 사용하며, Set 인터페이스 만의 고유한 추가 메서드는 따로 없습니다.

Object 메서드

메서드	설명	반환값
equals(Object obj)	두 객체가 동일한지 비교	boolean
hashCode()	객체의 해시 코드를 반환	int
toString()	객체의 문자열 표현을 반환	String

Iterable 메서드

메서드	설명	반환값
iterator()	컬렉션의 요소를 순차적으로 탐색할 수 있는 Iterator 반환	Iterator<T>
forEach(Consumer<? super T> action)	각 요소에 대해 주어진 동작을 수행	void
spliterator()	요소의 분할 가능한 반복자를 반환	Spliterator<T>

Collection 메서드

메서드	설명	반환값
add(T e)	컬렉션에 요소를 추가	boolean
addAll(Collection<? extends T> c)	주어진 컬렉션의 모든 요소를 추가 (합집합 연산)	boolean
clear()	컬렉션의 모든 요소를 제거	void
contains(Object o)	컬렉션에 특정 요소가 포함되어 있는지 확인	boolean
containsAll(Collection<?> c)	주어진 컬렉션의 모든 요소가 이 컬렉션에 포함되어 있는지 확인 (포함 연산)	boolean
isEmpty()	컬렉션이 비어있는지 확인	boolean
remove(Object o)	컬렉션에서 특정 요소를 제거	boolean
removeAll(Collection<?> c)	주어진 컬렉션에 포함된 모든 요소를 이 컬렉션에서 제거 (차집합 연산)	boolean
retainAll(Collection<?> c)	이 컬렉션에 포함된 요소들 중 주어진 컬렉션에 있는 요소만 유지 (교집합 연산)	boolean
size()	컬렉션에 포함된 요소의 개수를 반환	int
toArray()	컬렉션의 요소를 배열로 반환	Object[] 또는 T[]
toArray(T[] a)	컬렉션의 요소를 주어진 배열에 맞게 반환	T[]

2. Map 인터페이스

2.1. Map 인터페이스란?

• Map은 Key-Value 쌍으로 데이터를 저장하는 자료구조로, 각 key는 고유해야 하며, 각각의 key는 하나의 value에 매핑됩니다.
  • Map은 중복된 Key를 허용하지 않으며, 하나의 Key에 대해 하나의 Value만 저장됩니다.
  • Map은 주로 빠르게 데이터를 검색하거나 Key를 기준으로 데이터를 관리할 때 유용하게 사용됩니다.

2.2. Entry

• Map.Entry<K, V>는 Map 인터페이스의 내부 인터페이스로, 하나의 Key-Value 쌍을 표현합니다.
  • Entry는 Map에 저장된 각 Key와 Value를 나타내는 객체로, Map의 요소를 다룰 때 사용됩니다.
  • Map을 순회할 때 Entry 객체를 통해 각 요소에 접근할 수 있으며, getKey(), getValue() 메서드를 사용해 Key와 Value를 가져올 수 있습니다.

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

// Entry로 Map 순회하기
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

2.3. Map의 주요 특징

• Key-Value 쌍: Map은 고유한 Key와 Key에 매핑된 Value로 데이터를 저장합니다.
• 중복된 Key 허용 안 함: 동일한 Key를 중복으로 추가하면, 기존의 Value가 덮어쓰여집니다.
• 빠른 검색: HashMap과 같은 해시 기반 Map 구현체는 Key를 기준으로 빠르게 검색이 가능합니다.

2.4. Map 인터페이스의 주요 구현체

2.4.1. HashMap

• HashMap은 해시 테이블을 사용하여 Key-Value 쌍을 저장하는 대표적인 Map 구현체입니다.
  • Key는 고유하며, 순서가 보장되지 않는 Map입니다.
  • 해시 함수를 기반으로 데이터를 저장하고 관리하기 때문에, 평균적으로 O(1) 시간 복잡도로 데이터를 검색할 수 있습니다.
  • 중복된 Key를 허용하지 않으며, Key가 null일 수도 있습니다.

2.4.2. LinkedHashMap

• LinkedHashMap은 삽입 순서가 유지되는 HashMap 구현체입니다.
  • 이중 연결 리스트를 통해 각 요소의 삽입 순서를 유지하며, 해시 기반의 검색 성능도 제공합니다.
  • 순서를 유지하면서도 해시 기반의 빠른 검색이 필요한 경우 적합한 구현체입니다.

2.4.3. TreeMap

• TreeMap은 이진 탐색 트리(레드-블랙 트리)를 기반으로 하는 Map 구현체로, Key가 정렬된 순서로 저장됩니다.
  • 기본적으로 오름차순으로 정렬되며, 사용자 정의 Comparator를 통해 정렬 기준을 변경할 수 있습니다.
  • Key의 순서가 중요한 경우에 적합하며, 검색, 삽입, 삭제의 시간 복잡도는 O(log n) 입니다.

2.4.4. EnumMap

• EnumMap은 EnumSet와 마찬가지로 특정 열거형(enum) 타입에 대한 모든 값을 Key-Value 쌍으로 관리하는 특수한 Map 구현체입니다.
• 이 또한 특수한 경우에 해당해서 이 시리즈에서는 자세히 다루진 않습니다.

2.5. Map 인터페이스의 메서드

• Map 인터페이스는 Object에서 상속된 메서드 외에도, Map의 Key-Value 구조를 다루기 위한 다양한 메서드를 제공합니다.

Object 메서드

메서드	설명	반환값
equals(Object obj)	두 객체가 동일한지 비교	boolean
hashCode()	객체의 해시 코드를 반환	int
toString()	객체의 문자열 표현을 반환	String

Map 메서드

메서드	설명	반환값
put(K key, V value)	Key와 Value를 Map에 추가	V (기존 값 반환 가능)
get(Object key)	Key에 해당하는 Value를 반환	V (없을 시 null)
remove(Object key)	Key에 해당하는 Entry를 삭제	V (기존 값 반환)
containsKey(Object key)	Key가 Map에 존재하는지 확인	boolean
containsValue(Object value)	특정 Value가 Map에 포함되어 있는지 확인	boolean
keySet()	Map의 모든 Key를 Set으로 반환	Set<K>
values()	Map의 모든 Value를 Collection으로 반환	Collection<V>
entrySet()	Map의 모든 Entry를 Set으로 반환	Set<Map.Entry<K, V>>
size()	Map에 저장된 Key-Value 쌍의 개수를 반환	int
isEmpty()	Map이 비어있는지 확인	boolean
clear()	Map의 모든 Entry를 삭제	void

3. Set & Map 비교

• Set과 Map은 Java의 Collection과 Map 프레임워크에서 각각 요소들의 집합과 키-값 쌍을 저장하는 구조로 사용됩니다.
  • 이 두 인터페이스는 서로 다른 목적으로 사용되지만, 내부적으로는 유사한 동작 원리를 가지고 있습니다.
• Set은 기본적으로 Map과 유사하게 동작하며, 값(value)이 없는 Map과 거의 같습니다.
  • 즉, Set의 요소들은 Map의 키(key) 역할을 하며, 중복을 허용하지 않는다는 특성을 공유합니다.

3.1. Set과 Map의 주요 차이점

• 데이터 저장 방식
  • Set은 중복을 허용하지 않는 요소들의 집합입니다. 각 요소는 고유하며, 오직 하나의 인스턴스만 포함될 수 있습니다.
  • Map은 키-값(Key-Value) 쌍으로 데이터를 저장합니다. 각 키는 고유하며, 동일한 키에 중복된 값을 할당할 수 없습니다.
• 구조적 차이
  • Set의 경우 단일 값을 저장하며, 그 값은 중복이 허용되지 않습니다.
  • Map은 고유한 키를 통해 여러 값을 관리하며, 키는 중복될 수 없지만 값은 중복될 수 있습니다.

3.2. Set과 Map의 내부 유사성

• Map에서 Set처럼 사용
  • Set은 내부적으로 키를 중심으로 데이터의 고유성을 보장합니다. 마찬가지로, Map에서 키가 고유하므로, Set은 Map에서 키만 사용하는 구조로 볼 수 있습니다.
  • 예를 들어, HashSet은 HashMap을 내부적으로 사용하여 중복 없는 값을 저장하며, HashMap에서는 각 키에 대해 값이 null로 저장됩니다.

3.3. Set과 Map의 메서드 유사성

• Set의 메서드들은 본질적으로 Map의 메서드들과 비슷한 구조를 가집니다.
  • Set.add() → Map.put(): Set에 요소를 추가할 때는 Map의 키를 추가하는 것과 동일한 원리로 작동합니다.
  • Set.contains() → Map.containsKey(): Set에서 특정 요소가 존재하는지 확인하는 메서드는 Map에서 키가 존재하는지 확인하는 것과 유사한 방식으로 동작합니다.
  • Set.remove() → Map.remove(): Set에서 요소를 삭제하는 메서드는 Map에서 키와 값을 함께 제거하는 방식과 유사합니다.

4. Set & Map의 내부 구현에 따른 분류

4.1. Hash 기반 Set & Map

• HashSet과 HashMap은 해시 테이블을 기반으로 한 자료구조로, 해시 함수를 통해 고유한 위치를 할당하여 빠르게 데이터를 저장하고 검색할 수 있는 구조입니다.
• 특징
  • 빠른 접근 속도: 평균적으로 O(1) 시간 복잡도로 삽입, 삭제, 검색이 이루어집니다.
  • 순서 보장 없음: 요소들이 삽입된 순서를 보장하지 않으며, 요소들이 해시 값을 기반으로 무작위로 분포됩니다.

4.2. Tree 기반 Set & Map

• TreeSet과 TreeMap은 이진 탐색 트리(레드-블랙 트리) 구조를 기반으로 하여 데이터를 정렬된 순서로 저장합니다.
• 특징
  • 정렬된 데이터 저장: 데이터가 항상 오름차순 또는 사용자 정의 기준에 따라 정렬된 상태로 저장됩니다.
  • 높은 탐색 비용: 삽입, 삭제, 검색의 시간 복잡도는 O(log n) 로, 해시 기반 자료구조에 비해 상대적으로 느리지만, 데이터가 정렬된 상태로 유지되므로 범위 검색에 유리합니다.

마무리

• 이번 포스팅에서는 Java의 Set과 Map 인터페이스의 개요를 살펴보았습니다.

• 두 자료구조는 중복을 허용하지 않는다는 공통된 특징을 가지며, 내부적으로는 유사한 동작 원리를 공유하고 있습니다.

  • Set은 Map의 키(key)처럼 동작하고, Map은 Key-Value 쌍으로 데이터를 관리하면서 데이터의 고유성을 보장합니다.
  • 또한, 자료구조의 특성에 따라 해시 기반과 트리 기반으로 나눌 수 있으며, 각각의 성능과 용도가 다릅니다.

• 다음 포스팅에서는 Hash 기반 Set과 Map 구현체들에 대해 더 깊이 다룰 예정입니다.

  • HashSet, HashMap, LinkedHashSet, LinkedHashMap의 구체적인 동작 원리와 성능 차이를 알아보고, 실제 사용 시 어떤 상황에서 유용한지 살펴보겠습니다.