HashSet
- Set 인터페이스를 구현한 가장 대표적인 컬렉션으로, 해시 알고리즘을 사용하기 때문에 검색 속도가 매우 빠르다.
- 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장하며, 중복을 허용하지 않기 때문에 add()를 통해 중복된 요소를 추가할 경우 해당 요소를 추가하지 않고 false를 반환한다.
- 또한 저장 순서를 유지하지 않기 때문에, 저장 순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.
중복 확인
- HashSet의 add 메서드는 새로운 요소의 중복 여부를 판별하기 위해 다음과 같은 과정을 거친다.
- 해당 요소에서 hashCode() 메서드를 호출하여 반환된 해시값으로 검색할 범위를 결정한다.
- 해당 범위 내의 요소들을 equals() 메서드로 비교한다.
- 따라서 HashSet에서 중복없이 새로운 요소를 추가하기 위해서는 key로 사용하는 객체의 equals()와 hashCode()를 목적에 맞게 오버라이딩 해야 한다.
class Animal {
String species;
String habitat;
Animal(String species, String habitat) {
this.species = species;
this.habitat = habitat;
}
public int hashCode() {
return (species + habitat).hashCode();
}
public boolean equals(Object obj) {
if(obj instanceof Animal) {
Animal temp = (Animal)obj;
return species.equals(temp.species) && habitat.equals(temp.habitat);
} else {
return false;
}
}
}
haseCode() 조건
- 실행 중인 애플리케이션 내의 동일한 객체에 대해서 여러번 hashCode()를 호출해도 동일한 int 값을 반환해야 한다.
- equals()를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 haseCode()를 호출해서 얻은 결과는 반드시 같아야 한다.
- equals()를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int 값을 반환할 수 있지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int 값을 반환하는 것이 좋다.
해시 알고리즘
- 해시 알고리즘이란 해시 함수를 사용하여 데이터를 해시 테이블에 저장하고, 다시 그것을 검색하는 알고리즘을 말한다.
- 자바에서 해시 알고리즘을 구현하기 위해 배열과 연결 리스트를 사용한다.
- 저장할 데이터의 키 값을 해시 함수에 넣어 반환되는 값으로 배열의 인덱스를 구한다.
- 해당 인덱스에 저장된 연결 리스트에 데이터를 저장한다.
TreeSet
- 데이터가 정렬된 상태로 저장되는 이진 검색 트리(레드-블랙 트리)의 형태로 데이터를 저장하며, 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다.
- 중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장 순서를 유지하지 않는다.
- TreeSet에 저장되는 객체는 Comparable을 구현한 것이던가 아니면, Comparator를 제공해서 두 객체를 비교할 방법을 알려주어야 한다.
이진 검색 트리
- 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조로, TreeSet은 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리로 구현되어 있다.
- 부모 노드의 왼쪽에는 부모 노드의 값보다 작은 값의 자식 노드를, 오른쪽에는 큰 값의 자식 노드를 저장한다.
- 데이터를 삭제하는 경우 트리의 일부를 재구성하므로 연결 리스트보다 추가와 삭제에 시간이 오래 걸리지만, 배열이나 연결 리스트에 비해 검색과 정렬 기능이 뛰어나다.
범위 검색
- TreeSet의 인스턴스에 저장되는 요소들은 모두 정렬된 상태로 저장되므로, 해당 트리의 부분 집합을 구하는 등의 범위와 관련된 연산이 가능하다.
SortedSet subSet(Object from, Object to) | from과 to 사이의 범위 검색 결과를 반환 |
SortedSet headSet(Object from) | 지정된 객체보다 작은 값의 객체들을 반환 |
SortedSet tailSet(Object from) | 지정된 객체보다 큰 값의 객체들을 반환 |
'Java > Java' 카테고리의 다른 글
Arrays, Collections (0) | 2022.03.28 |
---|---|
Comparable과 Comparator (0) | 2022.03.28 |
Iterator (0) | 2022.03.28 |
Map 컬렉션 클래스 (0) | 2022.03.28 |
컬렉션 프레임워크와 List 컬렉션 클래스 (0) | 2022.03.28 |