Set

List vs Set

각각 특정한 방식으로 데이터를 저장하고 관리한다

List

요소들의 순차적인 컬렉션으로 요소들은 특정 순서를 갖고, 중복을 허용한다
인덱스로 요소에 접근할 수 있다

Set

유일한 요소들의 컬렉션으로 요소들은 특정 순서를 갖지 않고, 중복을 허용하지 않는다
셋은 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어 있다 (빠른 조회 가능)

구현

기본적인 형태는 배열을 필드로 갖고
중복 체크를 하는 contains() 와
contains() 를 사용하여 중복 체크 후 값을 추가하는 add() 로 구성

데이터 추가 메서드 add() 는 O(1) 이지만
데이터 추가 시마다 전체 데이터를 대상으로 중복 체크를 해야 하기 때문에
contains() 를 항상 실행해야 하기 때문에
입력 성능이 O(n)으로 좋지 않다

해시 알고리즘