Java - HashSet, TreeSet, LinkedSet

0. Set

중복된 요소를 허용하지 않고, 기본적으로 순서가 없는 배열 (집합의 성격)

---

1. HashSet : 해시->빠르다! 순서 없음! null값 저장가능!

• 특징:
  • 해시 테이블을 기반으로 한 Set 구현체입니다.
  • 순서를 보장하지 않고, 중복된 요소를 허용하지 않습니다.
  • null 값을 저장할 수 있습니다.
• 사용 이유:
  • 빠른 검색 속도를 제공합니다. *해시 기반으로 구현되어 있어서 요소를 빠르게 찾을 수 있습니다.
  • 순서가 중요하지 않은 경우에 사용됩니다.

* 해시(Hash) 기반?

1. 일관성: 동일한 입력에 대해 항상 동일한 해시 코드를 생성합니다.
2. 고유성: 서로 다른 입력은 가능한 한 서로 다른 해시 코드를 생성합니다.
3. 고속성: 빠르게 해시 값을 계산할 수 있어야 합니다.

 

해시 기반의 자료구조들(예: HashSet, HashMap 등)은 해시 함수를 사용하여 데이터를 저장하고 검색하는데 이용됩니다. 데이터가 해시 함수에 의해 생성된 해시 값에 따라 저장되는데, 이를 통해 데이터에 빠르게 접근할 수 있습니다. 예를 들어, HashSet은 해시 테이블을 기반으로 하여 중복되지 않는 값을 저장하는데, 이때 각 요소의 해시 코드를 기반으로 저장되어 빠르게 접근할 수 있습니다.

---

HashSet 코드 예시

추가 .add()

개수 확인 .size()

포함여부 확인 .contains()

제거 .remove()

비우기 .clear()

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        // HashSet 생성
        HashSet<String> uniqueNames = new HashSet<>();

        // 요소 추가
        uniqueNames.add("Alice");
        uniqueNames.add("Bob");
        uniqueNames.add("Charlie");
        uniqueNames.add("Alice"); // 중복된 요소는 추가되지 않음

        // 요소 수 확인
        System.out.println("HashSet에 저장된 요소 수: " + uniqueNames.size()); 
        // 중복된 "Alice"는 추가되지 않으므로 3 출력

        // 요소 존재 여부 확인
        System.out.println("HashSet에 'Alice'가 포함되어 있는가? " + uniqueNames.contains("Alice")); 
        // true 출력

        // 요소 반복
        System.out.println("HashSet의 모든 요소:");
        for (String name : uniqueNames) {
            System.out.println(name);
        }
        // Bob Alice Charlie

        // 요소 제거
        uniqueNames.remove("Bob");
        System.out.println("Bob을 제거한 후의 HashSet의 모든 요소:");
        for (String name : uniqueNames) {
            System.out.println(name);
        }
        // Alice Charlie

        // HashSet 비우기
        uniqueNames.clear();
        System.out.println("HashSet이 비어있는가? " + uniqueNames.isEmpty()); 
        // true 출력
    }

 

---

2. TreeSet : 트리 -> 순서 정렬!  null값 저장 안됨!

• 특징:
  • *이진 검색 트리를 기반으로 한 Set 구현체입니다.
  • 요소를 자동으로 정렬(순서 O)하여 저장합니다.
  • 중복된 요소를 허용하지 않습니다.
  • null 값을 저장할 수 없습니다.
• 사용 이유:
  • 정렬된 상태로 데이터를 유지해야 하는 경우에 사용됩니다.
  • 정렬된 순서로 요소에 접근해야 할 때 유용합니다.

*이진 검색 트리?

이진 검색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 해당 노드보다 작은 값을 가지고 오른쪽 자식 노드는 해당 노드보다 큰 값을 가지는 트리 구조입니다. TreeSet은 이진 검색 트리를 활용하여 요소를 저장하고 정렬하는데 사용됩니다.

예를 들어, 다음과 같은 정수를 TreeSet에 추가하는 과정을 살펴보겠습니다: 5, 3, 8, 2, 7, 10, 6.

처음에는 빈 TreeSet에서 시작합니다. 각 요소를 추가할 때마다 TreeSet은 이진 검색 트리의 규칙에 따라 요소를 추가하고 정렬합니다.

이렇게 TreeSet은 요소를 추가하는 과정에서 이진 검색 트리의 특성을 활용하여 작은 값은 왼쪽에, 큰 값은 오른쪽에 추가하여 정렬된 상태로 유지합니다. 따라서 TreeSet은 이진 검색 트리의 구조를 활용하여 데이터를 저장하고 정렬하기 때문에 빠르고 효율적인 검색 및 정렬이 가능합니다.

 

숫자형이 아닌 문자열 형태의 요소의 경우 예를 들어, "Apple", "Banana", "Grapes", "Orange"와 같은 문자열을 TreeSet에 추가할 때, 각 문자열의 첫 글자인 'A', 'B', 'G', 'O'의 Unicode 코드 포인트 값에 따라서 정렬이 이루어질 것입니다. 만약 문자열의 첫 글자가 동일하다면 두 번째 글자, 그 다음 글자들의 Unicode 코드 포인트 값으로 비교하여 정렬됩니다.

---

 

TreeSet 코드 예시

추가 .add()

개수 확인 .size()

포함여부 확인 .contains()

제거 .remove()

비우기 .clear()

-

최대값 .first()

최소값 .last()

n보다 크거나 같은 요소 중 가장 작은 값 .ceiling(n)

n보다 작거나 같은 요소 중 가장 큰 값 .floor(n)

 

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        // TreeSet 생성
        TreeSet<Integer> numberSet = new TreeSet<>();

        // 요소 추가
        numberSet.add(5);
        numberSet.add(2);
        numberSet.add(8);
        numberSet.add(1);
        numberSet.add(10);

        // 요소 수 확인
        System.out.println("TreeSet에 저장된 요소 수: " + numberSet.size()); // 5 출력

        // 요소 출력 (정렬된 순서로 출력됨)
        System.out.println("TreeSet의 모든 요소:");
        for (int num : numberSet) {
            System.out.println(num);
        }

        // 특정 요소의 존재 여부 확인
        int searchNumber = 8;
        System.out.println("TreeSet에 " + searchNumber + "가 포함되어 있는가? " + numberSet.contains(searchNumber)); // true 출력

        // 최솟값, 최댓값 찾기
        System.out.println("TreeSet의 최솟값: " + numberSet.first()); // 1 출력
        System.out.println("TreeSet의 최댓값: " + numberSet.last()); // 10 출력

        // 특정 요소보다 작거나 큰 가장 인접한 요소 찾기
        int ceiling = numberSet.ceiling(6); // 6보다 크거나 같은 요소 중 가장 작은 값
        int floor = numberSet.floor(6); // 6보다 작거나 같은 요소 중 가장 큰 값
        System.out.println("6보다 크거나 같은 요소 중 가장 작은 값: " + ceiling); // 8 출력
        System.out.println("6보다 작거나 같은 요소 중 가장 큰 값: " + floor); // 5 출력

        // 요소 제거
        numberSet.remove(2);
        System.out.println("2를 제거한 후의 TreeSet의 모든 요소:");
        for (int num : numberSet) {
            System.out.println(num);
        }

        // TreeSet 비우기
        numberSet.clear();
        System.out.println("TreeSet이 비어있는가? " + numberSet.isEmpty()); // true 출력
    }
}

 

---

3. LinkedHashSet : 해시->빠르다! 요소의 삽입 순서대로 정렬! null 값 저장가능!

• 특징:
  • 해시 테이블과 연결 리스트를 결합한 Set 구현체입니다.
  • 순서를 보장하며, 중복된 요소를 허용하지 않습니다.
  • 요소의 삽입 순서를 기억합니다.
  • null 값을 저장할 수 있습니다.
• 사용 이유:
  • 순서를 보장하면서 중복된 요소를 허용하지 않는 경우에 사용됩니다.
  • 요소의 삽입 순서가 중요한 경우에 사용됩니다. (값을 추가하면 배열 마지막에 순서대로 추가된다!)

import java.util.LinkedHashSet;
// LinkedHashSet 생성
LinkedHashSet<String> uniqueWords = new LinkedHashSet<>();

// 외의 기능은 동일하다

---

비교 및 사용 시 고려 사항:

• 중복 요소: 모든 Set 구현체는 중복된 요소를 허용하지 않습니다.
• 순서: HashSet은 순서를 보장하지 않지만, TreeSet은 요소를 정렬하여 저장하며, LinkedHashSet은 요소의 삽입 순서를 기억합니다.
• 속도: HashSet은 해시 기반이므로 검색 속도가 빠르지만, TreeSet은 정렬된 상태를 유지하기 위해 추가 작업을 수행하므로 상대적으로 느릴 수 있습니다. 경우마다 다르지만 일반적으로는 HashSet >= LinkedHashSet > TreeSet
• null 값: HashSet과 LinkedHashSet은 null 값을 저장할 수 있지만, TreeSet은 null 값을 저장할 수 없습니다.

---

사용 시나리오:

• HashSet: 빠른 검색 속도가 필요하고 순서가 중요하지 않은 경우에 사용됩니다.
• TreeSet: 정렬된 데이터가 필요하거나 정렬된 순서로 요소에 접근해야 하는 경우에 사용됩니다.
• LinkedHashSet: 순서를 보장하면서 중복을 허용하지 않는 경우에 사용됩니다. 요소의 삽입 순서가 중요한 경우에 적합합니다.