[자료구조, Java] Set 개념 및 활용

개념

Set은 Map과 더불어 프로그래머로써 필수적으로 알아야 할 자료구조 중 하나입니다.

Set/Map을 구현한 종류로는 Tree와 Hash가 있는데, 두 가지의 개념 및 Java Collection을 통한 활용을 할 예정입니다.

 

어떤 것으로 구현했느냐에 따라, 값 추가와 탐색 방법이 상이하며, 그에 따라 구현 방법별 값 추가와 탐색의 시간 복잡도가 다르게 됩니다.

 

일반적으로 Hash가 Tree보다 더 빠르므로, 자주 사용됩니다.

 

Hash

HashSet을 설명드리기 전에, Hash에 대한 이해가 필요하다고 생각됩니다.

Set을 배우는 단계에서 Tree는 이미 알고 오셨을 가능성이 높으나, Hash는 아직 생소한 단어일 것이라 생각 되어, 따로 설명드립니다(Tree는 개념 자체는 설명하지 않을 예정입니다).

 

Hash는 값을 저장하고 조회하는데 있어 가장 빠른 알고리즘입니다.

그 메커니즘으로는, 저장하고자 하는 값을 어떤 값과도 중복되지 않는 숫자 코드로 변환(이를 해시 코드라 지칭)하여 해당 코드의 메모리 위치에 값을 저장하는 방법입니다.

저장을 그림으로 설명드리자면, 다음과 같습니다.

따라서, 저장하려는 값을 일련의 공식을 통해 해시코드로 변환된 값이, 저장되는 위치입니다.

그렇기 때문에, 값을 조회할 경우에도 저장된 값만 알고 있다면, 해시 코드로 변환하여 곧바로 그 주소에 다가가 안에 어떠한 값이 저장되어 있는지 알 수 있습니다.

탐색을 한 번 그림으로 나타내자면,

보여드린 저장과 탐색 방법에 따라, 다음과 같은 시간 복잡도가 나오게 됩니다.

- 저장 : O(1)

- 탐색 : O(1)

 

이런 식으로 값을 고유한 코드(해시코드)로 변환하여 해당 코드 위치에 값을 저장하고 조회하는 방법을 해시 테이블(=해시)라고 합니다.

 

HashSet

위 해시의 내용대로 값을 저장한 방식이 바로 HashSet입니다.

Set은 비선형 자료구조이기 때문에 저장한 순서대로 값이 저장되지 않고, 따라서 출력 또한 저장된 순서대로 출력되지 않는 특징을 갖고 있습니다.

또한, 값의 중복을 허용하고 있지 않습니다. 해시의 경우 값 자체가 메모리 주소가 되기 때문에, 같은 위치에 두 개의 값을 저장할 수는 없고, 한 번만 저장됩니다.

 

Iterator

자바의 컬렉션에 존재하는 값들을 읽어오기 위한 방법으로 'iterator'라는 클래스가 존재합니다.

이 iterator는 해당 컬렉션의 주소값을 기반으로 하나씩 값을 조회하는 클래스입니다.

따라서, 대표적으로 다음과 같은 두 개의 함수가 존재합니다.

hasNext() : 다음 값을 갖고 있는지 true/false 반환

next() : 다음 값으로 이동 및 반환

 

자바에서는 각각의 컬렉션별로 Iterator를 반환하는 함수를 갖고 있고, 이 함수는 컬렉션의 첫 번째 주소 값을 반환하는 형식으로 되어있습니다.

Iterator를 이용해 컬렉션을 추출하는 방법은

'첫 번째 주소를 담은 Iterator 생성 -> 반복문을 통해 하나씩 이동하며 저장된 값 반환' 입니다.

이를 코드로 나타내면 다음과 같습니다,

Iterator<String> setIter = hSet.iterator(); // 만든 hSet의 iterator 정보를 담은 setIter 변수 생성(hSet 자료형과 동일하게 생성)
while(setIter.hasNext()) { // 값이 존재할때까지 반복
	String str1 = setIter.next(); // hSet의 다음 값 가져오기
	System.out.print(str1 + " "); // 출력
}

 

HashSet 활용

package Set_Map.Set;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class SetPractice {
	public static void main(String[] args) {
		/* HashSet 사용법 */
		
		// HashSet 선언 방법
		Set<String> hSet = new HashSet<String>(); // 자료형 지정 
		Set<String> hSet2 = new HashSet<>(); // 좌측 선언부만 자료형 지정
		Set<String> hSet3 = new HashSet<String>(Arrays.asList("a", "b")); // 생성 시 값 초기화
		
		// 좌축 클래스를 HashSet으로 해도 Set과 동일
		HashSet<String> hSet4 = new HashSet<String>();
		HashSet<String> hSet5 = new HashSet<>();
		HashSet<String> hSet6 = new HashSet<String>(Arrays.asList("a", "b"));
		
		// 값 추가
		hSet.add("e");
		hSet.add("c");
		hSet.add("g");
		hSet.add("f");
		hSet.add("d");
		hSet.addAll(hSet3); // "a", "b"가 들어있는 HashSet 추가
		
		System.out.println("-Contain Test");
		System.out.println("a 포함 여부 : " + hSet.contains("a")); // 추가된 "a" 포함 여부 출력
		System.out.println("hSet3 변수 포함 여부 : " + hSet.containsAll(hSet3)); // 추가된 hSet3 변수 포함 여부 출력
		System.out.println();
		
		// 출력 방법 1: iterator 사용
		System.out.println("-Output Test");
		System.out.println("출력방법 1 : iterator 사용");
		Iterator<String> setIter = hSet.iterator(); // 만든 hSet의 iterator 정보를 담은 setIter 변수 생성(hSet 자료형과 동일하게 생성)
		while(setIter.hasNext()) { // 값이 존재할때까지 반복
			String str1 = setIter.next(); // hSet의 다음 값 가져오기
			System.out.print(str1 + " "); // 출력
		}
		System.out.println("\n");
		
		// 출력방법 2 : 내장된 foreach 함수 사용
		System.out.println("출력방법 2 : 내장된 foreach 함수 사용");
		hSet.forEach(System.out::print);
		System.out.println("\n");
		
		// 출력방법 3 : forEach 사용
		System.out.println("출력방법 3 : forEach 사용");
		for(String c : hSet) {
			System.out.print(c + " ");
		}
		System.out.println();
		
		String str = "abc";
		System.out.println(str.hashCode());
	}
}

 

Tree

해시에 이어 이번엔 Tree입니다.

이번 게시글에서는 Tree에 대해 상세하게 설명하지 않을 예정이며, Tree에 대한 내용은 이전 내용을 참조해 주시길 바랍니다.

TreeSet에 사용되는 트리의 종류는 이진트리 기반의 레드-블랙 트리입니다.

단순히 자식 노드가 최대 2개가 될 수 있는 이진 트리 개념에 더하여, 한 노드를 기준으로 적은 값은 왼쪽에, 큰 값은 오르 쪽에 저장하는 개념을 추가한 것이 레드-블랙 트리입니다.

이진트리와 레드-블랙 트리를 비교하자면 다음과 같습니다.

기능 및 사용 방법

HashSet, TreeSet은 구현 및 저장, 조회 방법만 다를 뿐 사용하는 방법은 동일합니다.

다만, 시간 복잡도는 구현의 차이로 인해 차이가 있고, TreeSet은 다음과 같은 시간 복잡도를 갖고 있습니다.

저장 : O(log n)

탐색 : O(log n)

다른 자료구조들에 비해 빠른 시간 복잡도를 갖고 있지만, O(1)인 HashSet에 비해서는 부족해 보이죠. 그렇기 때문에 Set을 이야기할 때는 주로 HashSet을 가리켜 말하곤 합니다.

 

TreeSet 활용

상세한 내용을 HashSet과 비교하실 필요는 없습니다. 앞서 말씀드렸다시피 사용 방법이 HashSet과 완전히 동일하기 때문에 코드 또한 변수명들을 제외하고는 모든 내용이 동일하기 때문입니다.

package Set_Map.Set;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class SetPractice {
	public static void main(String[] args) {
		/* TreeSet 활용 방법 */
		Set<String> tSet = new TreeSet<String>(); // 자료형 지정 
		Set<String> tSet2 = new TreeSet<>(); // 좌측 선언부만 자료형 지정
		Set<String> tSet3 = new TreeSet<String>(Arrays.asList("a", "b")); // 생성 시 값 초기화
		
		// 좌축 클래스를 HashSet으로 해도 Set과 동일
		TreeSet<String> tSet4 = new TreeSet<String>();
		TreeSet<String> tSet5 = new TreeSet<>();
		TreeSet<String> tSet6 = new TreeSet<String>(Arrays.asList("a", "b"));
		
		// 값 추가
		tSet.add("e");
		tSet.add("c");
		tSet.add("g");
		tSet.add("f");
		tSet.add("d");
		tSet.addAll(tSet3); // "a", "b"가 들어있는 HashSet 추가
		
		System.out.println("-Contain Test");
		System.out.println("a 포함 여부 : " + tSet.contains("a")); // 추가된 "a" 포함 여부 출력
		System.out.println("tSet3 변수 포함 여부 : " + tSet.containsAll(tSet3)); // 추가된 hSet3 변수 포함 여부 출력
		System.out.println();
		
		// 출력 방법 1: iterator 사용
		System.out.println("-Output Test");
		System.out.println("출력방법 1 : iterator 사용");
		Iterator<String> treeIter = tSet.iterator(); // 만든 hSet의 iterator 정보를 담은 setIter 변수 생성(hSet 자료형과 동일하게 생성)
		while(treeIter.hasNext()) { // 값이 존재할때까지 반복
			String str1 = treeIter.next(); // hSet의 다음 값 가져오기
			System.out.print(str1 + " "); // 출력
		}
		System.out.println("\n");
		
		// 출력방법 2 : 내장된 foreach 함수 사용
		System.out.println("출력방법 2 : 내장된 foreach 함수 사용");
		tSet.forEach(System.out::print);
		System.out.println("\n");
		
		// 출력방법 3 : forEach 사용
		System.out.println("출력방법 3 : forEach 사용");
		for(String c : tSet) {
			System.out.print(c + " ");
		}
		System.out.println();
		
		String str = "abc";
		System.out.println(str.hashCode());
	}
}