[Java] HashSet
개요
HashSet은 자바의 컬렉션 프레임워크 중 하나로, 중복되지 않는 요소들을 저장하는 데 사용됩니다. 내부적으로 해시 테이블(Hash Table)을 사용하여 요소들을 저장하며, 그로 인해 매우 빠른 검색, 삽입, 삭제 성능을 제공합니다.
주요 특징
중복 허용 안함
HashSet은 중복된 요소를 저장하지 않습니다. 동일한 객체를 추가하려고 하면 기존의 객체가 유지되고 새로운 객체는 무시됩니다.
순서 보장 안함
HashSet에 저장된 요소들은 저장된 순서가 보장되지 않습니다. 이는 HashSet의 내부 구현 방식인 해시 테이블의 특성 때문입니다.
null 값 허용
HashSet은 하나의 null 값을 허용합니다. 이는 HashSet이 비어있는 경우와 구분할 수 있도록 합니다.
빠른 성능
일반적으로 삽입, 삭제, 검색 연산이 평균적으로 O(1) 시간 복잡도를 가지므로 매우 효율적입니다.
생성자
HashSet 클래스는 다양한 생성자를 제공합니다.
HashSet()
기본 초기 용량(16)과 기본 부하 인수(0.75)를 사용하여 빈 해시 집합을 생성합니다.
HashSet(Collection<? extends E> c)
지정된 컬렉션의 요소를 포함하는 새로운 해시 집합을 생성합니다.
HashSet(int initialCapacity)
지정된 초기 용량과 기본 부하 인수를 사용하여 빈 해시 집합을 생성합니다.
HashSet(int initialCapacity, float loadFactor)
지정된 초기 용량과 지정된 부하 인수를 사용하여 빈 해시 집합을 생성합니다.
주요 메소드
add(E e)
지정된 요소를 추가합니다. 요소가 이미 존재하는 경우 추가되지 않습니다.
remove(Object o)
지정된 요소를 제거합니다. 요소가 존재하지 않는 경우 아무 일도 일어나지 않습니다.
contains(Object o)
지정된 요소가 존재하는지 여부를 반환합니다.
size()
HashSet의 요소 개수를 반환합니다.
clear()
HashSet의 모든 요소를 제거합니다.
isEmpty()
HashSet이 비어있는지 여부를 반환합니다.
사용 예시
다음은 HashSet의 사용 예시입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.HashSet;
public class HashSetExample {
public static void main(String[] args) {
// HashSet 생성
HashSet<String> set = new HashSet<>();
// 요소 추가
set.add("Apple");
set.add("Banana");
set.add("Orange");
set.add("Apple"); // 중복 요소, 추가되지 않음
// 요소 출력
System.out.println("HashSet 요소: " + set);
// 요소 포함 여부 확인
if(set.contains("Banana")) {
System.out.println("Banana가 HashSet에 포함되어 있습니다.");
}
// 요소 제거
set.remove("Banana");
System.out.println("Banana 제거 후 HashSet 요소: " + set);
// HashSet의 크기
System.out.println("HashSet 크기: " + set.size());
}
}
내부 동작 원리
HashSet은 내부적으로 HashMap을 사용하여 요소를 저장합니다. HashSet에 요소를 추가할 때, 해당 요소는 HashMap의 키로 저장되며, 값은 HashSet 내부적으로 사용되는 상수 객체로 저장됩니다. 이는 다음과 같은 방식으로 이루어집니다.
1
2
3
4
5
6
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
HashMap은 해시 테이블을 사용하여 요소를 저장하므로, 각 요소는 해시 함수를 통해 해시 코드(hash code)를 계산하여 해당 해시 코드에 매핑된 버킷(bucket)에 저장됩니다. 이로 인해 HashSet은 매우 빠른 조회 및 삭제가 가능합니다.
HashSet과 다른 Set 구현체 비교
자바에는 HashSet 외에도 여러 가지 Set 인터페이스의 구현체가 있습니다. 그 중 가장 일반적인 세 가지는 HashSet, LinkedHashSet, TreeSet입니다. 이들은 각기 다른 용도와 특성을 가지고 있습니다.
HashSet
가장 빠른 접근 시간과 불규칙한 순서를 제공합니다. 요소가 순서에 상관없고, 빠른 삽입과 삭제가 필요한 경우 적합합니다.
LinkedHashSet
요소가 삽입된 순서를 유지합니다. 요소가 삽입된 순서대로 접근해야 하는 경우 적합합니다.
TreeSet
요소가 정렬된 순서를 유지합니다. 요소가 자연 순서나 사용자 정의 순서로 정렬되어야 하는 경우 적합합니다. 내부적으로는 NavigableMap 인터페이스를 구현하는 TreeMap을 사용합니다.
다음 예제는 HashSet, LinkedHashSet, TreeSet의 동작 차이를 보여줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class SetComparison {
public static void main(String[] args) {
Set<String> hashSet = new HashSet<>();
Set<String> linkedHashSet = new LinkedHashSet<>();
Set<String> treeSet = new TreeSet<>();
String[] elements = {"Banana", "Apple", "Orange", "Mango"};
for (String element : elements) {
hashSet.add(element);
linkedHashSet.add(element);
treeSet.add(element);
}
System.out.println("HashSet: " + hashSet);
System.out.println("LinkedHashSet: " + linkedHashSet);
System.out.println("TreeSet: " + treeSet);
}
}
/** 결과
HashSet: [Banana, Orange, Apple, Mango]
LinkedHashSet: [Banana, Apple, Orange, Mango]
TreeSet: [Apple, Banana, Mango, Orange]
*/
HashSet은 요소의 순서를 보장하지 않지만, LinkedHashSet은 삽입된 순서를 유지하고, TreeSet은 요소를 정렬된 순서로 저장합니다.
이러한 HashSet은 중복을 허용하지 않으며 빠른 검색, 삽입, 삭제가 필요한 경우에 매우 유용한 자료 구조입니다. 순서를 보장할 필요가 없고, 효율적인 집합 연산이 필요한 경우 HashSet을 사용하는 것이 좋습니다. 또한, 자바의 다른 Set 구현체와 비교하여 용도와 필요에 맞게 선택할 수 있습니다.
읽어주셔서 감사합니다. 😊
Reference
ChatGPT - OpenAI