[Java] Collection에 대해 알아보기(2) - Set

Erin Lee·2024년 3월 7일

Java

Set Interface

Set 인터페이스는 List 인터페이스와 다르게 데이터의 저장 순서가 유지되지 않으며 데이터의 중복을 허용하지 않는 집합 구조이다.

Set 인터페이스를 구현하는 클래스로는 HashSet, LinkedHashSet, SortedSet 인터페이스를 상속받은 TreeSet가 있다.

HashSet

Set 인터페이스를 상속받은 클래스로 Hashtable을 기반으로 구현하는 클래스(*HashTable 개념은 Map인터페이스에 정리할 예정)이다.

HashSet 클래스의 내부를 보면 HashSet 생성자에서 HashMap을 가리키고 있으며 add나 remove같이 기본 함수들이 HashMap의 메서드를 사용한다.

그래서 아래와 같이 HashSet의 생성자를 보면 HashSet이 갖고 있는 map 변수의 값을 HashSet 클래스의 객체가 생성될 때 HashMap 타입을 참조하게 하도록 설정한 것이다.

즉, HashSet은 HashMap과 비슷한 구조를 가진다고 할 수 있다.

HashSet vs HashMap

데이터를 추가하는 add() 함수도 받은 인자를 키로, Object를 참조하고 있는 객체를 값으로 put() 메서드로 보내고 있다. → 즉 Map의 형태

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashSet은 내부적으로 동기화를 제공하지 않기 때문에 외부에서 동기화를 해줘야한다. → 그렇다는 것은 HashMap도 동기화를 제공하지 않은 것을 알 수 있다!

Collections.synchronizedSet() 메서드

synchronizedList() 메서드와 동일한 흐름으로 구현된다.

Collections.synchronizedSet(HashSet 타입);

LinkedHashSet

HashSet 클래스를 상속받은 클래스로 HashSet에서 데이터의 저장 순서가 유지되는 특징이 추가된 구조로 구현된다.

LinkedHashSet의 생성자를 보면 부모 클래스인 HashSet의 생성자로 인자를 보내고 HashSet의 생성자는 LinkedHashMap을 참조하고 있다.

public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
}

↓

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

즉, LinkedHashSet 클래스도 LinkedHashMap 클래스와 같다고 할 수 있다.

→ LinkedHashSet vs LinkedHashMap

LinkedHashSet과 HashSet 데이터 출력 비교해보자

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;

public class LinkedHashSetTest {
    public static void main(String[] args) {

        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("a");
        hashSet.add("b");
        hashSet.add("c");
        hashSet.add("d");
        hashSet.add("e");
        hashSet.add("f");
        hashSet.add("x");
        hashSet.add("y");
        hashSet.add("z");
        hashSet.add("ㄱ");
        hashSet.add("ㄴ");
        hashSet.add("ㄷ");
        hashSet.add("ㄹ");

        
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();

        linkedHashSet.add("a");
        linkedHashSet.add("b");
        linkedHashSet.add("c");
        linkedHashSet.add("d");
        linkedHashSet.add("e");
        linkedHashSet.add("f");
        linkedHashSet.add("x");
        linkedHashSet.add("y");
        linkedHashSet.add("z");
        linkedHashSet.add("ㄱ");
        linkedHashSet.add("ㄴ");
        linkedHashSet.add("ㄷ");
        linkedHashSet.add("ㄹ");

        Iterator<String> it1 = hashSet.iterator();
        Iterator<String> it2 = linkedHashSet.iterator();
        
        for(;it1.hasNext();) {
            System.out.print(it1.next() + " "); // a b c d e f ㄱ ㄴ ㄷ x y ㄹ z
        }

        System.out.println(" ");

        for(;it2.hasNext();) {
            System.out.print(it2.next() + " "); // a b c d e f x y z ㄱ ㄴ ㄷ ㄹ -> 추가한 순서대로 출력된다.
        }
    }

    //추가로 확인한 점!
    //데이터 타입으로 Integer을 넣고 Integer 타입을 출력하였을 때에는 HashSet도 순서대로 나왔다.
}

TreeSet

SortedSet 인터페이스를 상속받았으며 Tree구조로 구현되는 인터페이스다.

SortedSet Interface

SortedSet 인터페이스는 Set 인터페이스를 상속받았으며 데이터들끼리 비교를 통해 정렬을 구현하는 Comparator 인터페이스를 구현함으로써 정렬된 데이터 구조를 구현한다.

헷갈렸던 부분!

여기서 정렬된 데이터 구조라는 것은 데이터의 저장 순서를 유지한다는 것이 아니다!

Comparator의 정렬 기준으로 정렬이 되는 것을 말한다.

//Comparator Interface
public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}

위 코드는 Comparator 인터페이스에서 Int 타입을 비교하는 메서드이다.

return 값을 보면 Integer.compare 메서드로 인자값을 넘겨주고 Integer의 compare 메서드를 통해 두 값을 비교하여 결과를 내놓는다.

//Integer class
public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

(람다나 ToIntFunction 등등까지 들어가는 것은 범위를 초과하는 것 같아서 흐름만 먼저 파악하였다.)

import java.util.HashSet;
import java.util.SortedSet;
import java.util.TreeSet;

public class SortedSetTest {

    public static void main(String[] args) {
        
        HashSet<Integer> hashSet = new HashSet<>();

        hashSet.add(1);
        hashSet.add(10);
        hashSet.add(5);
        hashSet.add(3);
        hashSet.add(7);

        SortedSet<Integer> sortedSet = new TreeSet<>(hashSet);

        System.out.println(sortedSet); // [1, 3, 5, 7, 10] 정렬된 결과로 나왔다.

    }
    
}

→ HashSet에 넣은 데이터를 SortedSet을 통해 정렬되어 추출되게 하였다.

TreeSet 특징

SortedSet 인터페이스를을 구현하여 데이터가 정렬된 구조를 가지고 있다.
데이터 저장 시 이진 탐색 트리 구조 기반으로 저장된다.
동기화를 내부적으로 구현하지 않아 외부에서 구현해줘야 한다.
데이터의 추가 혹은 삭제가 일어날 때 수정 작업 후 정렬 작업이 이뤄지기 때문에 HashSet보다 느리다.

여기서 이진 탐색 트리 구조(Binary Search Tree)란?

이진 트리는 ‘노드’로 이루어져 있으며 각 노드는 최대 2개까지만 자식 노드를 가질 수 있는 구조이다.

TreeSet은 이진탐색트리(Binary Search Tree) 형태로 이진 트리의 한 종류로 이진 트리와 동일한 구조로 데이터를 저장한다.

이때 첫번째로 저장한 값이 root 노드가 되고 root 노드를 시작으로 왼쪽 노드는 부모 노드보다 더 작은 값, 오른쪽 노드는 부모 노드보다 더 큰 값이 들어가는 구조이다.

이진 탐색 트리는 노드끼리의 비교 작업이 수행되는 방식이다.

그렇기 때문에 데이터의 삭제나 추가 작업이 일어날 때마다 데이터의 비교 작업 처리가 진행되어 정렬되기 때문에 느리다.

하지만 크기에 따라 정렬된 구조이기 때문에 크기 비교에 따른 검색 작업은 빠르다.

TreeSet 동기화

TreeSet 클래스는 동기화가 되지 않기 때문에 HashSet과 동일하게 synchronizedSet() 메서드를 사용하여 동기화 작업을 해줘야 한다.

Collections.synchronizedSet(TreeSet 타입);

HashSet vs TreeSet

	HashSet	TreeSet
공통점	데이터의 저장 순서가 유지되지 않는다.
	데이터 중복 허용이 되지 않는다.
차이점	데이터의 정렬 작업이 없다.	데이터의 정렬 작업이 이뤄진다.
	Hashtable 기반이기 때문에 검색 작업이 빠르다.	이진 탐색 트 구조 기반이기 때문에 데이터 검색이 빠르다. 하지만 Hashtable 기반 HashSet보다는 느리다.
		데이터가 삭제, 수정될 때마다 노드 정렬이 이뤄지기 때문에 작업이 느리다.
	null 값이 허용된다.	null 값이 허용되지 않는다.