[자료구조] Set 살펴보기

Set이란?

 

Set은 집합이라는 의미를 가진다.

Set은 JFC에 있는 자료구조로 순서가 없고 중복을 허용하지 않는다.

 

즉, 집합의 개념과 같다고 생각하면 된다.(집합 역시 {1, 9, 6, 4}처럼 중복과 순서가 없다.)

Set이라는 인터페이스를 통해 자바에서는 3가지의 Set이 있다.

 

1. Hash 알고리즘을 이용한 HashSet
2. 이진 탐색 트리를 사용하여 오름차순 정렬까지 해주는 TreeSet
3. Set에 순서를 부여해주는 LinkedHashSet

 

일반적으로 HashSet, TreeSet, LinkedHashSet 순으로 빠르다.

 

왜 Set을 사용해야하나?

 

Set의 가장 큰 특징은 바로 순서가 없고 중복을 허용하지 않는다는 것이다.

따라서 비록 위 특징을 List나 다른 자료구조를 통해 커버할 수 있지만 명백한 "속도" 차이가 나기 때문에 Set을 사용하는 것이 좋다.

Set을 사용해야 되는 경우는 다음과 같다.

 

1. 집합 관련 문제
2. 중복 처리를 고려해야할 때
3. 2번 사항 + 빠르게 찾아야할 때

 

Set의 동작원리

 

HashSet의 경우 Hash 알고리즘 기반으로 동작한다.

1. 입력된 키를 해시 코드로 변환한다.
2. 해시 코드를 인덱스로 한 bucket이라는 array에 해당 인덱스를 찾아 저장한다.(여기서 배열 길이가 초과하는 경우에는 길이의 나머지를 구해 링크드 리스트로 추가한다.)

TreeSet의 경우 이진트리의 향상된 버전인 Red-Black Tree를 기반으로 만들어진다.

 

1. 새로운 데이터가 들어오면 루트부터 비교한다.
2. 비교의 결과에 따라 우측, 좌측으로 갈지 결정된다.
3. 더 이상 비교를 할 수 없을 때까지 2번을 반복한다.

추가/삭제는 링크드 리스트 보다 비효율적이지만 검색/정렬은 TreeSet이 더 좋다.

 

동작원리 설명

Set의 주요 기능

Set의 기본 기능은 다음과 같다.

 

 

 

추가적인 기능을 넣으면 다음과 같다.

메서드	기능
boolean addAll(Collection c)	주어진 컬렉션에 저장된 모든 객체를 추가한다.(합집합)
boolean containsAll(Collection c)	주어진 컬렉션에 저장된 모든 객체를 포함하고 있는지 검사한다.(부분집합 검사)
boolean removeAll(Collection c)	주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 모두 삭제한다.(차집합)
boolean retainAll(Collection c)	주어진 컬렉션에 저장된 모든 객체와 동일한 것만 남기고 삭제한다.(교집합)