Set 자료구조의 특징

순서가 없고(LinkedHashSet을 제외하고), 데이터의 유일성을 가지는 자료구조

중복: 중복 불가능, 유일성을 가짐
순서: 순서 보장X (LinkedHashSet 제외)
정렬: 불가능 -> TreeSet 클래스 가능
동기화: (Thread-Safe): 동기화 불가능, 불안전

주요 메소드

• add(Object o): 데이터 추가
• remove(Object o): 데이터 삭제(없다면 false 반환)
• clear(): 데이터 모두 삭제
• size(): 크기
• contains(Object): 값이 있는지 여부(boolean)
• Iterator< E >iterator(): 반복자(iterator) 반환
• isEmpty(): Set이 비어있는지 확인

HashSet

HashMap과 Set 인터페이스를 상속하여 빠른 연산이 가능한 자료형

• 가장빠른 임의 접근 속도
• 순서를 예측할 수 없음
• 정렬이 불가능함
• null을 허용

시간 복잡도

add : O(1)
contains : O(1)
next : o(h/n) h는 테이블 용량

TreeSet

Tree와 Set을 상속한 연산이 느려도 다양한 정렬을 지원하는 자료형

• 삽입과 동시에 정렬되는 상태를 유지함.
• HashSet 보다는 삽입이 느림
• 다양한 정렬 방법을 지정할 수 있음
• null을 허용X
  
  TreeSet은 이진검색트리 구조(root와 node)이기 때문에 HashSet과는 다르게 추가된 메서드들이 존재한다.

  • SortedSet headSet(Object o) : 지정된 객체(데이타)보다 작은 값의 객체들을 반환한다.
  • SortedSet tailSet(Object o) : 지정된 객체(데이타)보다 큰 값의 객체들을 반환한다.
  • Object pollFirst() : TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환한다.
  • Object pollLast() : TreeSet의 마지막 번째 요소(제일 큰 값의 객체)를 반환한다.

시간 복잡도

add : O(log n)
contains : O(log n)
next : o(log n)

LinkedHashSet

저장순서를 유지하고 관리하는 HashSet이다. 하지만 인덱스로 접근할 수 없어 데이터에 하나하나 접근하기 위해서는 Iterator 객체를 생성해야 한다.
예시코드

import java.util.Iterator;
import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
	public static void main(String[] args)  {
		LinkedHashSet<String> str = new LinkedHashSet<String>(); // LinkedHashSet 선언
		
		// 값 추가
		str.add("Hello1");
		str.add("World2");
		str.add("Hello3");
		str.add("World4");
		
		/* Iterator를 사용 HashSet 배열 출력 */
		Iterator iter = str.iterator();
		while(iter.hasNext())
			System.out.print(iter.next() + " ");
	}
}

시간 복잡도

add : O(1)
contains : O(1)
next : o(1)