자바의 정석 기초편 ch11 - 34 ~ 45 [HashSet, TreeSet]

1) HashSet

• Set인터페이스를 구현한 대표적인 컬렉션 클래스로 순서가 없고 중복값을 허용하지 않음
• 순서를 유지하려면 LinkedHashSet클래스를 사용
• 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인하고 같은객체가 없으면 저장, 있으면 저장하지 않음
• boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출해서 자동으로 확인함
• 객체를 Set으로 저장하면 참조값이 저장되어 저장된 논리 값이 같더라도 참조값을 다르므로 Set에 저장이됨
• 객체를 생성할 클래스에 Set의 특징을 적용하려면 equals()와 hashCode()를 직접 오버라이딩하여 값을 비교하도록 하여 실제 저장된 값이 동일하면 중복으로 판단되어 저장하지 않도록 할 수 있음

(1) HashSet 주요 메서드

• HashSet() : 기본생성자
• HashSet(Collection c) : 객체저장
• HashSet(int initialCapacity) : 초기용량지정(보통 2배)
• HashSet(int initialCapacity, float loadFactor) : 언제 용량을 늘릴건지 설정(loadFactor 0.8 -> 80%)

Collection 인터페이스 메서드		설명
추가	boolean add(Object o) boolean addAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가함
전체삭제	void clear()	Collection의 모든 객체를 삭제
검색	boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들이 Collection에 포함 되어있는지 확인
-	bollean isEmpty()	Collection이 비어 있는지 확인
	Iterator iterator()	Collection의 Iterator를 얻어서 반환
삭제	boolean remove(Object o)	지정된 객체를 삭제
	boolean removeAll(Collection c)	지정된 Collection(c)에 포함된 객체들을 삭제
	boolean retainAll(Collenction c)	지정된 Collection(c)에 포함된 객체만을 남기고 다른 객체들은 Collection에서 삭제 이 작업으로 인해 Collection에 변화가 있으면 true 없으면 false를 반환
	int size()	Collection에 저장된 객체의 개수를 반환
배열 저장	Object[] toArray()	Collection에 저장된 객체를 객체배열(Object[])로 반환
	Object[] toArray(Object[] a)	지정된 배열에 Collection의 객체를 저장해서 반환

 

Set 메서드		설명
합집합	boolean addAll(Collection c)	지정된 Collection(c)의 객체들을 Collection에 추가함
부분집합	boolean containsAll(Collection c)	지정된 Collection(c)의 객체들이 Collection에 포함 되어있는지 확인
차집합	boolean removeAll(Collection c)	지정된 Collection(c)에 포함된 객체들을 삭제
교집합	boolean retainAll(Collenction c)	지정된 Collection(c)에 포함된 객체만을 남기고 다른 객체들은 Collection에서 삭제

 

(2) HashSet예제1

• 중복값을 배열에 저장 후 HashSet에 다시 저장하면 중복값을 제외한 값만 저장됨
• 문자열1과 숫자 1은 다른 타입이므로 저장이 됨

import java.util.*;

class Ex11_9 {
	public static void main(String[] args) {
		// 배열 선언
		Object[] objArr = {"1",new Integer(1),"2","2","3","3","4","4","4"};
		Set set = new HashSet();

		for(int i=0; i < objArr.length; i++) {
			// HashSet에 objArr의 요소들을 저장하고 어떤값이 저장 되었는지 확인.
			System.out.println(objArr[i]+"="+set.add(objArr[i]));	
		}
		// HashSet에 저장된 요소들을 출력
		System.out.println(set);	

		// HashSet에 저장된 요소를 Iterator를 이용하여 출력
		Iterator it = set.iterator();
		while(it.hasNext()) {
			System.out.println(it.next());	
		}
	}
}

/*
출력
1=true	// 문자열 1
1=true	// Integer 1
2=true
2=false
3=true
3=false
4=true
4=false
4=false
[1, 1, 2, 3, 4]	// HashSet 저장결과
1
1
2
3
4
*/

 

(3) HashSet예제2

• 1 ~ 45의 중복되지않는 숫자를 출력(로또번호 출력)
• 임의의 랜덤값을 HashSet으로 저장 후 sort()메서드를 활용하여 정렬하면 Set은 순서가 없으므로 정렬 불가
• List로 변환 후 정렬해야 정렬이 적용 됨

import java.util.*;

class Ex11_10 {
	public static void main(String[] args) {
		// HashSet객체 생성
		Set set = new HashSet();
		
		// set의 크기가 6보다 작은동안 1~45 사이의 난수를 저장
		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);
		
		// set의 값을 정렬하기 1.set을 리스트에 저장 2.sort()로 list를 정렬
		List list = new LinkedList(set); // LinkedList(Collection c)
		Collections.sort(list);          // Collections.sort(List list)
		System.out.println("오름차순 정렬한 상태의 값 = "+list);
        
		Collections.sort(list, new Descending1());	// 내림차순 정렬
		System.out.println("내림차순 정렬한 상태의 값 = "+list);
	}
}

class Descending1 implements Comparator { 
	public int compare(Object o1, Object o2){
		if( o1 instanceof Comparable && o2 instanceof Comparable) {
			Comparable c1 = (Comparable)o1;
			Comparable c2 = (Comparable)o2;
			return c1.compareTo(c2) * -1 ; // -1을 곱해서 기본 정렬방식의 역으로 변경
            // 또는 c2.compareTo(c1)와 같이 순서를 바꿔도 됨
		}
		return -1;
	} 
}

출력값
정렬하지 않은 상대의 값 = [4, 42, 26, 43, 12, 45]
오름차순 정렬한 상태의 값 = [4, 12, 26, 42, 43, 45]
내림차순 정렬한 상태의 값 = [45, 43, 42, 26, 12, 4]

 

(4) HashSet 예제3

• 클래스에 equals()와 hashCode() 오버라이딩하여 해당 클래스를 객체를 생성하여 Set에 저장하면 객체 저장된 논리적인 값이 중복되면 Set에 저장되지 않도록 할 수 있음

import java.util.*;

class Ex11_11 {
	public static void main(String[] args) {
		HashSet set = new HashSet();
		
		// String을 Set에 저장
		set.add("abc");
		set.add("abc");
        
		// 객체를 생성하여 Set을 저장
		set.add(new Person("David",10));
		set.add(new Person("David",10));

		System.out.println(set);
	}
}

// equals()와 hashCode()를 오버라이딩 해야 HashSet이 바르게 동작.
class Person {
	String name;
	int age;

	// eclips의 자동 기능
	@Override
	public int hashCode() {
		return Objects.hash(age, name);
	}

	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof Person)) return false;
		Person p = (Person) obj;
		return this.name.equals(p.name) && this.age == p.age;
	}

	Person(String name, int age) {
		this.name = name;
		this.age = age;
	}

	public String toString() {
		return name +":"+ age;
	}
}

// 출력
// [abc, David:10]

 

(5) HashSet 예제4

• Set의 합집합, 차집합, 교집합을 Iterator를 활용하여 직접 구현
• 메서드를 활용하면 쉽게 합집합, 차집합, 교집합을 구할 수 있음

import java.util.*;

class Ex11_12 {
	public static void main(String args[]) {
		HashSet setA   = new HashSet();
		HashSet setB   = new HashSet();
		HashSet setHab = new HashSet();
		HashSet setKyo = new HashSet();
		HashSet setCha = new HashSet();

		setA.add("1");	setA.add("2");  setA.add("3");
		setA.add("4");  setA.add("5");
		System.out.println("A = "+setA);

		setB.add("4");	setB.add("5");  setB.add("6");		
		setB.add("7");  setB.add("8");
		System.out.println("B = "+setB);
		
		// 교집합 구하기
		Iterator it = setB.iterator();
		while(it.hasNext()) {
			Object tmp = it.next();
			if(setA.contains(tmp))
				setKyo.add(tmp);
		}
		
		// 차집합 구하기
		it = setA.iterator();
		while(it.hasNext()) {
			Object tmp = it.next();
			if(!setB.contains(tmp))
				setCha.add(tmp);
		}
		
		// 합집합 구하기
		it = setA.iterator();
		while(it.hasNext())
			setHab.add(it.next());

		it = setB.iterator();
		while(it.hasNext())
			setHab.add(it.next());

		System.out.println("A ∩ B = " + setKyo);
		System.out.println("A U B = " + setHab);
		System.out.println("A - B = " + setCha); 
	}
}
/* 
출력
A = [1, 2, 3, 4, 5]
B = [4, 5, 6, 7, 8]
A ∩ B = [4, 5]
A U B = [1, 2, 3, 4, 5, 6, 7, 8]
A - B = [1, 2, 3]
*/

// 메서드를 활용하면 쉽게 구할 수 있음
// setA.retainAll(setB)	// 교집합. 공통된 요소만 남기고 삭제
// setA.addAll(setB)	// 합집합. setB의 모든 요소를 추가(중복 제외)
// setA.removeAll(setB)	// 차집합. setA와 setB의 공통 요소를 제거

 

2) TreeSet

• 범위 검색과 정렬에 유리한 컬렉션 클래스
• 이진탐색트리(binary search tree)로 구현된 Set
• 이진트리는 모든 노드가 최대 2개의 하위 노드를 갖으며 각 요소(node)가 나무(tree)형태로 연결됨(LinkedList 의 변형)
• 데이터가 많아질수록 HashSet보다 추가, 삭제에 시간이 더 걸림(비교 횟수가 증가)

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

 

hashtree 구조

 

(1) 이진탐색트리(binary search tree)

• 이진트리의 종류 중 하나
• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
• 실제 값이 아닌 참조를 저장함

 

(2) TreeSet 데이터 저장과정

• TreeSet에 7, 4, 9, 1, 5의 순서로 데이터를 저장한다고 가정하면 루트부터 값을 저장한 뒤 트리를 따라 내려가며 저장된 값과 저장될 값을 비교하여 작으면 왼쪽에 크면 오른쪽에 저장함
• 저장하는 구조를 살펴보면 데이터가 많아질수록 비교 횟수가 늘어나는 것을 알 수 있음

 

(3) TreeSet의 주요 생성자와 메서드

• Collection의 메서드는 동일하게 사용 가능하므로 제외하고 작성
• TreeSet은 값을 저장할 때 중복값을 저장하지 않기 위해 필수로 비교 기준이 필요하며 Comparator로 비교기준을 직접 제공해야하며 비교기준값을 입력하지 않으면 저장하는 객체의 Comparable로 비교 후 저장함

TreeSet 메서드		설명
생성자	TreeSet()	기본 생성자
	TreeSet(Collection c)	주어진 걸렉션을 저장하는 TreeSet생성
	TreeSet(Comparator comp) 비교기준제공 필수	주어진 정렬기준으로 정렬하는 TreeSet을 생성
메서드	Object first()	정렬된 순서에서 첫번째 객체를 반환(오름차순일 때 제일 작은 값)
	Object last()	정렬된 순서에서 마지막 객체를 반환(오름차순일 때 제일 큰 값)
	Object ceiling(Object o)	지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
	Object floor(Object o)	지정된 객체와 같은 객체를 반환 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
	Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환 없으면 null
	Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환 없으면 null
	SortedSet subSet(Object fromElement, Object toElement)	범위 사이의 결과를 반환(끝 범위는 포함 X)
	SortedSet headSet(Odbject toElement)	지정된 객체보다 작은 값의 객체들을 반환(기준값 미포함)
	SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환

 

(4) TreeSet예제1

• 저장할 때 지정한 비교 기준을 통해 자동으로 정렬되어 정렬이 필요가 없음
• HashSet은 순서가 없기 때문에 정렬이 필요하면 List 계열로 변환하여 정렬을 해주어야 함 

import java.util.*;

class Ex11_13 {
	public static void main(String[] args) {
		// TreeSet은 비교기준이 필수
		Set set = new TreeSet();	// 범위검색, 저장하는 것만으로 정렬이 되어 정렬이 필요가 없음
		Set set2 = new HashSet();	// 정렬을 별도로 해주어야 함
		
		for (int i = 0; set.size() < 6 ; i++) {
			int num = (int)(Math.random()*45) + 1;
			// Integer는 정렬기준을 가지고 있음
			set.add(num);  // set.add(new Integer(num));
			set2.add(num);  // set.add(new Integer(num));
		}
		

		System.out.println("Treeset = "+set);
		System.out.println("Hashset = "+set2);
	}
}
/*
출력값
Treeset = [6, 12, 13, 20, 21, 23]
Hashset = [20, 21, 6, 23, 12, 13]
*/

(5) TreeSet예제2

• 필수로 객체가 비교기준을 가지고 있거나, 직접 비교기준을 정의하여 생성자에 입력하거나 해야함

import java.util.*;

class Ex11_13 {
	public static void main(String[] args) {
		// TreeSet은 비교 기준이 필수임
		// TreeSet이 비교 기준을 가지고 있거나 - Comparator의 compareTo를 오버라이딩
		Set set = new TreeSet(new TestComp());
		
		// 객체가 비교 기준을 가지고 있거나 - Comparable의 기본 비교기준 사용
		Set set2 = new TreeSet();
        
		set.add(new Test());
		set.add(new Test());
		set.add(new Test());
        
		set2.add(new Test());
		set2.add(new Test());
		set2.add(new Test());
        
		System.out.println(set);
		System.out.println(set2);
	}
}

// 별도의 클래스 생성
class Test implements Comparable {
	public int compareTo(Object o) {
		return 1;	// 0으로 설정하면 같은 객체로 판단되어 1개만 출력(중복이 제거 됨)
	}
}

class TestComp implements Comparator {
	public int compare(Object o1, Object o2) {
		return 1;	// 0으로 설정하면 같은 객체로 판단되어 1개만 출력(중복이 제거 됨)
	}
}

 

(6) TreeSet예제3

• TreeSet은 범위 검색에 유리함
• subSet(from, to)메서드를 사용하면 지정된 범위사이의 값을 반환할 수 있으며 기본적으로 to는 검색 범위에 포함되지 않지만 커스터마이징하여 범위를 포함시킬 수 있음

import java.util.*;

class Ex11_14 {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();	// 범위 검색에 유리(from ~ to)

		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);
		// to 범위는 들어가지 않음
		System.out.println("result1 : " + set.subSet(from, to));
        
		// to의 범위도 포함되게 검색
		System.out.println("result2 : " + set.subSet(from, to + "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, dzzzz]
*/

 

(7) TreeSet예제4

• headSet, tailSet을 활용하면 인수의 값보다 높거나 낮은 값을 출력할 수 있음

import java.util.*;

class Ex11_15 {
	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(50));
		System.out.println("50보다 큰 값 :"  + set.tailSet(50));
		System.out.println("40과 80사이의 값 :"  + set.subSet(40,80));
	}
}
/*
출력
50보다 작은 값 :[10, 35, 45]
50보다 큰 값 :[50, 65, 80, 95, 100]
40과 80사이의 값 :[45, 50, 65]
*/

 

(8) 그림으로 설명

• 이진탐색트리로 데이터를 저장하면 특정 기준값보다 큰값, 작은값, 범위의 값들을 부담가지 않게 구할 수 있음
• 이미지처럼 특정 값을 기준으로 작은값들은 왼쪽의 값들만 찾으면 되고, 큰 값은 오른쪽의 값들만 찾으면 되기 때문에 기준이 되는 값만 찾게 되면 범위 검색에 유리함

 

(9) 트리순회(tree traversal)

• 이진 트리의 모든 노드를 한번씩 읽는 것을 순위라고 함
• 전위순회(pre order) : 부모의 노드를 가장 먼저 읽음
• 후위순회(post order) : 부모의 노드를 제일 마지막에 읽음
• 중위순회(in order) : 부모의 노드를 중간에 읽음 -> 자동으로 오름차순으로 정렬된 됨(TreeSet이 정렬에 유리한 이유)
• 레벨순회(level order) : 최고 부모의 노드부터 순서대로 읽음

중위 순회가 진행되는 순서

 

* 출처 : 남궁성의 정석코딩_자바의정석_기초편 유튜브 강의