Set Collection
- 요소의 저장 순서 유지 ❌
- 같은 요소의 중복 저장 허용 ❌
HashSet<E>
HashSet 클래스는 Set 컬렉션 클래스에서 가장 많이 사용되는 클래스다.
JDK 1.2부터 제공된 HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다.
HashSet 클래스는 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다.
HashSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다. 만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 된다.
HashSet<String> hs01 = new HashSet<String>();
HashSet<String> hs02 = new HashSet<String>();
hs01.add("홍길동");
hs01.add("이순신");
System.out.println(hs01.add("임꺽정"));
System.out.println(hs01.add("임꺽정")); // 중복 요소 저장
for (String e : hs01) System.out.print(e + " ");
hs02.add("임꺽정");
hs02.add("홍길동");
hs02.add("이순신");
System.out.println("집합의 크기 : " + hs02.size());
// 실행 결과
// true
// false
// 홍길동 이순신 임꺽정
// 집합의 크기 : 3예제에서 요소의 저장 순서를 바꿔도 저장되는 순서에는 영향을 미치지 않는 것을 확인할 수 있다.
또한, add() 메서드를 사용하여 해당 HashSet에 이미 존재하는 요소를 추가하려고 하면, 해당 요소를 저장하지 않고 false를 반환하는 것을 볼 수 있다.
해당 HashSet에 이미 존재하는 요소인지를 파악하기 위해서는 내부적으로 아래와 같은 과정을 거치게 된다.
- 해당 요소에서 hashCode() 메서드를 호출하여 반환된 해시값으로 검색할 범위를 결정한다.
- 해당 범위 내의 요소들을 equals() 메서드로 비교한다.
Hash Algorithm
해시 알고리즘(hash algorithm)이란 해시 함수(hash function)를 사용하여 데이터를 해시 테이블(hash table)에 저장하고, 다시 그것을 검색하는 알고리즘
자바에서 해시 알고리즘을 이용한 자료 구조는 위의 이미지와 같이 배열과 연결 리스트로 구현된다.
저장할 데이터의 키값을 해시 함수에 넣어 반환되는 값으로 배열의 인덱스를 구하고,
해당 인덱스에 저장된 연결 리스트에 데이터를 저장한다.
예를 들어, 정수형 데이터를 길이가 10인 배열에 저장한다고 한다면 1,002를 검색하는 방법은 다음과 같다.
1,002를 10으로 나눈 나머지가 2이므로 배열의 세 번째 요소에 연결된 연결 리스트에서 검색을 시작한다.
간단한 예제이지만 이렇게 해시 알고리즘을 이용하면 매우 빠르게 검색 작업을 수행할 수 있다.
TreeSet<E>
TreeSet 클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장한다. 이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다.
JDK 1.2부터 제공되는 TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현한다.
TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.
TreeSet<Integer> ts = new TreeSet<Integer>();
ts.add(30);
ts.add(40);
ts.add(20);
ts.add(10);
for (int e : ts) System.out.print(e + " ");
ts.remove(40);
System.out.println("이진 검색 트리의 크기 : " + ts.size());
// 실행 결과
// 10 20 30 40
// 이진 검색 트리의 크기 : 3TreeSet 인스턴스에 저장되는 요소들은 모두 정렬된 상태로 저장된다.
Set Interface Method
Set Interface는 Collection Interface를 상속받으므로,
Collection Interface에서 정의한 Method도 모두 사용할 수 있다.
| 메서드 | 설명 |
|---|---|
| boolean add(E e) | 해당 집합(set)에 전달된 요소를 추가 |
| void clear() | 해당 집합의 모든 요소를 제거 |
| boolean contains(Object o) | 해당 집합이 전달된 객체를 포함하고 있는지를 확인 |
| boolean equals(Object o) | 해당 집합과 전달된 객체가 같은지를 확인 |
| boolean isEmpty() | 해당 집합이 비어있는지를 확인 |
| Iterator<E> iterator() | 해당 집합의 반복자(iterator)를 반환 |
| boolean remove(Object o) | 해당 집합에서 전달된 객체를 제거 |
| int size() | 해당 집합의 요소의 총개수를 반환 |
| Object[] toArray() | 해당 집합의 모든 요소를 Object 타입의 배열로 반환 |
