[자료구조] Java 집합(Set)

 

집합(Set)이란? 

 Java에서 집합 자료구조는 Set 인터페이스를 구현한 Set 컬렉션 클래스를 사용하며,

 대표적으로 HashSet<E>, TreeSet<E>가 있다. 

 

 Set 인터페이스는 Collection 인터페이스를 상속받으며,

Collection 인터페이스에서 정의 한 메소드는 모두 사용할 수 있으며, 주요 메소드는 다음과 같다. 

메소드	설명
boolean add(E e)	전달된 요소를 추가.
boolean contains(Object o)	전달된 객체를 포함하는지 확인.
boolean equals(Object o)	전달된 객체와 같은지 확인.
boolean remove(Object o)	전달된 객체와 같은 객체를 제거.
boolean isEmpty()	비어있는지를 확인.
void clear()	모든 요소 제거.
int size()	요소의 총 개수 반환.
Object[] toArray()	요스를 배열로 반환.
Iterator<E> iterator()	반복자를 반환

 Set인터페이스를 구현한 대부분의 Set 컬렉션 클래스는 두가지의 특징을 갖는다.

  1. 요소의 저장 순서를 유지하지 않는다.

  2. 같은 요소의 중복 저장을 허용하지 않는다.

 

HashSet

저장 순서가 유지되지 않는다.

(저장 순서를 유지하고 싶으면 LinkedHashSet 클래스를 사용한다.)

해시 알고리즘을 사용하여 검색 속도가 매우 빠르며,

내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다.

 

탐색은 for each문 or Iterator를 사용하며, 아래 코드와 같이 탐색한다.

import java.util.HashSet;
import java.util.Iterator;

public class HashSet_ex {
	public static void main(String[] args) {
		HashSet<String> setTest = new HashSet<String>();
		
		setTest.add("집합");
		setTest.add("해시셋");
		setTest.add("저장순서유지안돼");
		setTest.add("해시알고리즘사용");
		setTest.add("집합");
		
        //for each문을 이용한 탐색
		for(String s : setTest) {
			if(s.equals("집합"))
            	System.out.println(s);
		}
        
        //Iterator를 이용한 탐색
		Iterator<String> it = setTest.iterator();
		while(it.hasNext()) {
			String s = it.next();
			if(s.equals("집합")) 
            	System.out.println(s);;
		}
	}
}

 

중복 요소를 추가하려고 하면, 해당요소는 저장하지 않고 false를 반환한다.

이때 중복 요소를 판단하기 위해서 내부적으로 2가지 과정을 거치게된다.

1. 해당 요소에서 hashCode() 메소드를 호출하여 반환된 해시값으로 검색할 범위를 결정한다.

2. 해당 범위내의 요소들을 equals() 메소드로 비교한다.

따라서 add() 메소드를 사용하여 중복 없이 새로운 요소를 추가하기 위해서는

hashCode()와 equals() 메소드를 상황에 맞게 오버라이딩 해야한다.

아래 예제는 사용자 정의 클래스의 인스턴스를 HashSet에 저장하기 위해

hashCode()와 equals() 메소드를 오버라이딩한 예제이다.

class Phone_book {
    String name;
    String number;
    Phone_book(String name, String number) {
    	this.name = name;
    	this.number = number;
	}
 
	public int hashCode() { 
    	return (name + number).hashCode(); 
    }
    public boolean equals(Object obj) {
       	if(obj instanceof Phone_book) {
           	Phone_book tmp = (Phone_book)obj;
           	return name.equals(tmp.name) && number.equals(tmp.number);
       	} else {
           	return false;
       	}
    }
}
 
public class HashSet_ex2 {
   	public static void main(String[] args) {
       	HashSet<Phone_book> setTest = new HashSet<Phone_book>();
        
	    setTest.add(new Phone_book("홍길동", "010-xxxx-xxxx"));
      	setTest.add(new Phone_book("홍길동", "010-yyyy-yyyy"));
       	setTest.add(new Phone_book("홍길동", "010-xxxx-xxxx"));
	 
     	//중복확인.
     	System.out.println(setTest.size());
    }
}

 

TreeSet

이진 검색 트리의 형태로 요소를 저장하는 집합으로 정렬된 상태로 요소가 저장된다.

이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작시간이 매우 빠르다.

TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.

 

 

집합의 연산

연산으로 합집합, 교집합, 차집합, 부분집합등이 있으며, 예제 코드는 다음과 같다.

import java.util.HashSet;

public class Set_Test {
	public static void main(String[] args) {
		HashSet<Integer> test1 = new HashSet();	// 1 2 3 
		HashSet<Integer> test2 = new HashSet();	// 3 4 5
		HashSet<Integer> test3 = new HashSet();	// 1 2
		
		test1.add(1);
		test1.add(2);
		test1.add(3);
		
		test2.add(3);
		test2.add(4);
		test2.add(5);
		
		test3.add(1);
		test3.add(2);
		
		// (1 2 3) ∪ (3 4 5) = (1 2 3 4 5) 합집합
		// 중복된 요소는 1개만 포함하여 요소를 합한 집합을 생성.
		test1.addAll(test2);
		
		// (1 2 3) ∩ (3 4 5) = (3) 교집합
		// 중복된 요소로 이루어진 집합을 생성.
 		test1.retainAll(test2);	
		
 		// (1 2 3) - (3 4 5) = (1 2) 차집합
		// test1 집합에서 test1과 test2의 교집합을 제거한다.
		test1.removeAll(test2);	
		
		//부분집합
		//test1의 부분집합이면 true 아니면 false를 반환한다.
		test1.containsAll(test2);	// (1 2 3) ≠ (3 4 5) false.
		test1.containsAll(test3);	// (1 2 3) ⊃ (1 2) true.
	}
}