Set 인터페이스

1) 정의

중복 X
저장순서 유지 X

• 객체 추가 시, 이미 객체가 저장돼있다면 중복으로 간주되어 false를 반환

2) 메서드

• Collection 인터페이스의 메서드와 동일하다
  • Collection 인터페이스의 자식이기 때문에, Collection 인터페이스에서 사용되는 메서드를 모두 상속받아 사용

3) HashSet

(1) 정의

• Set 인터페이스를 구현하는 가장 대표적인 컬렉션

• 해싱(hashing)

  • 아무리 임의의 순서로 저장을 해도, 해싱(hashing) 알고리즘의 특성상 한 숫자가 고정된 위치에 저장된다

(2) 사용법

예시 1

import java.util.HashSet;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Set<Integer> intSet = new HashSet<Integer>(); // 선언 및 생성

		intSet.add(1);
		intSet.add(2);
		intSet.add(3);
		intSet.add(3); 		// 중복된 값은 덮어쓴다. 즉, 한 번만 출력됨
		intSet.add(3); 		// 중복된 값은 덮어쓴다.

		for (Integer value : intSet) {
			System.out.println(value); 		// 1,2,3 출력
		}

		// contains()
		System.out.println(intSet.contains(2)); 		// true 출력
		System.out.println(intSet.contains(4)); 		// false 출력

		// remove()
		intSet.remove(3); 		// 3 삭제

		for (Integer value : intSet) {
			System.out.println(value); 		// 1,2 출력
		}
	}
}

/* 출력 결과
1
2
3
true
false
1
2
*/

예시 2 : HashSet + 정렬하기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Set set = new HashSet();				// HashSet
        
        for (int i = 0; set.size() < 6; i++) {
        	int num = (int)(Math.random() * 45) + 1;
            set.add(new Integer(num));
        }
        
        List list = new LinkedList(set);		// LinkedList 생성자
        Collection.sort(list);			// 오름차순 정렬
        System.out.println(list);
	}
}

/* 출력 결과
[7, 11, 17, 18, 24, 28]
*/

• HashSet
  • 로또번호는 저장 순서가 유지되지 않는다
• LinkedList
  • Collection.sort() 메서드로 정렬하기 위해서는 LinkedList클래스의 생성자가 필요

(3) LinkedHashSet

public class LinkedHashSetDemo {
    public static void main(String args[]) {
    
        // LinkedHashSet 선언 및 데이터 입력
        LinkedHashSet<String> lhs = new LinkedHashSet<String>();
  
        lhs.add("Hello");
        lhs.add("World");
        lhs.add("Hello");
        lhs.add("blog");
        lhs.add("CrazyKim");
  
        // 결과 출력
        Iterator<String> itr = lhs.iterator();
        while (itr.hasNext()) {
            System.out.println(itr.next());
        }
    }
}

/* 출력 결과
Hello
World
blog
CrazyKim
*/

중복 X
저장순서 유지 O

4) TreeSet

(1) 정의

• '레드 - 블랙 트리'의 형태로 데이터를 저장(구현)

  • 이진 탐색 트리 (자료 구조 中 하나) 의 성능을 향상시킨 자료 구조의 형태

• 정렬기준이 주어지지 않으면, 오름차순으로 정렬(숫자의 기본정렬)

• 장단점

  • 장점

    • 정렬

      • 정렬된 순서를 얻을 수 있으므로, 단일 값 검색 & 범위 검색이 매우 빠름 (배열, LinkedList에 비해)
        (예시 : 3 ~ 7 사이의 값 검색)

    • 검색

      • 저장된 값의 개수에 비해, 검색 효율이 뛰어남 (배열, LinkedList에 비해)
        (값 개수가 10개로 늘어나도, 검색 횟수는 그것보다 적게 증가)

  • 단점

    • 저장 : 저장 위치를 찾아서 저장하므로, 시간 더 걸림 (LinkedList에 비해)
    • 삭제 : 트리의 일부를 재구성 해야하므로, 시간 더 걸림 (LinkedList에 비해)

(2) 이진 탐색 트리 & 레드-블랙 트리

• 노드

  • 부모 - 자식관계
    • 부모 노드 : 최대 2개까지의 노드를 연결 가능
    • 자식 노드

• 정렬

  • 오름차순 정렬 : 왼쪽 노드 → 부모 노드 → 오른쪽 노드 순으로 읽을 경우

class TreeNode {
	TreeNode left;   	// 왼쪽 자식 노드
    Object element;  	// 저장할 객체
    TreeNode right;  	// 오른쪽 자식 노드

• 정렬, 검색, 범위 검색에 높은 성능을 보여줌

(3) 사용법

예시 1

public class TreeSetDemo {
    public static void main(String args[]) {
    
        // TreeSet 변수 선언 및 데이터 입력
        TreeSet<String> ts = new TreeSet<String>();
  
        ts.add("Hello");
        ts.add("World");
        ts.add("Hello");
        ts.add("Blog");
        ts.add("CrazyKim");
  
        // Traversing elements
        Iterator<String> itr = ts.iterator();
        while (itr.hasNext()) {
            System.out.println(itr.next());
        }
    }
}

/* 출력 결과
Blog
CrazyKim
Hello
World
*/

예시 2 : 메서드

예시 3 : 정렬 불필요

import java.util.*;

class Ex {
	public static void main(String[] args) {
		Set set = new TreeSet();
		
		for (int i = 0; set.size() < 6 ; i++) {
			int num = (int)(Math.random() * 45) + 1;
			set.add(num);  		// set.add(new Integer(num));
		}

		System.out.println(set);
	}
}

/* 출력 결과
[5, 12, 24, 26, 33, 45]
*/

• TreeSet은 저장할 때 이미 정렬하기 때문에, 읽어올 때 따로 정렬할 메서드가 필요 X

예시 3 : subSet() 범위 검색

import java.util.*;

class Ex {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();

		String from = "b";		// 시작 문자
		String to	= "d";		// 끝 문자

		set.add("abc");
		set.add("alien");
		set.add("bat");
		set.add("car");
		set.add("Car");
		set.add("disc");
		set.add("dance");
		set.add("dZZZZ");
		set.add("dzzzz");
		set.add("elephant");
		set.add("elevator");
		set.add("fan");
		set.add("flower");

		System.out.println(set);
		System.out.println("range search : from " + from  +" to "+ to);
		System.out.println("result1 : " + set.subSet(from, to));
		System.out.println("result2 : " + set.subSet(from, to + "zzz"));		// 끝 범위인 d로 시작하는 단어까지 포함시키고 싶을 경우, 끝 범위에 ZZZ 문자열을 붙임
	}
}

/* 출력 결과
[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from b to d
result1 : [bat, car]
result2 : [bat, car, dZZZZ, dance, disc]
*/

예시 4 : headSet() 기준보다 작은 값, tailSet() 기준보다 큰 값

import java.util.*;

class Ex {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		int[] score = {80, 95, 50, 35, 45, 65, 10, 100};

		for (int i = 0; i < score.length; i++)
			set.add(new Integer(score[i]));

		System.out.println("50보다 작은 값 :"	+ set.headSet(new Integer(50)));
		System.out.println("50보다 큰 값 :"	+ set.tailSet(new Integer(50)));
	}
}

/* 출력 결과
50보다 작은 값 :[10, 35, 45]
50보다 큰 값 :[50, 65, 80, 95, 100]
*/

• headSet() : TreeSet에 저장된 객체 中 지정된 기준 값보다 큰 값의 객체들을 얻을 수 있음

• tailSet() : TreeSet에 저장된 객체 中 지정된 기준 값보다 큰 값의 객체들을 얻을 수 있음

용 머리보다 용 꼬리가 크다.

5) SortedSet

중복 X
저장순서 유지 O

• 순서를 정렬하는 메서드를 제공