[자료구조] Set

정의

• 데이터를 비순차적으로 저장할 수 있는 순열 자료구조이다.

특징

• Array, List와 마찬가지로 수정이 가능하다.
• 중복을 허용하지 않는다.
• 빠른 탐색이 필요한 경우에 주로 쓰인다.
• 비순차적이기 때문에 삽입 순서대로 저장되지 않아서, 특정한 순서를 기대할 수 없다.
• 인덱스가 존재하지 않기 때문에 iterator를 사용한다.

시간 복잡도

• add: O(1)
• containment: O(1) (내부적으로 해시테이블을 사용하는 구조기 때문에 평균 O(1))
• remove: O(1)

종류 in JAVA

1. HashSet
   • 인스턴스의 해시 값을 기준으로 저장하기 때문에 순서를 보장하지 않는다.
   • NULL값을 허용한다.
   • TreeSet보다 삽입, 삭제가 빠르다.
2. LinkedHashSet
   • 입력된 순서를 보장한다.
3. TreeSet
   • 이진 탐색 트리(Red-Black Tree)를 기반으로 한다.
   • 데이터들이 오름차순으로 정렬된다.
   • 데이터의 삽입, 삭제에는 시간이 걸리지만, 검색과 정렬이 빠르다.

내부구조

1. 저장할 데이터의 hash값을 구한다.
2. hash값에 해당하는 공간에 값을 저장한다.

언제 사용해야 할까?

• 중복된 값을 골라내야 하는 경우
• 특정 값이 있는지 빠르게 확인하는 경우
• 순서가 중요하지 않은 경우