[JAVA] Set 컬렉션 클래스에 대하여

Set 컬렉션 클래스

Set 컬렉션 클래스는 Set 인터페이스를 구현한 클래스이다. Set 컬렉션 클래스는 요소의 저장 순서를 유지하지 않고, 같은 요소의 중복 저장을 허용하지 않는다. 따라서 중복을 제거해야 하거나 저장 순서가 중요하지 않을 때 자주 사용되는 컬렉션 클래스이다.

 

이러한 Set 컬렉션 클래스에 속하는 대표적인 클래스는 다음과 같다.

 

1. HashSet<E>

2. TreeSet<E>

 

간단하게 이 두 가지 클래스에 대해 알아보자.

 

HashSet<E> 클래스

HashSet 클래스는 Set 컬렉션 클래스에서 가장 많이 사용되는 클래스이다. HashSet 클래스는 hash 알고리즘을 사용하여 검색 속도가 매우 빠르다. 이러한 HashSet 클래스는 내부적으로  HashMap 인스턴스를 이용하여 요소를 저장한다.

 

HashSet 클래스는 Set 인터페이스를 구현하기 때문에, 요소의 저장 순서를 유지하지 않고 중복된 값은 저장하지 않는다.

 

아래의 간단한 예제를 통해 몇 가지 메서드에 대해서만 알아보자.

 

 

HashSet<String> set =  new HashSet<String>();

// add() 메서드 : 요소의 저장, 순서 X, 중복 X
set.add("아이유");
set.add("제니");
set.add("로제");
set.add("태연");
set.add("태연");


// remove() 메서드 : 요소의 삭제
set.remove("로제");


// Enhanced for 문을 이용한 순회
for(String value : set){
	System.out.println(value);
}

// size() 메서드 : set의 사이즈, 즉 요소의 총 개수 반환
System.out.println(set.size());

 

실행결과

 

[그림 1] 예제 실행결과

실행결과를 보면, "태연" 요소를 두 번 넣었음에도 중복으로 저장되지 않는다는 사실과, 순서가 보장되지 않는다는 것을 확인할 수 있다.

 

이처럼 HashSet은 요소를 삽입할 때 이미 존재하는 요소인지를 파악하기 위해 내부적으로 다음과 같은 과정을 거친다.

 

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

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

 

따라서, 사용자가 직접 설계한 클래스의 인스턴스를 HashSet에 저장하기 위해서는 hashCode()와 equals() 메서드를 오버라이딩 해야만 한다.

 

예를 들어 아래와 같은 상황을 보자.

	public static void main(String[] args) {
		HashSet<Point> set =  new HashSet<>();
		set.add(new Point(1,1));
		set.add(new Point(1,1));
		
		// 출력 결과 : 2
		System.out.println(set.size());
	}
	
	// 좌표를 저장하는 클래스
	public static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x  = x;
			this.y = y;
		}
	}

 

위처럼 좌표를 저장하는 클래스를 만들었다고 해보자. 알고리즘 문제를 해결해본 사람이라면 저런 클래스를 생각보다 자주 만드는 경우가 있을 것이다. 사용자의 의도는 set에 좌표를 넣어 중복을 제거하려고 했다고 하면, 의도와는 다르게 중복된 좌표가 들어가게 된다. 즉, set의 사이즈는 1이어야 하는데 2가 되어버린다.

 

중복된 요소가 들어가는 이유는 사용자가 정의한 클래스가 hashCode()와 equals() 메서드를 오버라이딩 하지 않았기 때문이다.

 

따라서 아래와 같이 오버라이딩 해주면 문제가 해결된다.

 

	public static void main(String[] args) {
		HashSet<Point> set =  new HashSet<>();
		set.add(new Point(1,1));
		set.add(new Point(1,1));
		
        // 출력 결과 : 1
		System.out.println(set.size());
		
	}
	
	// 좌표를 저장하는 클래스
	public static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x  = x;
			this.y = y;
		}
		
		@Override
		public int hashCode() {
			return (String.valueOf(x) + String.valueOf(y)).hashCode();
		}
		
		@Override
		public boolean equals(Object obj) {
			if(obj instanceof Point) {
				Point temp = (Point)obj;
				return x== temp.x && y == temp.y;
			}else {
				return false;
			}
		}
	}

 

참고 :
중간에 hashCode() 메서드를 보면 조금 복잡해 보일 수 있다. 
간단하게 return (x+y).hashCode() 를 하면 안 될까? 

잘 생각해보면 좌표의 합은 다른 좌표여도 같을 수 있다. (2,3)과 (3,2)는 다른 좌표이지만 합은 5로 똑같다.
따라서 좌표의 합을 hashCode로 사용하면 둘은 다른 클래스이지만 같은 hashCode를 가져버리게 된다.
하지만 String으로 변환해서 만든다면 (2,3) 은 "23", (3,2)는 "32"가 되어 다른 hashCode를 가지게 된다.

 

Hash에 대해 더 자세히 알고 싶다면 다음 글을 참고하자.

 

[자료구조] 해시 테이블(Hash Table) 이란? | 해시 알고리즘 | 해시 함수

[자료구조] 해시 테이블(Hash Table) 이란? | 해시 알고리즘 | 해시 함수

 

 

 

TreeSet<E> 클래스

TreeSet 클래스는 특이하게 요소들을 정렬해서 저장한다. JDK 1.2부터 제공되는 TreeSet 클래스는 내부적으로 레드-블랙 트리를 이용해 요소를 저장한다. 

 

레드-블랙 트리에 대해 자세히 알고 싶다면 다음을 참고하자.

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

 

TreeSet도 Set 인터페이스를 구현하기 때문에 중복을 허용하지 않는다. 따라서 TreeSet은 요소의 순서를 정렬해서 사용하고, 중복을 허용하지 않기 위해서 사용할 수 있다. 

 

다음 예제를 살펴보자.

 

TreeSet<Integer> set = new TreeSet<Integer>();

// add() 메서드 : 요소의 저장, 저장 순서 X, 중복 X, but 정렬 O
set.add(30);
set.add(10);
set.add(20);
set.add(50);

// remove() 메서드 : 요소의 삭제
set.remove(50);

// Enhanced for 문을 이용한 순회
for(Integer cur : set){
	System.out.println(cur);
}

 

실행결과 :

[그림 2] TreeSet 예제

위처럼 요소가 오름차순으로 정렬되었음을 알 수 있다.

 

 

 

---

참고

 

1. http://www.tcpschool.com/java/java_collectionFramework_set