Set 컬렉션 - HashSet, TreeSet, LinkedHashSet

gillog·2020년 10월 16일
0

자료구조

목록 보기
5/6

Set 컬렉션

Set 컬렉션은 저장 순서가 유지되지 않는다.
객체를 중복 저장할 수 없고, 하나의 null만 저장 할 수 있다.
Set 컬렉션은 수학의 집합에 비유 될 수 있는데, 순서와 상관없이 중복이 허용되지 않기 때문이다.

Set 인터페이스를 구현한 클래스로는 HashSetTreeSet, LinkedHashSet이 있는데 HashSet의 경우 정렬을 해주지 않고 TreeSet의 경우 오름차순으로 자동정렬을 해준다는 차이점이 있다. LinkedHashSet은 입력된 순서대로 데이터를 관리한다.

이를 정리하면 아래와 같다.

|클래스 명|특징|
|:---:|:---:|
|HashSet|Hashing을 이용해서 구현한 컬렉션이다.
데이터를 중복 저장할 수 없고, 순서를 보장하지 않는다.
equals()나 hashCode()를 오버라이딩해서,
인스턴스가 달라도 동일 객체를 구분해 중복 저장을 막을 수 있다.|
|TreeSet|이진탐색트리(Red-Black Tree)의 형태로 데이터를 저장한다.
데이터 추가, 삭제에는 시간이 더 걸리지만, 검색과 정렬이 더 뛰어나다.
기본적으로 오름차순으로 데이터를 정렬한다.|
|LinkedHashSet|HashSet 클래스를 상속받은 LinkedList이다.
데이터에 삽입된 순서대로 데이터를 관리한다.|

HashSet, TreeSet, LinkedHashSet의 시간 복잡도

|HashSet|TreeSet|LinkedHashSet|
|:---:|:---:|:---:|
|O(1)|O(log n)|O(1)|

HashSet이 TreeSet이나 LinkedHashSet보다 성능이 더 빠르고, 메모리를 적게 사용한다.


Set의 가장 큰 장점은 중복을 자동으로 제거해준다는 점이다.

Set 인터페이스의 공통적으로 사용가능한 메소드들은 아래와 같다.

|기능|메소드|설명|
|:--:|:--:|:--:|
|추가|boolean add(E e)|주어진 객체를 저장, 객체가 성공적으로 저장되면 true를 return, 중복 객체면 false를 return
|검색|boolean contains(Object o)|주어진 객체가 저장되어 있는지 여부|
|검색|boolean isEmpty()|컬렉션이 비어있는지 조사|
|검색|Iterator iterator()|저장된 객체를 한 번씩 가져오는 반복자 리턴|
|검색|int size()|저장되어 있는 전체 객체 수 리턴|
|삭제|void clear()|저장된 모든 객체를 삭제|
|삭제|boolean remove(Object o)|주어진 객체를 삭제|

Set 컬렉션은 인덱스를 통해 객체를 검색해서 가져오는 메소드가 없기 때문에, 전체 객체를 대상으로 한번씩 반복하여 가져오는 Iterator(반복자)를 제공한다.
반복자는 Iterator 인터페이스를 구현한 객체를 말하는데, iterator()를 호출하면 얻을 수 있다.

// iterator 생성 예제
Set<String> set = new HashSet<String>();
Iterator<String> iterator = set.iterator();

Iterator 인터페이스에 선언된 메소드들은 아래와 같다.

|타입|메소드|설명|
|:--:|:--:|:--:|
|boolean|hasNext()|가져올 객체가 있다면 true를 return, 없다면 false를 return 한다|
|E|next()|하나의 객체를 가져온다|
|void|remove()|객체를 제거한다|

Iterator에서 하나의 객체를 가져올 때는 아래와 같이 hasNext()를 통해서 가져올 객체가 있는지 확인한 후 next()메소드를 사용한다.

만약 객체를 삭제하고 싶다면 remove() 메소드를 실행하면 되는데 Iterator의 메소드지만 실제 Set컬렉션에서 삭제 된다.

Set <String> set = new HashSet<String>();
Iterator<String> iterator = set.iterator();
while(iterator.hasNext()){
    String str = iterator.next();
    if(str.equals("AA"){
        //실제 set에서 "AA"객체가 삭제된다.
        iterator.remove();
    }
}

HashSet의 hashCode()와 equals()

HashSet은 같은 인스턴스가 아니더라도 동일 객체를 구분하여 중복 저장을 막을 수 있다.
HashSet에 객체를 저장하기 전에, hashCode()를 호출해 해시코드를 얻어내는데, 이미 저장되어 있는 객체들의 해시코드와 비교해서, 만약 동일한 해시코드가 있다면 다시 equals()로 두 객체를 비교해 true가 나오면 동일한 객체로 판단해 중복 저장을 하지 않는 방식이다.

사용 예제

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

Set<String> hashSet = new HashSet<String>();
Set<String> treeSet = new TreeSet<String>();
Set<String> linkedHashSet = new LinkedHashSet<String>();
  	
hashSet.add("a");
hashSet.add("b");
hashSet.add("c");
  	
Iterator<String> hashIter = hashSet.iterator();
  	
while(hashIter.hasNext()){
  System.out.println(hashIter.next());
}
  	
System.out.println();
  	
// treeSet은 오름차순 정렬 이므로 출력 결과 a, b, c
treeSet.add("a");
treeSet.add("c");
treeSet.add("b");
  	
Iterator<String> treeIter = treeSet.iterator();
  	
while(treeIter.hasNext()) {
  System.out.println(treeIter.next());
}
  	
System.out.println();

// set에선 동일 객체 저장 불가
linkedHashSet.add("a");
linkedHashSet.add("a");
linkedHashSet.add("c");
linkedHashSet.add("b");
  	
Iterator<String> linkedIter = linkedHashSet.iterator();
  	
while(linkedIter.hasNext()) {
  System.out.println(linkedIter.next());
}

🙆‍♂️ 참고사이트 🙇‍♂️

[JAVA/자바] Set - HashSet, TreeSet, LinkedHashSet[Joker님]

JAVA의 HashSet, TreeSet[Swalloow님]

profile
🕔 Start Today. 🕚

0개의 댓글