[공부의 흔적]_HashSet / TreeSet

▶ HashSet

 

Set인터페이스에서 지원하는 구현 클래스. 그래서 Set 특징을 그대로 상속받음.

Set은 중복 허용하지 않고, 하나의 null 값만 저장 가능. 또한 순서 없이 Key로만 데이터를 저장함.

 

Set의 가장 큰 장점은 중복을 자동으로 제거해 줌.

 

Set은 비선형 구조이기 때문에 순서가 없고, 인덱스도 당연히 존재하지 않음.

따라서 값을 추가하거나 삭제할 때는 그 값이 Set 내부에 있는지 검색 한 뒤, 추가나 삭제를 해야 하므로 속도가 List 구조에 비해 느림.

 

Set 인터페이스를 구현하는 클래스는 HashSet, TreeSet 등이 있음.

 

HashSet은 중복 제거해야 할 때, 값이 존재하는지 빠르게 확인해야 할 때(contains), 정렬이 피요 없는 데이터 집합일 때 사용하면 좋음.

---

 

● HashSet 생성 ●

// 타입 지정 가능
HashSet<String> animals1 = new HashSet<String>();

// 타입 생략하여 사용 가능 → 빈 HashSet 생성 시 사용
HashSet<String> animals2 = new HashSet<>();

// 초기 용량(Capacity) 설정
HashSet<String> animals3 = new HashSet<>(10);

// animal의 모든 값을 가진 HashSet 생성
HashSet<String> animal4 = new HashSet<>(animals1);

// 초기값 지정 가능
HashSet<String> animal5 = new HashSet<>(Arrays.asList("tiger", "lion", "fox"));

---

● 주요 특징 ●

 

- 중복 허용 안 함 : 같은 값은 한 번만 저장 (값의 존재 유무 파악할 때 사용 가능)

- 순서 보장 안함 : 입력 순서와 출력 순서가 다를 수 있음

- null 허용함 : null 값을 1개 저장 가능

- 빠른 탐색 : 내부적으로 HashMap 기반으로 동작해 탐색, 삽입, 삭제가 빠름 (평균 O(1))

---

● 내부 동작 ●

 

내부적으로는 HashMap 사용해 데이터를 저장함.

값이 들어올 때 hashCode() 값을 계산해서 저장 위치 결정함.

값이 많아져도 빠르게 검색, 삽입, 삭제가 가능한 것임.

---

● 주요 메서드 ●

 

add(E e) : 요소 추가

remove(Object o) : 요소 제거

contains(Object o) : 해당 요소가 있는지 확인

size() : 저장된 요소 개수

isEmpty() : 비어있는지 확인

clear() : 모든 요소 제거

---

● 예시01 ●

import java.util.HashSet;

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

        HashSet<String> fruits = new HashSet<>();

        fruits.add("apple");
        fruits.add("banana");
        fruits.add("apple");    // 중복 무시됨.

        System.out.println(fruits); // [banana, apple] 순서 보장되지 않음
        System.out.println(fruits.contains("banana"));  // true
        fruits.remove("banana");
        System.out.println(fruits.contains("banana"));  // false
    }
}

실행결과

[banana, apple]
true
false

---

● 예시02 ●

import java.util.*;

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

        HashSet<Integer> num = new HashSet<>();

        num.add(1);
        num.add(null);
        num.add(1);

        System.out.println(num);    // [null, 1] 순서 보장하지 않음
        System.out.println("num 사이즈 : " + num.size());  // 2

        System.out.println("1을 포함하나요? " + num.contains(1)); // true
        System.out.println("2를 포함하나요? " + num.contains(2)); // false

        num.remove(1);
        System.out.println("1을 포함하나요? " + num.contains(1)); // false
        num.clear();
        System.out.println(num);    // []

        num.add(1);
        num.add(2);
        num.add(3);
        System.out.println(num.toString()); // [1, 2, 3]

        Iterator iter = num.iterator();
        while(iter.hasNext()) {
            System.out.print(iter.next() + " ");    // 1 2 3
        }

        System.out.println();
        
        // 자바 Set List로 변환하여 정렬
        ArrayList<Integer> list = new ArrayList<>(num);    // num을 ArrayList로 변경

        Collections.sort(list, ((o1, o2) -> o2 - o1));  // 내림차순 정렬
        System.out.println(list.toString());    // [3, 2, 1]

        Collections.sort(list, ((o1, o2) -> o1 - o2));  // 오름차순 정렬
        System.out.println(list.toString());    // [1, 2, 3]

    }
}

실행결과

[null, 1]
num 사이즈 : 2
1을 포함하나요? true
2를 포함하나요? false
1을 포함하나요? false
[]
[1, 2, 3]
1 2 3 
[3, 2, 1]
[1, 2, 3]

---

▶ TreeSet

 

Java의 java.util 패키지에 포함된 클래스이고, Set 인터페이스를 구현하면서 내부적으로는 Red-Black Tree(이진 균형 트리) 기반으로 작동함.

 

데이터를 자동 정렬하면서 중복 제거하고 싶을 때나 범위 검색이 필요할 때 사용하면 좋음.HashSet보다 느리지만 정렬된 결과를 제공함.

---

● TreeSet 생성 ●

// 타입 지정 가능
TreeSet<Integer> num1 = new TreeSet<Integer>();

// 타입 생략하여 사용 가능 → 빈 HashSet 생성 시 사용
TreeSet<Integer> num2 = new TreeSet<>();

// 초기값 지정 가능
TreeSet<Integer> num3 = new TreeSet<>(Arrays.asList(1, 2, 3));

---

● 주요 특징 ●

 

- 중복 허용 안 함 : Set 계열이라 중복된 값은 저장되지 않음

- 자동 정렬 됨 : 값이 오름차순(기본)으로 정렬됨

- 정렬 기준 변경 가능 : Comparator를 사용하면 정렬 기준 변경 가능

- 탐색, 삭제 성능 : 평균 O(log N), 트리기반이기 때문

- null 저장 불가 : null은 저장할 수 없음 → NullPointerException 발생

---

● 주요 메서드 ●

 

add(E e) : 요소 추가

remove(E e) : 요소 제거

contains(E e) : 포함 여부 확인

first() / last() : 가장 작은 / 큰 값 반환

higher(E e) : 주어진 값보다 큰 값 중 가장 작은 값

lower(E e) : 주어진 값보다 작은 값 중 가장 큰 값

---

 

● 예시01 ●

import java.util.*;

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

        TreeSet<Integer> scores = new TreeSet<>();

        scores.add(50);
        scores.add(20);
        scores.add(70);
        scores.add(20); // 중복 무시됨

        System.out.println(scores); // [20, 50, 70] → 자동 오름차순
        
        TreeSet<String> names = new TreeSet<>(Comparator.reverseOrder());
        
        names.add("banana");
        names.add("apple");
        names.add("cherry");

        System.out.println(names);  // [cherry, banana, apple] → 내림차순
    }
}

실행결과

[20, 50, 70]
[cherry, banana, apple]

---

● 예시02 ●

import java.util.*;

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

        TreeSet<Integer> ts = new TreeSet<>();

        ts.add(5);
        ts.add(3);
        ts.add(9);
        ts.add(7);

        System.out.println(ts); // [3, 5, 7, 9] 자동 오름차순

        ts.remove(3);
        System.out.println(ts); // [5, 7, 9]

        ts.clear(); // 전체 삭제
        System.out.println(ts); // []

        ts.add(1);
        ts.add(5);
        //ts.add(null);
        System.out.println(ts);
        System.out.println("ts 사이즈 : " + ts.size());    // 2

        System.out.println("1을 포함하나요? " + ts.contains(1));  // true
        System.out.println("2를 포함하나요? " + ts.contains(2));  // false

        ts.add(3);
        ts.add(9);
        System.out.println(ts.first()); // 1
        System.out.println(ts.last());  // 9

        for (Integer t : ts) {
            System.out.print(t + " ");  // 1 3 5 9
        }

        System.out.println();

        Iterator iter = ts.iterator();
        while(iter.hasNext()) {
            System.out.print(iter.next() + " ");    // 1 3 5 9
        }

        System.out.println();
       
        // 내림차순
        TreeSet<Integer> nums = new TreeSet<>(Comparator.reverseOrder());
        nums.add(8);
        nums.add(4);
        nums.add(9);
        System.out.println(nums);   // [9 8 4]

        Iterator iterator = nums.iterator();
        while(iterator.hasNext()) {
            System.out.print(iterator.next()+ " "); // 9 8 4
        }
    }
}

실행결과

[3, 5, 7, 9]
[5, 7, 9]
[]
[1, 5]
ts 사이즈 : 2
1을 포함하나요? true
2를 포함하나요? false
1
9
1 3 5 9 
1 3 5 9 
[9, 8, 4]
9 8 4

null은 허용하지 않음.

TreeSet은 내부적으로 비교(compareTo or compare)를 이용해서 값을 정렬하기 때문에

null은 비교 불가하므로 NullPointerException이 터짐.

 

Iterator iter = ts.iteraor();에서

iterator() 메서드는 컬렉션에 대한 반복자(Iterator)를 반환함.

이 반복자를 통해 컬렉션의 요소들을 하나씩 꺼낼 수 있음.

 

while(iter.hasNext())에서

hasNext()는 다음에 읽을 요소가 있는지 확인하는 메서드.

true면 다음 요소가 있고, false면 더 이상 없음.

 

System.out.print(iter.next() + " ");에서

next()는 현재 위치의 값을 반환하고, 포인터를 다음 위치로 이동시킴.

그래서 출력하고 나면 다음 값을 준비함.

 

 

 

 

 

 

 

 

[출처]

https://velog.io/@acacia__u/hashSet

[Java] HashSet의 개념과 사용법 정리

https://velog.io/@db_jam/Java-%ED%8A%B8%EB%A6%AC%EC%85%8BTreeSet-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC

[Java] 트리셋(TreeSet) 자료구조 정리