java #11 HashSet, TreeSet

1. HashSet - 순서 x , 중복 x <-> List
1) HashSet 
 a. Set인터페이스를 구현한 대표적 컬렉션 클래스
 b. 순서를 유지하려면, LinkedHashSet클래스를 사용하면 된다.

2) TreeSet
a. 범위 검색과 정렬에 유리한 컬렉션 클래스
b. HashSet보다 데이터 추가, 삭제에 시간이 더 걸림

3)HashSet 주요 메서드
 
HashSet(Collection c) - 생성자
HashSet(int initialCapacity) - 초기용량
boolean retainAll(Collection c) - 조건부 삭제 (차집합)
Object[] toArray() - 객체 배열로 반환
Object[] toArray(Object[] a) - 객체 배열로 반환

import java.util.*;

public class HashSetEx {

	public static void main(String[] args) {
		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);
		}
		// HastSet은 정렬이 안되므로 List로 변경한 후 sort를 통해 정렬한다!!
		List list = new LinkedList(set); // 1. set의 모든 요소를 List에 저장
		Collections.sort(list); // 2.list를 정렬
		System.out.println(list); // 3.list를 출력
	}
}

4) HashSet 예제3 중복 X 순서 X
a. HashSet은 객체를 저장하기전에 기존에 같은 객체가 있는지 확인, 같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.
b. boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출 equals()와 hashCode()가 오버라이딩 되어 있어야 함.

 

import java.util.*;

public class HashSetEx2 {

	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);
		
		setA.retainAll(setB); // 교집합. 공통된 요소만 남기고 삭제
//		setA.addAll(setB); // 합집합.  setB의 모든 요소를 추가(중복 제외)
//		setA.removeAll(setB); // 차집합. setB와 공통 요소를 제거
		System.out.println(setA);
		
//		System.out.println("A 교집합 B = " + setKyo);
//		System.out.println("A 합칩합 B = " + setHab);
//		System.out.println("A - B = " + setCha);
	}
}

2. TreeSet - 범위 탐색, 정렬
1) TreeSet 
a. 이진 탐색 트리로 구현. 범위 탐색과 정렬에 유리
b. 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
   각 요소가 나무형태로 연결(LinkedList)

2) 이진 탐색 트리(binary search tree)
a. 부모보다 작은 값은 왼쪽 큰 값은 오른쪽에 저장
b. 데이터가 많아질 수록 추가, 삭제에 시간이 더 거림 (비교 횟수 증가)

3) TreeSet 데이터 저장과정 boolean add(Object o) <- 저장한 객체 HashSet은 epquals().hashCode()로 비교, TreeSet은 compare()를 호출해서 비교
a. TreeSet에 7,4,9,1,5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.
(루트부터 트리를 따라 내려가며 값을 비교, 작으면 왼쪽, 크면 오른쪽에 저장)

4) TreeSet - 주요 생성자와 메서드
TreeSet() 생성자

ex)import java.util.*;

public class TreeSetEx {

	public static void main(String[] args) {
		Set set = new TreeSet(new TestComp());
		
		set.add(new Test());
		set.add(new Test());
		set.add(new Test());
		set.add(new Test());
		
		
		System.out.println(set);
	}
}
class Test implements Comparable {

	@Override
	public int compareTo(Object o) {
		return -1;
	}}
class TestComp implements Comparator {

	@Override
	public int compare(Object o1, Object o2) {
		return 0; // -1,1  중복 허용
	}
	
}

import java.util.*;
public class TreeSetEx2 {

	public static void main(String[] args) {
		TreeSet set = new TreeSet(); // 범위 검색에 유리! (from - to)
		
		String from = "b";
		String to = "d";
		
		set.add("adc");	set.add("wad"); set.add("asd"); set.add("csd");
		set.add("dfdg"); set.add("bddf"); set.add("bdbd"); set.add("bbb");
		set.add("bfdsc"); set.add("esada"); set.add("dd"); set.add("acx");
		
		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"));

	}

}

import java.util.*;
public class TreeSetEx3 {

	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(50));
	}

}

5) TreeSet - 범위 검색 subSet(), headSet(), tailSet()
메서드 설명
SortedSet subSet(Object fromElement,Object toElement) : 범위 검색(fromElement와 toElement사이)의 결과를 반환한다.(끝 범위인 to Element는 범위에 포함되지 않음)
SortedSet headSet(Object toElement) : 지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement) : 지정된 객체보다 큰 값의 객체들을 반환한다.

a. 트리 순회(tree traversal)
- 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다. 

 

3.HashMap과 Hashtable
1) HashMap과 Hashtable - 순서X , 중복(키X , 값O)
a. Map인터페이스를 구현, 데이터를 키와 값의 쌍으로 저장
b. HashMap(동기화 X)은 Hashtable(동기화 O)의 신버전.
c. HashMap
- Map인터페이스를 구현한 대표적인 컬렉션 클래스
- 순서를 유지하려면, LinkedHashMap클래스를 사용하면 된다.
d. TreeMap
- 범위 검색과 정렬에 유리한 컬렉션 클래스
- HashMap 보다 데이터 추가, 삭제에 시간이 더 걸림

2) HashMap의 키(key)와 값(value)
a. 해싱(hashing) 기법으로 데이터를 저장. 데이터가 많아도 검색이 빠르다.
b. Map인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장
키(key) : 컬렉션 내의 키(key) 중에서 유일해야 한다.
값(value) : 키(key)와 달리 데이터의 중복을 허용한다.

3) 해싱(hashing)
a. 해시함수(hash function)로 해시테이블(hash table)에 데이터를 저장, 검색
b. 해시테이블은 링크드 리스트가 조합된 형태
c. 해시테이블에 저장된 데이터를 가져오는 과정
- 키로 해시함수를 호출해서 해시코드를 얻는다.
- 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다.
- 링크드리스트에서 키와 일치하는 데이터를 찾는다.
해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다.
서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.