23, 24장. 자바랭 다음으로 많이 쓰는 애들은 컬렉션 - Set, Queue, Map

💡 해당 글은 『자바의 신 3판』을 복습하며 도서의 내용과 본인의 주관적인 생각을 정리한 글입니다.

☁️ 내용정리

Set

public interface Set<E> extends Collection<E>

All Superinterfaces:
Collection<E>, Iterable<E>

All Known Subinterfaces:
EventSet, NavigableSet<E>, SequencedSet<E>, SortedSet<E>

All Known Implementing Classes:
AbstractSet, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, 
CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, 
LinkedHashSet, TreeSet

Set은 순서에 상관없이 어떤 데이터가 존재하는지를 확인하기 위한 용도로 많이 사용된다.

원소가 중복괴는 것을 방지하고, 원하는 값이 포함되어 있는지 확인하는 것이 주 용도이다.

Set 인터페이스를 구현하는 주요 클래스는 아래와 같다.

• HashSet: 내부적으로 hashMap을 사용, hashCode를 통한 데이터 저장, 순서를 보장하지 않음
• TreeSet: 내부적으로 TreeMap을 사용, 레드-블랙 tree를 통한 값 저장, 값에 의한 순서를 보장함
• LinkedHashSet: 내부적으로 LinkedHashMap을 사용, 입력에 의한 순서를 보장함

HashSet 과 LinkedHashSet은 저장할 때의 시간 복잡도는 O(n)이다. 하지만 레드-블랙 트리를 사용하여 구현한 TreeSet은 O(logN)의 시간복잡도를 가진다.

 

Load Factor

Load Factor란 (데이터의 개수) / (저장 공간)을 의미한다. 로드 팩터가 높을수록 해시 테이블이 가득 찬 상태라는 의미이고 이는 해시 충돌이 일어날 가능성이 높은 상태이다.

데이터의 개수가 증가하여 (데이터의 개수) / (저장 공간) 이 loadFactor 변수 값에 도달하는 경우, 저장 공간의 크기가 증가하고, 해시 재정리 작업을 해야한다. 이는 성능에 영향을 끼칠 수 있다.

 

Map

public interface Map<K, V>

All Known Subinterfaces:
Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>,
 NavigableMap<K,V>, SequencedMap<K,V>, SortedMap<K,V>

All Known Implementing Classes:
AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, 
ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, Headers, 
IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, 
Provider, RenderingHints, SimpleBindings, TabularDataSupport, 
TreeMap, UIDefaults, WeakHashMap

Map은 Key-Value 쌍으로 이루어진 원소를 저장하기 위한 자료구조이다.

모든 데이터는 Key와 Value가 존재하며, 키가 없이 값만 저장되거나, 값이 없이 키만 존재하는 경우는 있을 수 없다. 키는 Map에서 중복될 수 없다. 값은 중복이 가능하다.

Map을 구현하는 대표적인 클래스는 아래와 같다.

• HashMap
• TreeMap
• LinkedHashMap
• Hashtable

 

Map 과 Hashtable

Hashtable도 Map인터페이스를 구현하긴 하지만 일반적으로 Map을 구현한 클래스들과는 조금 다른점이 있다.

Map은 Collection view를 사용한다. Key들의 집합을 Set통해 Value들의 리스트를 Collection을 통해 반환하여 외부에서 컬렉션을 통해 값을 확인할 수 있는 기능을 제공한다.

Hashtable은 collection view 외에도 Enumeration 객체를 통해서 데이터를 처리한다.

HashMap과 Hashtable의 차이도 존재한다. HashMap은 Key 혹은 Value에 null을 저장할 수 있는 반면, Hashtable은 불가능하다. Hashtable은 thread-safe한 반면, HashMap은 그렇지 않다.

왜 이러한 차이를 보이는 것일까?

Collection은 JDK 1.2에서 추가되었다. HashMap과 TreeMap도 이 때 만들어져 사용되고 있다.

하지만 Hashtable은 JDK 1.0부터 만들어져 사용되고 있었다. 따라서 본인보다 늦게 등장한 Map에 맞추어 보완된 클래스이기 때문에 이러한 차이가 발생한다.

 

HashMap

HashMap은 HashSet에서 사용되는 클래스이므로, HashSet의 내용과 거의 동일하다.

HashMap에서 동일한 키와 값이 존재하는 상황에서 키에 새로운 값을 할당하면 값을 덮어쓰여진다.

TreeMap, LinkedHashMap 또한 각각의 Set과 설명이 동일하다.

 

Properties

Properties 클래스는 Hashtable을 확장한다. 각종 속성 값들을 저장하니 아래의 링크를 통해 사용하자.

Properties (Java SE 21 & JDK 21)

 

Queue

FIFO의 용도로 사용하기 위한 자료구조이다.

public interface Queue<E> extends Collection<E>

All Known Subinterfaces:
BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes:
AbstractQueue, ArrayBlockingQueue, **ArrayDeque**, ConcurrentLinkedDeque, 
ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, 
LinkedBlockingQueue, **LinkedList**, LinkedTransferQueue, PriorityBlockingQueue, 
**PriorityQueue**, SynchronousQueue

Queue는 먼저 온 사용자가 먼저 자원을 획득하는 구조를 위해 사용하곤 한다.

구현체로는 LinkedList, PrioriyQueue, ArrayDeque를 주로 사용한다.

 

Linked List

LinkedList는 List와 Queue를 모두 구현한다.

 

LinkedList는 비슷한 이름의 ArrayList와 많이 비교되곤 한다. ArrayList는 배열을 가지며 동적으로 그 크기를 변경하며 데이터를 저장하는 반면, LinkedList는 내부에 선언된 private static nested class인 Node를 사용하여 구현한다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    // ...
}

각 노드는 item이라는 값을 가지고, 이전, 다음 노드의 참조를 가진다.

LinkedList는 리스트의 중간에 값을 추가히거나 제거할 때, ArrayList보다 효율적이다.

이전, 다음 노드의 참조만 수정하면 되기 때문이다. 이는 O(1)시간이 소요된다.

하지만 ArrayList는 중간에 값을 추가하거나 제거하기 위해 해당 값으로부터 뒤의 모든 값의 인덱스를 1씩 증가시키거나 1씩 감소시켜야 하기에 O(n)시간이 소요되는 작업이 필요하다.

 

탐색을 위한 메서드

• ListIterator<E> listIterator(int index): index부터 데이터를 탐색하는 ListIterator를 반환
• Iterator<E> descendingIterator(): 데이터를 끝에서부터 탐색하는 Iterator를 반환

 

---

 

☁️ 내 생각

hash를 통해 데이터를 저장하는 컬렉션을 사용할 때 유의해야할 점

사용자가 선언한 클래스를 컬렉션의 요소로 사용하는 경우에 HashSet, HashMap, HashTable, LinkedHashMap 등 hash를 통해 데이터를 저장하는 컬렉션을 사용해야 한다면 유의해야할 점이 있다.

hashCode() 와 equals() 를 재정의해야 한다는 점이다.

 

equals() 와 hashCode()를 재정의해야 하는 이유

hash를 사용하는 컬렉션에서 오동작할 수 있는 가능성을 제거하기 위해서라고 생각한다.

HashMap에 데이터를 저장하는 동작에 대한 내부 코드는 아래와 같다.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {// ...

put 동작 시 먼저 key의 해시코드 값을 비교한다. 해시코드 값이 같으면 equals를 사용하여 동등한지 판단한다.

즉, hashCode 반환값이 다르다면 equals 메서드를 호출하기도 전에 다른 객체로 인식한다는 의미이다.

 

반대로 hashCode가 동일하면 무조건 equals 메서드를 호출한다. 이렇게 equals와 hashCode는 hash를 사용하는 컬렉션에서 성능에 영향을 줄 수 있는 메서드이다.

 

key를 통해 element를 찾는 작업도 동일하게 이루어진다.

그 이후, <K, V>를 가지는 Node의 배열인 table에 hashCode()값을 인덱스로 사용하여 저장한다.

 

만약 내가 선언한 클래스는 특정한 하나의 인스턴스변수 값만 같다면 동등한 객체로 판단하고 싶어서 equals를 재정의 했다. 그런데 hashCode를 재정의하지 않았다. 이러한 상황에 hashMap의 키로 해당 클래스를 저장하면 어떠한 문제가 발생할까?

문명히 equals를 통해 동등하다고 판단되는 객체임에도 불구하고 Map은 Key의 중복을 판단하기 위해 hashCode부터 비교한다.

따라서 대부분은 재정의한 equals를 실행하기도 전에 다른 객체라고 판단되어 독립적인 Key로 사용되고 아주 가끔은 운 좋게 hashCode가 동일하여 같은 Key로 사용될 것이다. 아주 난장판이 되는것이다.

 

만약 HashMap의 요소가 hashCode를 재정의하여 모두 같은 값을 반환한다고 가정해보자.

모든 요소는 모두 같은 인덱스에 저장되고, 이러한 해시충돌을 chaining 방식을 통해 해결하여 linkedList 형식으로 저장될 것이다. 이는 탐색 속도를 O(1)에서 O(n)으로 낮출 수 있으므로 hashCode를 재정의 하는 경우 신중해야 한다.

 

좋은 해시란 최대한 중복 값이 발생하지 않고 고르게 생성되는 값이라고 생각한다.

 

---

 

☁️ 질문

• Set은 어떤 상황에서 사용되는가?
  • 특정 데이터가 존재하는지를 확인하기 위해 사용된다.
• HashSet, TreeSet, LinkedHashSet에 대해 설명해달라.
  • HashSet은 내부적으로 HashMap을 통해 구현되어 있으며, hashCode 값을 인덱스로 사용해 데이터를 저장하고 탐색한다.
  • TreeSet은 내부적으로 TreeMap을 통해 구현되어 있으며, 값에 따른 정렬을 지원한다. 정렬은 Red-Black Tree를 사용하여 구현한다. 탐색 속도는 O(logN)이다.
  • LinkedHashSet은 내부적으로 LinkedHashMap을 통해 구현되어 있으며, 데이터가 저장되는 순서를 보장한다.