📚 Set

Set이란 수학에서의 유한 집합을 구현한 인터페이스로, 저장하는 값들의 순서가 존재하지 않으며 중복되지 않는다는 특징이 있다.

• 데이터 비순차적으로 저장하는 집합 자료구조
• 삽입한 데이터가 순서대로 저장되지 않음 (LinkedHashSet 제외)
• 중복 삽입 불가능, 동일한 값이 삽입되면 무시
• Fast Lookup이 필요할 때 주로 사용됨

💡 Fast Lookup이란?
데이터를 검색할 때 빠른 시간 안에 원하는 값을 찾을 수 있는 성능적 특성

List 구현체는 검색(contains()) 시 시간 복잡도가 최악의 경우 O(N)이 걸리지만, HashSet이나 LinkedHashSet 같은 해시 기반 자료구조는 검색 시 평균 O(1)의 시간 복잡도를 가진다.

1️⃣ HashSet

	public class HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    	private transient HashMap<E, Object> map; // HashMap 사용
    	private static final Object PRESENT = new Object(); // dummy 객체

    	public boolean add(E e) {
        	return map.put(e, PRESENT) == null; // 값이 존재하지 않는다면 넣기
    	}
        
        ...
	}

• 내부적으로 HashMap 사용

• add() 시 원소는 HashMap의 key로 저장되며, value는 항상 dummy 객체

  • 불필요한 객체 생성을 막기 위해 PRESENT라는 공용 객체 하나만 생성해서 재사용 => 성능 측면에서 이점

• 삽입 순서나 정렬 순서를 보장하지 않음

• 검색/삽입/삭제 평균 시간 복잡도는 O(1)

• 중복을 허용하지 않으며, equals()와 hashCode()를 기준으로 중복 판단

  • add() 시 HashMap의 put()이 호출되며 이 로직에서 중복 판단

❗ Set의 add()에서 알 수 있는 것

우리가 잘 알고 있다시피 Map은 동일한 키를 삽입할 경우 값을 덮어쓰지만, Set은 내부적으로 Map을 쓰지만 덮어쓰지 않는다. 즉, 해당 행위를 무시한다.

Map의 put()은 같은 key가 있을 경우 원래 존재하는 값을 반환하는데, Set의 add()는 이 반환 값을 가지고 null인지 아닌지를 판별한 뒤 값을 넣기 때문이다!

2️⃣ TreeSet

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m; // NavigableMap 사용
    private static final Object PRESENT = new Object();
    
    public TreeSet() {
        this(new TreeMap<>()); // 내부적으로 TreeMap 사용
    }
	
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    
    ...
}

• 내부적으로 Red-Black Tree 기반의 NavigableMap의 구현체 TreeMap 사용

• 요소들을 자동으로 정렬된 상태로 유지

The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

TreeSet 공식 문서에 따르면 요소들은 기본적으로 자연 순서(숫자 오름차순, 문자열 사전순)로 정렬되며, 생성자에서 Comparator를 제공하면 그것을 기준으로 정렬된다고 한다.

• 삽입/삭제/검색 평균 시간 복잡도는 O(log N) -> Red-Black Tree를 사용하기 때문

• 중복 허용을 허용하지 않으며, compareTo() 또는 compare() 기준으로 중복 판단

  • 기본 생성자면 Comparable의 compareTo() 사용 / 생성자에 Comparator 넘기면 compare() 사용

3️⃣ LinkedHashSet

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {

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

• 내부적으로 LinkedHashMap 사용

  • LinkedHashSet은 HashSet을 상속 받고 있으며, HashSet의 아래 생성자를 super()를 통해 재정의하고 있다.

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

• HashMap처럼 데이터를 저장하지만, 이중 연결 리스트로 삽입 순서 유지

• 삽입 순서를 유지하여 add()한 순서대로 순회 가능

  • 이미 존재하는 요소를 다시 add() 해도 순서는 바뀌지 않음

• 검색/삽입/삭제 평균 시간 복잡도는 O(1)

• 중복 허용을 허용하지 않으며, HashSet처럼 equals()와 hashCode()를 기준으로 중복 판단

🤔 LinkedHashSet은 내부적으로 LinkedHashMap을 사용하는데 그럼 LRU 캐시를 구현할 수 없을까?

LinkedHashMap

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

LinkedHashMap은 생성 시 accessOrder를 입력 받아 접근 순서를 보장할지 결정한다. (입력 받지 않는다면 기본이 false) 또한 removeEldestEntry() 메서드를 사용해서 특정 제한(크기 제한 등)이 되었을 때 가장 오래된 엔토리를 자동으로 제거할 수도 있다. => LRU 캐시 구현 가능

반면에 LinkedHashSet은 내부적으로는 LinkedHashMap을 사용하지만 accessOrder를 설정할 수 있는 생성자를 제공하지 않고, removeEldestEntry() 메서드도 오버라이드 할 수 없다. => 접근 순서 기반 정렬이나 LRU 캐시 기능 제공 X

HashSet vs TreeSet vs LinkedHashSet

항목	HashSet	TreeSet	LinkedHashSet
저장 구조	해시 테이블	이진 탐색 트리 (Red-Black Tree 기반)	해시 테이블 + LinkedList
정렬 여부	X	오름차순 자동 정렬 (Comparator 사용 가능)	입력 순서 유지
중복 허용 여부	X	X	X
null 허용 여부	1개 허용	가능 (정렬 시 첫 번째로 위치)	1개 허용
속도 (일반)	가장 빠름 O(1)	느림 O(log n)	중간 O(1) (순서 관리로 약간 느림)
정렬 기준 설정	불가능	가능 (Comparable, Comparator 사용)	불가능
순서 유지 여부	X	정렬 순서 유지	입력 순서 유지
사용 예시	빠른 검색/삽입/삭제가 필요한 경우	정렬된 집합이 필요할 때	순서대로 저장하며 빠른 작업이 필요할 때

	hashSet.add(100);
    hashSet.add(5);
    hashSet.add(83);
    hashSet.add(27);
    
	treeSet.add(100);
    treeSet.add(5);
    treeSet.add(83);
    treeSet.add(27);
    
	linkedHashSet.add(100);
    linkedHashSet.add(5);
    linkedHashSet.add(83);
    linkedHashSet.add(27);

HashSet과 TreeSet, LinkedHashSet에 위와 같이 값을 넣는다면 for(int num : set) System.out.print(num);은 어떤 순서로 출력될까?

HashSet 출력 : 5 100 27 83
TreeSet 출력 : 5 27 83 100
LinkedHashSet 출력 : 100 5 83 27

먼저 HashSet은 순서가 정해져 있진 않지만, JVM 버전과 해시 함수, 버킷 크기에 따라 순서가 다를 수 있다. 즉, 한 번 실행해서 나온 동일 JVM에서는 대부분 동일하게 출력된다.

TreeSet은 따로 정렬 조건을 주지 않는다면 기본적으로 오름차순으로 출력된다.

LinkedHashSet은 입력된 순서를 유지하기 때문에 입력한 순서대로 출력된다.