[Java] Set 인터페이스와 클래스 - 총정리

지난번에 자바의 다양한 Java.Utill 패키지에 포함되는 Collection 자료구조들을 정리하였다.

https://bangu4.tistory.com/194

[Java] Java Collection 구조 정리

 

이번에는 Collecition 인터페이스 3가지중 Set부터 하나씩 정리해보겠다.

 

 

Set 인터페이스

순서가 없고, 데이터 유일성을 가지는 자료구조

Set은 인터페이스이며 이를 상속하여 구현된 클래스중 가장 잘 사용되는 클래스는 총 두가지이다.

HashSet, TreeSet 이다.

이외에 LinkedHashSet가 존재하지만 Set의 특성을 가지지않고, 성능이 좋지않아 잘 사용하지 않는다.

 

Set 인터페이스 메소드

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

Collection 인터페이스에서 정의한 메소드도 모두 사용할 수 있습니다.

Set 인터페이스에서 제공하는 주요 메소드는 다음과 같습니다.

boolean add(E e)	해당 집합(set)에 전달된 요소를 추가함. (선택적 기능)
void clear()	해당 집합의 모든 요소를 제거함. (선택적 기능)
boolean contains(Object o)	해당 집합이 전달된 객체를 포함하고 있는지를 확인함.
boolean equals(Object o)	해당 집합과 전달된 객체가 같은지를 확인함.
boolean isEmpty()	해당 집합이 비어있는지를 확인함.
Iterator<E> iterator()	해당 집합의 반복자(iterator)를 반환함.
boolean remove(Object o)	해당 집합에서 전달된 객체를 제거함. (선택적 기능)
int size()	해당 집합의 요소의 총 개수를 반환함.
Object[] toArray()	해당 집합의 모든 요소를 Object 타입의 배열로 반환함.

 

1. Set 자료구조의 특징 

- 중복 : 중복 불가능 , 유일성을 가짐
- 순서 : 예측 불가능
- 정렬 : 정렬 불가능 ->  TreeSet 클래스 가능
- 동기화 (Thread-Safe) : 동기화 불가능, 불안전함

 

기본적은 Set은 정렬이 불가하지만, 이를 보안하고 등장한게 TreeSet이다.

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

LinkedHashSet은 LinkedList로 연결된 HashSet이라 할 수 있고, 입력 순서를 보장해준다.

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

• HashSet
  - 가장빠른 임의 접근 속도
  - 순서를 예측할 수 없음
  - 정렬이 불가능함
• TreeSet
  - 삽입과 동시에 정렬되는 상태를 유지함.
  - HashSet 보다는 삽입이 느림
  - 다양한 정렬 방법을 지정할 수 있음

 

 

 

2. 주요 메소드

1) HashSet

 

객체생성과 초기화 (삽입), 출력 

	public static void main(String[] args) {
		HashSet<Integer> set1 = new HashSet<>(Arrays.asList(1,2,3)); // 리스트형으로 초기화를 한번에
		HashSet<Integer> set2 = new HashSet<>();	// 객체생성후 나중에 초기화
		for (int i = 0; i <= 10; i++) 
			set2.add(i);			// add() 반복문 초기화가 일반적임

		// for 출력
		for(int i : set1)
			System.out.print(i + " ");
		
		// Iterator 출력 (Collection은 모두가능)
		Iterator<Integer> it = set2.iterator();
		System.out.println("\n");
		while(it.hasNext())
			System.out.print(it.next() + " ");
	}

 

조회 / 삭제

	public static void main(String[] args) {
		HashSet<Integer> set1 = new HashSet<>(Arrays.asList(1,2,3)); // 리스트형으로 초기화를 한번에
		HashSet<Integer> set2 = new HashSet<>();	// 객체생성후 나중에 초기화
		for (int i = 0; i <= 10; i++) 
			set2.add(i);			// add() 반복문 초기화가 일반적임

		// for 출력
		for(int i : set1)
			System.out.print(i + " ");
		
		// Iterator 출력 (Collection은 모두가능)
		Iterator<Integer> it = set2.iterator();
		System.out.println("\n");
		while(it.hasNext())
			System.out.print(it.next() + " ");
		
		// 존재하면 삭제시 true , 아니면 False 반환
		System.out.println("\n\n"+set1.remove(1));
		System.out.println(set1.remove(1));
		
		// contains를 통해 존재여부 검색
		System.out.println("\n"+set1.contains(1));
		System.out.println(set2.contains(1));
	}

 

정렬

	public static void main(String[] args) {
		HashSet<Integer> set = new HashSet<>(Arrays.asList(5,2,3,7,10,4)); // 리스트형으로 초기화를 한번에
		
		// 리스트로 받아서 Collections.sort !
		ArrayList<Integer> arr = new ArrayList<Integer>(set);
		Collections.sort(arr);
		for(int i: arr)
			System.out.println(i);
			
	}

위와같이 set을 리스트로 받아서 sort해줄수 있지만,

알고리즘 문제상에서는 효율적이지 못하므로 TreeSet을 사용합니다.

 

 

 

2) TreeSet

정렬 특화되어 있으므로, 최대값, 최솟값 반환 메소드와 통계메소드를 제공함

 first() / last() 

• 가장 큰 값 / 가장 작은 값 반환

 lower() / higher() / floor() / ceiling()

• lower : 제공된 값보다 작은 값 중 가장 큰 값 (인자값 미포함)
• higher : 제공된 값보다 큰 값 중 가장 작은 값 (인자값 미포함)
• floor : 제공된 값과 같거나 작은 값 중 가장 큰 값 (인자값 포함)
• ceiling : 제공된 값보다 크거나 같은 값 중 가장 작은 값 (인자값 포함)

 

객체생성과 정렬

public static void main(String[] args) {
		TreeSet<Integer> tset = new TreeSet<Integer>(Arrays.asList(5,1,6,8,12,86,44));
		// 오름차순 정렬
        for(int i : tset)
			System.out.println(i);
		System.out.println();
            
        // descendingSet 역순 정렬 
		for(int i : tset.descendingSet())
			System.out.print(i+" ");
	    
	}

입력과 동시에 오름차순 정렬이 되어있다.

 

조회 / 삭제

	public static void main(String[] args) {
		TreeSet<Integer> tset = new TreeSet<Integer>(Arrays.asList(5,1,6,8,12,86,44));
		for(int i : tset)
			System.out.print(i+" ");
		System.out.println();
		
		for(int i : tset.descendingSet())
			System.out.print(i+" ");
		System.out.println();
	
		
		// 조회
		System.out.println(tset.contains(1));
		System.out.println(tset.contains(2));
		
		// 삭제
		System.out.println(tset.remove(1));
		System.out.println(tset.remove(2));
		
	}

없는건 삭제시 false를 반환한다. Set뿐아니라 대다수의 자료구조가 똑같음

 

그 외 기타 메소드

	public static void main(String[] args) {
		TreeSet<Integer> tset = new TreeSet<Integer>(Arrays.asList(5,1,6,8,12,86,44));
		for(int i : tset)
			System.out.print(i+" ");
		System.out.println();

		System.out.println(tset.pollFirst()); // 최소값 poll(삭제)
		System.out.println(tset.pollLast());  // 최댓값 poll(삭제)
		System.out.println(tset.first());	//최소값 조회
		System.out.println(tset.last());	//최댓값 조회
		System.out.println(tset.lower(5));	// 5보다 작은값	
		System.out.println(tset.higher(5));	// 5보다 큰값
		System.out.println(tset.ceiling(5));// 5를 포함한 큰값
		System.out.println(tset.floor(5));	// 5를 포함한 작은값
	}

 

 

3. 시간복잡도

HashSet 시간복잡도

add         :   O(1)
contains    :   O(1)
next        :   o(h/n) h는 테이블 용량
java 1.2 thread-safe 보장 안함

특징 : 객체들을 순서없이 저장하고 동일한 객체를 중복 저장하지 않는다.
    - 중복되지 않는 값을 등록할때 용의
    - 순서없이 저장되는것 주위
    - null을 허용한다.

LinkedHashSet 시간복잡도

add       : O(1)
contains  : O(1)
next      : O(1)
java 1.4 thread-safe 보장 안함

특징 : 속도는 hashSet에 비해 느리지만 좋은 성능을 보장한다.
    - 등록한 순으로 정렬을 한다.
    - null을 허용한다.

TreeSet 시간복잡도
add       : O(log n)
contains  : O(log n)
next      : O(long n)
java 1.2 에서 나옴 thread-safe 보장 안함
특징 : 객체기준으로 정렬을 한다. 느리다.
    - null을 허용하지 않는다.

 

 

 

 

 

 

시간복잡도의 개념과 모든 자료구조별 성능 정리글

https://bangu4.tistory.com/202

시간복잡도 - 총정리

 

 

 

챔쥬

1. 컬렉션 인터페이스의 주요메소드를 확인할수있음

http://tcpschool.com/java/java_collectionFramework_set

코딩교육 티씨피스쿨

 

2. 컬렉션프레임워크의 자료구조별 시간복잡도를 정리해둠

https://www.grepiu.com/post/9

GrepIU

 

3. 주요메소드는 여기가 잘 정리되어있음

https://codevang.tistory.com/137

java.util.TreeSet 주요 메소드 [1/1]

https://codevang.tistory.com/136