Set 인터페이스

✒️ 2025-05-27 16:51 내용 수정

순서가 없는 데이터 집합이고, 중복을 허용하지 않는다.

내부 구조가 비선형 방식이고, index가 존재하지 않는다.
- Set 내부의 요소를 하나씩 빼려면 Iterator 인터페이스 등을 사용해야 한다.
처음 들어온 값 이후의 중복된 데이터는 아예 무시해버린다.
- 중복을 제거할 때 사용한다.

인터페이스 메서드

Set 인터페이스 메서드	설명
`void add(E, e)`	해당 집합에 데이터를 순서대로 추가함
`boolean equals(Object o)`	해당 집합과 전달된 객체가 같은지 확인
`boolean isEmpty()`	해당 집합이 비어있는지 확인
`void remove(Object o)`	해당 집합에서 전달된 객체 제거
`void clear()`	해당 집합의 모든 데이터 제거
`int size()`	해당 집합에 저장된 데이터의 개수를 반환
`boolean contains(Object o)`	해당 집합에서 전달된 데이터 존재 여부 확인
`Object[] toArray()`	해당 집합의 모든 요소를 Object 타입의 배열로 반환
`Iterator<E> iterator()`	해당 집합의 반복자(iterator)를 반환
`void addAll(Collection<? extends E> c)`	해당 집합에 컬렉션의 모든 요소를 추가
`void removeAll(Collection<?> c)`	주어진 컬렉션의 요소를 집합에서 모두 제거
`void containsAll(Collections<?> c)`	주어진 컬렉션의 모든 요소가 집합에 있는지 확인
`void retainAll(Collection<?> c)`	주어진 컬렉션과 겹치는 요소만 유지

Set 컬렉션 클래스로는 HashSet<E>, TreeSet<E>, LinkedHashSet<E> 등이 있다.
TreeSet<E>, LinkedHashSet<E>, SortedSet<E>는 데이터를 가지는 알고리즘과 구조 때문에 순서 및 정렬이 가능하다.
TreeSet<E>은 데이터가 정렬된 상태로 저장되고, 이진 검색 트리의 형태로 요소를 저장한다.

데이터를 저장할 때 순서를 부여하지 않고, 동일한 객체를 허용하지 않는다.
- 동일한 객체 : 데이터의 객체를 hashCode() 호출로 비교 결과가 같은지 판단,
  같으면 equals()를 호출해서 객체의 요소(값)이 같은지 비교

Set<T> 인스턴스이름 = new HashSet<T>();

내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다. (Map 인터페이스)
HashSet<E>은 해시 알고리즘을 사용하기 때문에 검색이 매우 빠르다.
- Hash algorithm : 해시 함수(Hash function) 을 사용하여 데이터를 해시 테이블(Hash table)에 저장하고, 다시 그것을 검색하는 알고리즘.

- Hash Algorithm

1. 저장할 데이터의 키 값을 해시 함수에 넣는다
2. 반환된 값으로 해시 테이블의 인덱스를 구한다
3. 해당 인덱스에 저장된 연결 리스트에 데이터를 저장한다.

Set 인터페이스를 구현한 클래스이므로 중복을 허용하지 않지만 정렬이 가능하다.
- 삽입 순서를 유지하지 않고 Tree를 통한 자동 정렬 후의 순서를 유지한다.
이진 탐색 트리 중에서도 성능을 향상시킨 레드-블랙트리로 구현되어 있다.

TreeSet<T> 인스턴스이름 = new TreeSet<T>();

레드-블랙트리는 부모보다 작은 값을 가지는 객체는 왼쪽 자식으로, 큰 값을 가지는 객체는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어준다.
- 초기 추가 된 값을 기준으로 두 번째 추가된 값은 부모보다 작으면 왼쪽 자식, 크면 오른쪽 자식이 배치된다.
- 다음 들어온 값이 첫 부모 기준으로 작으면 왼쪽, 크면 오른쪽으로 비교되고, 두 번째 부모와 비교해서 작으면 왼쪽, 크면 오른쪽으로 배치되는 것을 반복한다.
TreeSet의 메서드들 : https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html

TreeSet 인터페이스 메서드	설명
`int first()`	TreeSet에 있는 최소값 반환
`int last()`	TreeSet에 있는 최대값 반환
`int higher(int i)`	전달 받은 객체보다 큰 데이터 중 최소값 반환, 없으면 `null`
`int lower(int i)`	전달 받은 객체보다 작은 데이터 중 최대값 반환, 없으면 `null`
`E ceiling(E e)`	전달 받은 객체보다 크거나 같은 데이터 중 최소값 반환, 없으면 `null`
`Iterator<E> descendingIterator()`	오른쪽에서 왼쪽으로 순회(역순)하는 Iterator를 반환
`NavigableSet<E> descendingSet()`	해당 set의 요소를 역순으로 정렬