글 작성자: ST_
728x90





 

•자료구조 관련 목록 링크 펼치기 

 

 

 





 

 

 







 

 

  • Set Interface

 




 

만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글을 먼저 보고 오셨으면 한다.

 

 

다른 자료구조 포스팅을 보셨다면 알겠지만, 자료구조를 구현하는 포스팅 하기 전에 인터페이스를 하나 만들고 시작하려 한다. Interface 장점이 해당 인터페이스를 implements 하는 클래스는 인터페이스에 선언 된 메소드들을 강제적으로 구현하도록 하고 있기 때문에 깜빡 잊어먹고 구현을 안하는 실수를 방지할 수 있다.

 

 

일단 셋(세트)(Set)에 대해 간략하게 설명하겠다.

 

Set은 쉽게 말해서 집합이라고 보시면 된다.

 

기본적으로 Set혹은 Set계열을 구현하는 클래스들은 다음과 같은 공통점이 있다.

1. 중복되는 요소(원소)를 허용하지 않는다.

2. 저장 순서를 유지하지 않는다. (LinkedHashSet 만 예외)

 

 

여기서 가장 눈여겨보아야 할 것은 '중복되는 요소를 허용하지 않는다.' 이다.

 

이전까지의 구현했던 자료구조는 중복 상관 없이 데이터를 추가했었지만, Set의 경우는 중복 요소를 허용하지 않는다. 이는 Java뿐만 아니라 다른 언어 또한 마찬가지다.

 

대강 이미지로 보자면 다음과 같다.

 

 

 

그리고 Set은 크게 HashSet, LinkedHashSet, TreeSet으로 나뉜다. 필자가 먼저 보고오라는 Java Collections FrameWork 글에서도 설명했지만, 여기서 한 번 더 간단하게 설명하고 가겠다.

 

먼저 HashSet이다. 가장 기본적인 Set 컬렉션의 클래스인데, 입력 순서를 보장하지 않고, 순서도 마찬가지로 보장되지 않는다. 그러면 어디에 쓰이냐는 생각이 들 수도 있다.

가장 쉽게 이해할 수 있는 예로는 여러분이 게임에서 '닉네임'을 만든다거나 아이디를 생성할 때 '중복확인'을 눌러 중복된 닉네임 또는 아이디인지 확인하는 것이다. 이는 데이터가 정렬되어있을 필요도 없고, 빠르게 중복되는 값인지만 찾으면 되기 때문에 유용한 방법이 될 수 있다.

좀 더 상세하게 말하자면 hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다. 즉, Hash 기능과 Set컬렉션이 합쳐진 것이 HashSet이다. 그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나다.

 

LinkedHashSet의 경우 이름에서 볼 수 있듯이 Link + Hash + Set 이 결합된 형태다. LinkedList에서 보면 add() 메소드를 통해 요소들을 넣은 순서대로 연결한다. 즉, LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미다.

Set의 경우 기본적으로 입력 순서대로의 저장순서를 보장하지 않아 '중복은 허용하지 않으면서 순서를 보장받고 싶은경우'에는 불편할 수밖에 없다. 이를 보완하기 위해 존재하는 것이 바로 LinkedHashSet인 것이다. 실생활에서 그나마 예로 들자면 페이지를 열 때 만약 해당 페이지가 중복되경우 cache는 다시 적재할 필요는 없지만, 새로운 페이지를 할당해야 할 경우 최근에 사용되지 않은 cache을 비우고자 할 때, 가장 오래된 cache를 비우는 것이 현명할 것이다. 이를 LRU 알고리즘(Least Recently Used Algorithm)이라고 하는데, 이럴 때 입력된(저장된) 순서를 알아야 오래된 캐시를 비울 수 있다. 이에 적용할 수 있는 자료구조 중 하나다. (현실적으로는 LRU기법으로 LinkedHashMap이라는 자료구조가 대부분을 차지하고 있어 많이 쓰이진 않으나 그나마 이해하기 쉬운 예시를 위해..)

 

 

TreeSet은 HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다. 다만 특별한 점이 있다면 SortedSet Interface의 이름을 보면 알 수 있듯 이를 구현한 TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 보장한다는 것이다. 앞서 PriorityQueue를 생각해보자. 데이터들이 입력한 순서대로가 아닌 값에 따라 정렬되어 Queue에 담아진다. 마찬가지로 TreeSet은 '중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다. 정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용하다.

(Tree 라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것이다.)

 

 

 

 

 

더보기

 

참고로 자바에서 제공하고 있는 Set계열 클래스들은 구체적으로 말하자면 기본적으로 Map으로 구현되어있다. 즉, 겉으로는 Set이지만, 내부를 보면 Map으로 생성하여 구현되고 있다는 말이다.

참고로 Set과 Map의 차이는 Set은 값만을 갖지만 Map은 key-value(키-값)쌍으로 이루어진 자료구조다.

 

즉, 어디까지나 실질적으로는 HashSet의 경우 HashMap으로, LinkedHashSet의 경우 LinkedHashMap, TreeSet의 경우 TreeMap으로 구현되나, Set을 다루면서 Map까지 같이 설명하면서 쓰기에는 이해하기도 어렵고, 무엇보다 Set이 무엇인지를 이해하는데 초점을 맞춰야 하기에 Map으로 구현하지는 않을 것이다.

 

(지금 당장으로는 Set의 경우 Map을 생성하고 데이터를 넣을 때 값(data)은 Map의 key가 되고, value는 빈 오브젝트로 동일하게 들어간다는 점만 아시면 된다.)

 

 

 

 

 

 

 

 

 

그럼 이제 Set 인터페이스에 선언 할 메소드들을 살펴보도록 하겠다.

 

 

<Set Interface에 선언 할 메소드>

 

 

 

 

이후에 TreeSet을 다루면 알겠지만, 이 Set인터페이스를 상속하여 SortedSet이란 인터페이스를 구현하기도 한다. 이 부분은 나중에 다루기로 하고 일단은 위 메소드를 중점으로 보자.

 

 

전체적으로 보자면 Set인터페이스를 구현하는 것은 HashSet, LinkedHashSet, TreeSet 정도가 있고, 앞으로 이 세가지를 구현해보고자 한다.

 

 

혹여 더 많은 메소드를 보고싶다면 아래 API 문서를 참고하시면 된다.

 

docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Set.html

 

Set (Java SE 11 & JDK 11 )

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction. The Set inter

docs.oracle.com

 

 

 

 

필자는 이를 토대로 앞으로 구현해나갈 것이니 참고하시길 바란다.

 

package Interface_form;

/**
 * 
 * 자바 Set Interface입니다. <br>
 * Set은 HashSet, LinkedHashSet, 
 * TreeSet에 의해 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this Set
 *
 * @version 1.0
 * 
 */

public interface Set<E> {

	/**
	 * 지정된 요소가 Set에 없는 경우 요소를 추가합니다. 
	 * 
	 * @param e 집합에 추가할 요소
	 * @return {@code true} 만약 Set에 지정 요소가 포함되지 않아 정상적으로 추가되었을 경우,
	 *         else, {@code false}
	 */
	boolean add(E e);
	
	/**
	 * 지정된 요소가 Set에 있는 경우 해당 요소를 삭제합니다.
	 * 
	 * @param o 집합에서 삭제할 특정 요소
	 * @return {@code true} 만약 Set에 지정 요소가 포함되어 정상적으로 삭제되었을 경우,
	 *         else, {@code false}
	 */
	boolean remove(Object o);
	
	/**
	 * 현재 집합에 특정 요소가 포함되어있는지 여부를 반환합니다.
	 * 
	 * @param o 집합에서 찾을 특정 요소
	 * @return {@code true} Set에 지정 요소가 포함되어 있을 경우,
	 *         else, {@code false}
	 */
	boolean contains(Object o);
	
	/**
	 * 지정된 객체가 현재 집합과 같은지 여부를 반환합니다.
	 * 
	 * @param o 집합과 비교할 객체
	 * @return {@code true} 비교할 집합과 동일한 경우,
	 *         else, {@code false}
	 */
	boolean equals(Object o);
	
	/**
	 * 현재 집합이 빈 상태(요소가 없는 상태)인지 여부를 반환합니다.
	 * 
	 * @return {@code true} 집합이 비어있는 경우,
	 *         else, {@code false}
	 */
	boolean isEmpty();
	
	/**
	 * 현재 집합의 요소의 개수를 반환합니다. 만약 들어있는 요소가
	 * {@code Integer.MAX_VALUE}를 넘을 경우 {@code Integer.MAX_VALUE}를 반환합니다.
	 * 
	 * @return 집합에 들어있는 요소의 개수를 반환
	 */
	int size();
	
	/**
	 * 집합의 모든 요소를 제거합니다.
	 * 이 작업을 수행하면 비어있는 집합이 됩니다.
	 */
	void clear();
}

 

 

 

 

이 번에 메인으로 구현할 Set의 경우 각 구현되는 클래스마다 특징과 구현 방법이 많이 상이하고 복잡하기 때문에 이전의 자료구조들을 정확히 구현할 줄 알고 가는 것이 좋다.

 

또한 기본적으로 여러분들이 재정의(Override), 예외처리(throw), 객체(Object), 인터페이스(nterface), 제네릭(Generic) 이렇게 5개에 대한 기본 지식은 있다는 전제하에 설명 할 것이다. 그렇지 않고 하나하나 설명하다보면 길이 너무 길어져 핵심을 못짚게 되어 결정했다.

 

 

 

 

 

 







  • 정리

 



 

오늘은 간단하게 Set에 대해 알아보고 앞으로 사용할 Set Interface를 간단하게 만들어놓았다. 이를 토대로 HashSet, LinkedHashSet, TreeSet 클래스들을 구현할 것이다. 혹여 앞으로의 포스팅에 있어 모르거나 헷갈리는 것이 있다면 언제든 댓글 남겨주시면 감사하겠다.

 

 

 

 

 

 

 

 

 

 

 

저작자표시 비영리 변경금지

'자료구조 > Java' 카테고리의 다른 글

자바 [JAVA] - Linked Hash Set (연결 해시 셋) 구현하기  (2) 2021.07.02
자바 [JAVA] - Hash Set (해시 셋) 구현하기  (14) 2021.04.14
자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기  (24) 2021.03.04
자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기  (52) 2021.02.10
자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기  (6) 2020.12.17

티스토리툴바