99클럽 코테 스터디 9일차 TIL Set

LinkedHashSet

• HashSet 의 순서를 유지하는 버전
• Set 인터페이스의 구현클래스
• HashSet 의 모든 특성을 가지면서도, 추가적으로 요소가 추가된 순서대로 반복할 수 있따는 특징이 있음.
  LinkedHashSet 이 내부적으로 연결 리스트(Linked List) 를 사용하여 요소의 삽입 순서를 기록하기 때문

특징

• 중복이 안됨
  LinkedHashSet 은 동일한 요소의 중복 저장을 허용하지 않음. 각 요소는 집합 내에서 유일
• 삽입 순서 유지
  요소가 추가된 순서대로 요소를 반복할 수 있음. LinkedHashSet 이 요소를 내부적으로 어떤 순서로 저장하고 있는지를 나타냄.
• 빠른 접근 속도
  HashSet 과 마찬가지로, LinkedHashSet 도 해시 테이블을 기반으로 하므로, 요소의 추가, 삭제, 검색 작업이 매우 빠름. 단, HashSet 에 비해 약간 느릴 수 있음.
  삽입 순서를 유지하기 위한 추가적인 Linked List 관리 때문
• null 값 허용
  LinkedHashSet 은 하나의 null 값을 저장할 수 있음.

사용사례
중복을 허용하지 않으면서도 요소의 추가 순서를 유지해야 할 때 유용함.
사용자가 입력한 고유한 데이터 항목의 순서를 유지하면서 처리해야할 경우가 있음.

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

linkedHashSet.add("Apple");
linkedHashSet.add("Banana");
linkedHashSet.add("Cherry");
linkedHashSet.add("Apple"); // 중복 요소 무시

System.out.println("LinkedHashSet : " + linkedHashSet);

//요소 순서대로 출력
for(String fruit : linkedHashSet) {
    System.out.println(fruit);
}

linkedHashSet.remove("Banana");
System.out.println("After removal: " + linkedHashSet);

//요소의 존재 여부 확인
if(linkedHashSet.contains("Apple")) {
    System.out.println("LinkedHashSet contains Apple");
}

이 부분에서 LinkedHashSet 에 여러 과일 이름을 추가하고, 중복된 요소 Apple 을 추가하려하지만, LinkedHashSet 은 중복을 허용하지 않기 때문에 중복 요소는 무시됨.

추가된 순서대로 요소를 출력하면, LinkedHashSet 이 삽입 순서를 어떻게 유지하는지 확인 할 수 있음.

메서드

추가, 삭제, 검사

• add(E e) : 지정된 요소를 세트에 추가. 요소가 세트에 이미 존재하지 않는 경우에만 추가되며, 추가 성공시 true 를 반환함.
• remove(Object o) : 지정된 요소가 세트에 존재하는 경우, 그 요소를 세트에서 제거함. 제거 성공 시 true 를 반환함.
• contains(Object o) : 세트가 지정된 요소를 포함하고 있는지 여부를 반환

크기 및 상태

• size() : 세트의 요소 개수를 반환함.
• isEmpty() : 세트가 비어 있는지 여부를 검사. 비어있으면 true 를 반환함.
• clear() : 세트의 모든 요소를 제거함.

반복자 및 배열로 변환

• iterator() : 세트의 요소에 접근할 수 있는 반복자(iterator) 를 반환함. 이 반복자는 세트의 요소를 추가된 순서대로 반복함.
• toArray() : 세트의 모든 요소를 포함하는 배열을 반환함.
• toArray(T[] a) : 세트의 모든 요소를 포함하는 배열을 반환. 이 메소드는 실행 시간 유형의 지정된 배열에 결과를 저장하고, 배열이 세트의 요소를 모두 담을 수 있을 만큼 충분히 큰 경우 해당 배열을 사용함.

대량 연산

• addAll(Collection<? extends E> c) : 지정된 컬렉션의 모든 요소를 세트에 추가함. 최소 하나의 요소가 추가되면 true 를 반환함.
• removeAll(Collection<?> c) : 지정된 컬렉션에 포함된 요소를 세트에서 모두 제거함. 세트가 변경되면 true 를 반환함.
• retainAll(Collection<?> c) : 지정된 컬렉션에 포함된 요소만을 유지하고, 나머지 요소는 세트에서 제거함. 세트가 변경되면 true 를 반환함.
• containsAll(Collection<?> c) : 세트가 지정된 컬렉션의 모든 요소를 포함하고 있는지 여부를 검사함.

순서 유지가 되기 때문에 HashSet 과 유사해도 순서 유지 기능 덕분에 add 한 순서가 중요한 경우 LinkedHashSet 을 사용하면 된다.

---

SortedSet

이란?

• Set 인터페이스를 확장하여 요소들이 정렬된 순서로 유지되는 집합
• 중복을 허용하지 않으면서 모든 요소를 특정 정렬 순서대로 저장
• TreeSet 처럼 레드-블랙 트리의 형태로 저장하고 관리함.

특징

• 자동 정렬
  SortedSet 에 요소를 추가하면, 해당 요소는 자동으로 정렬 순서에 따라 적절한 위치에 삽입됨. 정렬순서는 요소의 자연 순서(Comparable 인터페이스를 구현) 또는 생성 시 제공된 Comparator 에 의해 결정됨.
• 중복 불가
  동일한 요소를 SortedSet 에 추가하려고 하면 추가가 무시됨. 즉. Set 인터페이스의 특성을 그대로 상속받아 중복된 요소를 저장하지 않음
• 범위 검색
  특정 요소를 기준으로 부분 집합(subset), 머리 집합(headset), 꼬리 집합(tailset) 등을 생성할 수 있으며, 이는 대규모 데이터셋에서 특정 범위의 요소를 효율적으로 처리할 수 있도록 해줌.

메소드

• first() : 정렬된 집합에서 가장 작은(첫 번째) 요소를 반환함.
• last() : 정렬된 집합에서 가장 큰(마지막) 요소를 반환함.
• headSet(E toElement) : 지정된 요소보다 작은 요소들의 뷰를 반환
• tailSet(E fromElement) : 지정된 요소 이상의 요소들의 뷰를 반환
• subSet(E fromElement, E toElement) : 두 요소 사이의 요소들의 뷰를 반환
• comparator() : 집합의 정렬에 사용된 Comparator 객체를 반환함. 자연 순서를 사용하는 경우 null 을 반환함.

---

HashSet

란?

• Java 의 java.util 패키지에 포함된 컬렉션 클래스
• Set 인터페이스를 구현함.
• 집합을 구현하는데 사용되며, 그 특징으로는 요소의 중복을 허용하지 않고, 저장 순서를 보장하지 않음.

특징

• 중복 불가능 : HashSet 은 집합 성질을 모방하여, 중복된 요소의 저장을 허용하지 않음. 이미 집합에 존재하는 요소를 추가하려고 하면 그 요소는 무시됨.
• 순서 보장 없음 : 요소가 HashSet 에 추가되는 순서는 저장 시의 순서와 일치하지 않을 수 있음. 즉, HashSet 은 요소의 순서를 보장하지 않음
• 빠른 접근 속도 : 내부적으로 해시 테이블을 사용하기 때문에, 대부분의 연산(추가,삭제, 검색) 을 상수 시간 내에 수행할 수 있음.
• null 값 허용 : HashSet 은 하나의 null 값을 저장할 수 있음.

장점

1. 성능 : HashSet 은 해시 함수를 사용하여 요소를 저장하기 때문에, 큰 데이터 집합에 대한 빠른 검색, 추가, 삭제 작업을 제공함. 대부분의 시간 복잡도는 O(1)임.
2. 사용 용이성 : Set 인터페이스를 구현하므로, 집합 관련 연산을 사용하기 위한 다양한 메소드를 제공함. 중복을 자동으로 처리하기 때문에, 사용자는 데이터의 고유성을 신경쓰지 않아도 됨.
3. 메모리 효율성 : 중복된 요소를 저장하지 않기 때문에 메모리 사용을 최적화 할 수 있음

단점

1. 순서 없음 : HashSet 은 요소들의 추가 순서를 유지하지 않음. 요소들의 순서가 중요한 경우에는 LinkedHashSet 이나 TreeSet 과 같은 다른 Set 구현을 사용해야함.
2. 해시충돌 : 해시 함수의 성능에 따라 해시 충돌이 발생할 수 있고, 이는 HashSet 의 성능을 저하 시킬 수 있음.
3. 동기화 미지원 : HashSet 은 Thread-Safe 하지 않음. 여러 스레드가 동시에 HashSet 을 수정할 때 외부에서 동기화 처리를 해주어야 함. 필요한 경우 Collections.synchronizedSet 메소드를 사용하여 HashSet 을 동기화된 세트로 변환할 수 있음.

HashSet 은 데이터의 고유성을 보장해야 하고, 요소의 순서가 중요하지 않은 경우에 매우 유용한 자료 구조임.

그러나 요소의 순서를 유지해야 하는 상황이나 multi-thread 환경에서는 추가적인 고려가 필요함.

메서드

• add(E e): 지정된 요소가 집합에 아직 존재하지 않는 경우, 그 요소를 집합에 추가한다.
• remove(Object o): 지정된 요소가 집합에 있을 경우, 그 요소를 집합에서 제거한다.
• contains(Object o): 집합이 지정된 요소를 포함하고 있는 경우 true를 반환한다.
• size(): 집합의 요소 수를 반환한다.
• isEmpty(): 집합이 비어 있는 경우 true를 반환한다.
• clear(): 집합에서 모든 요소를 제거한다.
• iterator(): 집합의 요소에 순차적으로 접근할 수 있는 반복자를 반환한다.
• toArray(): 집합의 요소를 포함하는 배열을 반환한다.
• addAll(Collection<? extends E> c): 지정된 컬렉션의 모든 요소를 추가한다(중복 제외).
• removeAll(Collection<?> c): 지정된 컬렉션에 포함된 모든 요소를 집합에서 제거한다.
• retainAll(Collection<?> c): 지정된 컬렉션에 포함된 요소만을 유지하고, 나머지 요소는 집합에서 제거한다.

---

TreeSet

TreeSet 이란?

• Set 인터페이스를 구현한 클래스
• 객체를 중복해서 저장할 수 없음
• 저장 순서가 유지되지 않음
• 이진 탐색 트리(BinarySearchTree) 의 구조로 이루어져 있음.
  삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조임
  그래서 HashSet 보다 데이터의 추가와 삭제는 시간이 더 걸리지만 검색과 정렬에는 유리함.
• nature ordering 을 지원하며 생성자의 매개변수로 Comparator 객체를 입력하여 정렬방법을 임의로 지정해줄 수 있음. (asc, desc...)
• 저장 순서가 유지되지는 않지만 정렬된 순서를 유지함.

저장 순서가 유지되지는 않지만 정렬된 순서를 유지한다는게..?

Java 의 TreeSet 구현은 실제로 TreeMap 을 내부적으로 사용하여 요소를 저장하고 관리함.

TreeMap 을 까도 들어가보면 Red-Bloack Mechanics 라고 있음.

TreeSet 생성자에서 TreeMap 인스턴스를 초기화 하는 순간부터, TreeSet 에 요소를 추가, 삭제 하거나 특정 요소를 조회하는 등의 연산을 수행할 때마다 내부적으로 TreeMap 을 통해 레드-블랙 트리 로직이 실행됨.

레드-블랙 트리 로직이란

• 자가 균형을 유지하는 이진 탐색 트리의 한 종류
• 각 노드가 추가적인 정보인 '색' 을 가지며, 빨간색 or 검은색일 수도 있음.
• 이 트리는 몇가지 규칙을 가지고 있음.
• 부모 노드 보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞춰줌. (중요)

레드 블랙 트리 규칙

1. 노드의 색깔은 빨간색 또는 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL 노드) 는 검은색이다.
4. 빨간색 노드의 자식 노드들은 모두 검은색이다.(즉, 빨간색 노드는 연속될 수 없다.)
5. 각 노드로부터 해당 노드의 후손 리프 노드로 이어지는 모든 경로에는 같은 수의 검은색 노드가 존재해야한다.

레드 블랙 트리의 연산

• 검색 (search) : 일반 이진 탐색 트리와 마찬가지로, 레드-블랙 트리에서도 검색 연산은 효율적으로 수행됨.
• 삽입(Insertion) : 새로운 노드를 삽입한 후, 레드-블랙 트리의 규칙을 유지하기 위해 트리를 조정함. 이 과정에서 노드의 색을 변경하거나, 트리를 회전시키는 등의 작업이 수행될 수 있음.
• 삭제(Deletion) : 노드를 삭제한 후, 트리의 균형을 맞추기 위해 다양한 프로그래밍 언어와 라이브러리에서 맵,세트 등의 자료 구조의 구현 기반으로 널리 사용됨.

메소드

기본 연산

• add(E e) : 지정된 요소를 세트에 추가함. 요소가 이미 존재하면 추가되지 않음.
• remove(Object o) : 지정된 요소를 세트에서 제거함.
• contains(Object o) : 세트가 지정된 요소를 포함하고 있는지 여부를 반환
• size() : 세트에 있는 요소의 수를 반환함.
• isEmpty() : 세트가 비어 있는지 여부를 검사
• clear() : 세트에서 모든 요소를 제거

반복자 및 순회

• iterator() : 세트의 요소에 순차적으로 접근하는 반복자를 반환함.
• descendingIterator() : 세트의 요소에 역순으로 접근하는 반복자를 반환함.

범위 검색 및 뷰

• first() : 세트에서 가장 작은(첫번째) 요소를 반환
• last() : 세트에서 가장 큰(마지막) 요소를 반환
• headSet(E toElement) : 지정된 요소보다 작은 요소들의 뷰를 반환
• tailSet(E fromElement) : 지정된 요소 이상의 요소들의 뷰를 반환함.
• subSet(E fromElement, E toElement) : 두 요소 사이의 요소들의 뷰를 반환

배열변환

• toArray() : 세트의 모든 요소를 포함하는 배열을 반환
• toArray(T[] a) : 세트의 모든 요소를 포함하는 지정된 배열 타입의 배열을 반환비교 및 복사
• comparator() : 세트의 정렬에 사용된 비교자를 반환함. 자연 정렬을 사용하는 경우 null 을 반환함.

TreeSet은 이진 탐색 트리의 성질을 활용하여 중복 없이 요소를 저장하며, 모든 요소는 정렬된 순서를 유지함. 이러한 특성 때문에 TreeSet은 검색 및 정렬이 필요한 상황에서 유용하게 사용될 수 있음.