[JAVA] TreeSet HashSet

 

Set ?

Collection의 일부이다.  저장되는 데이터의 순서에 상관없이 저장하고, 데이터의 중복을 허용하지 않는 자료구조.(저장 순서 파악 힘듬)

 

자료구조 HashSet

 

HashSet 특징

1) 저장되는 데이터의 순서를 파악 할 수 없다. 2) Set에서 가장 빠른 데이터 접근 속도를 가지고 있다. 3) HashSet은 기본적으로 동기화를 하지 않는다. 대신 동기화를 따로 할 수 있다.     -> Collections.synchronizedSet 메소드를 이용하여 wrapping 해주면 된다.

HashSet은 다른 자료구조 클래스와 마찬가지로 제네릭을 아용하여 저장 데이터를 결정하게 된다.

 

HashSet 데이터 검색 과정

단계	내용
1단계	최상위인 Object 클래스의 hashCode 메소드의 반환 값을 해시값으로 받는다.
2단계	equals 메소드의 결과를 이용하여 해시값이 같은지 다른지 판단한다.

총 2단계를 거치며 검색을 한다. 해시값을 이용하여 검색하기 때문에, 검색하는 범위가 엄청 줄어들어 검색 속도가 빠르다. 그리고 2단계를 활용하여 데이터 중복도 차단하게 된다.

때문에 커스텀 클래스(개발자가 직접 만든 클래스) 를 제네릭으로 넘겨 사용할 때는,  hashCode, equals 메소드를 오버라이딩 하여 사용해야 한다.

 

HashSet을 사용하기 위해서는 HastSet을 import 해줘야 한다.import java.util.HashSet;

Wrapper 클래스나, 자신의 커스텀 클래스를 제네릭으로 넘겨셔 사용하면 된다

HashSet<Integer> hashSet = new HashSet<>();HashSet<Point> hashSetPoint = new HashSet<>();

HashSet 주요 메소드
형태	메소드	설명
boolean	add(E e)	e를 Set에 추가
void	clear()	Set의 데이터를 전부 삭제
boolean	contains(Object o)	Set에 o가 있다면 true, 없으면 false
boolean	isEmpty()	Set이 비었으면 true, 아니면 false
Iterator<E>	iterator()	Set의 iterator를 반환
boolean	remove(Object o)	셋에서 o를 제거
int	size()	index 위치의 값을 반환(무한대 가능)

 

Wrapper 클래스를 사용한 HashSet 예제

 

 

커스텀 클래스를 이용한 HashSet 사용

직접 만든 클래스를 제네릭으로 넘길 때 커스텀 클래스 내부에 hashCode 메소드와, equals 메소드를 오버라이딩 해야한다.

클래스를 만들어 보자.

 

Point 클래스를 만들었다.  이것을 그냥 HashSet에 사용하면 다음과 같은 문제가 발생한다. 

이렇게 동일한 값을 add 해주면 하나만 저장 되어야 하지만, 두개 다 저장을 해버린다.

이유는 기본적인 hashCode 메소드가 직접 만든 클래스에서는 제대로 작동을 하지 않는다.

해결법은 직접 hashCode 메소드를 정의를 해줘야 한다.

hashCode 메소드	해시코드를 만드는 메소드
hashCode	객체를 구별하는 고유의 정수 값

equals 메소드 또한 hashCode를 사용하기 때문에, equals 메소드도 다시 정의를 해줘야 한다.

(equals로 두 값이 같으면 hashCode가 같다고 인식을 한다)

위의 Point 클래스에 두 메소드를 오버라이딩 해준다.

 

 

자료구조 Treeset

 

TreeSet의 특징

1) 저장되는 데이터의 순서를 파악할 수 없다. 2) HashSet과 마찬가지로 데이터 중복 저장이 안된다. 3) 동기화를 하지 않는다. Collections.synchronizedSortedSet 메소드를 이용하여 wrapping 해주면 된다. 4) 이진탐색트리(BST)를 통해 데이터를 탐색한다.

TreeSet 또한 제네릭을 이용하여 저장 데이터를 결정하게 된다.

이진탐색트리(Binary Search Tree)

이진트리를 이용한 자료구조로 키 값에 따라 노드의 위치를 정의한 탐색트리 이진탐색트리 구조 1) 모든 노드는 유일한 키 값을 가진다. 2) 왼쪽 노드는 루트의 키 보다 작다. 3) 오른쪽 노드는 루트의 키보다 크다. 4) 모든 서브 트리도 이진탐색트리이다. TreeSet은 이진트리에 대한 개념이 필요하다. 이진트리에 대한 기초 지식을 배워오자.

TreeSet을 사용하기 위해서는 TreeSet을 import 해줘야 한다.

import.java.util.TreeSet;

Wrapper 클래스나 자신의 커스텀 클래스를 제네릭으로 넘겨서 사용하면 된다.

TreeSet<Integer> treeSet = new TreeSet<>():

TreeSet<Point> treeSetPoint = new TreeSet<>();

 

TreeSet 주요 메소드
형태	메소드	설명
boolean	add(E e)	e를 Set에 추가
void	clear()	Set의 데이터를 전부 삭제
boolean	contains(Object o)	Set에 o가 있다면 true, 없으면 false
E	first()	Set에서 가장 값이 낮은 원소를 반환
SortedSet<E>	headSet(E toElement)	toElement보다 낮은 요소를 반환
boolean	isEmpty()	Set이 비었으면 true, 아니면 false
int	size()	index 위치의 값을 반환(무한대 가능)
SortedSet<E>	subSet(E from, E to)	from부터 to까지 범위에 해당되는 요소를 반환
SortedSet<E>	tailSet(E fromElement)	fromElement보다 큰 요소 반환

subSet(E from, E to) -> from 이상 to 미만.. ex) subSet(1, 4) >> 1,2,3)

 

 

Wrapper클래스를 사용한 TreeSet 예제

 

 

 

 

HashSet, Iterator를 이용한 예제

 

 

import java.util.*;

public class C06SetMain {

	public static void main(String[] args) {
	//로또 만들기
	//set을 이용해서 6자리 난수 넣기
	//1-45 까지의 숫자
	//저장된 난수는 오름차순. 내림차순 둘다 출력
	//난수 만들기
	Set<Integer> set = new HashSet();
	Random random = new Random();

		while(set.size() != 6) {
			int num = ((int) (Math.random()*45+1));				
			set.add(num);
			}	
			
		Iterator<Integer> iter = set.iterator();
			
		while(iter.hasNext()) {
			System.out.println(iter.next());
			}
			
		 System.out.println();
		 List<Integer> list = new ArrayList(set);
			   
         //오름차순      
		 Collections.sort(list); 
			  
	     for (Integer num : list) {
		 System.out.print(num + " ");
			}
		 System.out.println();
		 
         //내림차순
		 Collections.sort(list,Collections.reverseOrder()); 
		 System.out.println();
			 
		 for (Integer num : list) {
				 
				System.out.print(num + " ");
		}
	    }
	}