Set이란?

• array나 list 처럼 연결 자료구조(collection) 이지만 set은 순서라는 개념이 존재하지 않음

• Set은 집합이라는 의미를 가짐

특징

• 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조 (collection)

• 집합의 개념과 같다고 생각

  • 집합 역시 {1, 9, 6, 4}처럼 중복과 순서가 없기 때문에

• 삽입(insertion) 순서대로 저장되지 않음

  • 즉, 특정한 순서를 기대할 수 없는 자료구조

• 수정 가능(mutable)

• 동일한 값을 여러번 삽입 불가능

  • 동일한 값이 여러번 삽입 되면 하나의 값만 저장됨

• Fast Lookup이 필요할때 주로 사용

• Set이라는 인터페이스를 통해 자바에서는 3가지의 Set이 존재

  • 일반적으로 HashSet, TreeSet, LinkedHashSet 순으로 빠름

    • Hash 알고리즘을 이용한 HashSet

    • 이진 탐색 트리를 사용하여 오름차순 정렬까지 해주는 TreeSet

    • Set에 순서를 부여해주는 LinkedHashSet

구조

• Array와 달리 set은 요소들을 순차적으로 저장하지 않음

• Set에서 요소들이 저장될 때 순서는 아래와 같음

  • 저장할 요소의 값의 hash 값을 구하고
  • 해쉬값에 해당하는 공간(bucket)에 값을 저장합니다.

• 이렇게 set는 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. 순서가 없기 때문에 indexing도 없습니다.

• 그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없는것입니다.

• 해쉬값을 기반으로 저장하기 때문에 look up 이 굉장히 빠릅니다.

  • Look up: 특정 값을 포함하고 있는지를 확인 하는것
  • O(1): Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 됨

사용처

• 순서 보장이 필요없고 중복은 없어야할 때

  ex) 이벤트 응모자 목록
  

• 해쉬값이 기반이기 때문에 조회속도가 빠른 장점을 사용해 실시간 처리에도 사용 가능

• 집합 관련 문제

• 빠른 look up 을 해야 할때

---

HashSet

• 내부적으로 HashMap을 사용하여 값을 저장

• 값의 중복 허용 X

• 값이 저장된 순서 보장 X

• null 허용