Set
Set은 ADT로 다음과 같은 특징을 갖는다.
- 중복을 허용하지 않는다.
- 저장 순서를 유지하지 않는다.
HashSet
자바에서는 Set 자료구조의 구현체로 HashSet을 제공한다. HashSet은 다음과 같이 Set 인터페이스를 구현하고 내부적으로 HashMap을 사용한다.
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
}HashSet이 중복된 데이터를 허용하지 않는 방법(equals(), hashCode())
그러면 HashSet는 어떻게 중복된 데이터를 허용하지 않을까? HashSet뿐만 아니라 해시 값을 사용하는 컬렉션 프레임워크(HashMap, HashSet, ConcurrentHashMap 등)는 새로운 데이터를 추가하기 전에 중복된 데이터가 이미 저장되어 있는지 확인하는 과정을 거친다.
- 다음 사진처럼 우선 hashCode() 메소드의 값을 비교하고
- equals() 메소드의 값을 비교한다.
- 두 비교 결과 모두 같을 때 동등 객체라고 판단한다.
- hashCode(): 객체의 주소 값을 해시 값으로 반환한다. 즉, 주소 값이 같으면 같은 객체라고 판단한다.
- equals(): == 과 마찬가지로 객체의 주소 값을 비교한다. 즉, 주소 값이 같으면 같은 객체라고 판단한다. 그러나 그 내용 값을 기준으로 비교하도록 몇가지 클래스는 equals() 메소드를 재정의해놨다. (ex, String 클래스 )
예를 들어 name이라는 변수를 가진 Car 클래스가 있고, 두개의 Car 클래스의 name 값이 같다고 가정하자.
- Car car1 = new Car("kim")
- Car car2 = new Car("kim"))
이때 name을 기준으로 비교한다고 equals() 메소드를 재정의했더라도, 두 객체의 hashCode() 값이 다르므로(주소 값이 다르므로), 두 객체는 다르다고 판단되어 set에 두 객체가 중복 저장된다. 따라서 해시 값을 사용하는 컬렉션 프레임워크에 데이터를 저장하기 위해선 저장하려는 데이터 타입에 대한 equals()와 hashCode()를 반드시 재정의해야 한다.
그리고 이때 재정의된 hashCode()는 다음 세 가지 조건을 만족시켜야 한다.
- 실행 중인 애플리케이션 내의 동일한 객체에 대해서 여러 번 hashCode()를 호출해도 동일한 int 값을 반환해야 한다.
- equals() 메소드를 이용한 비교에 의해 true를 얻은 두 객체에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야 한다.
- equals() 메소드를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int 값을 반환하는 경우가 있어도 괜찮지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int 값을 반환하는 것이 좋다. 즉 equals() 메소드를 호출한 결과가 true인 두 객체에 대해서 두 객체의 해시 값은 반드시 같아야 하지만 두 객체의 해시 값이 같다고 해서 반드시 equals() 호출 결과가 true이어야 하는 것은 아니다.
결론적으로 해시 값을 사용하는 컬렉션 프레임워크는 equals()메소드와 hashCode() 메소드를 통해 중복된 데이터가 이미 존재하는지 확인한 후에 데이터를 추가한다. 그리고 HashSet은 다음과 같이 내부적으로 HashMap을 사용하여 저장하고자 하는 데이터를 key로, 더미 데이터를 의미하는 Object 객체를 value로 저장한다.
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}LinkedHashSet
HashSet은 저장 순서를 유지하지 않는다. 따라서 저장 순서를 유지하고자 한다면 LinkedHashSet을 사용하면 된다.
LinkedHashSet에 대한 특징은 다음과 같다.
- LinkedHashSet은 HashSet을 상속받는다.
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
@java.io.Serial
private static final long serialVersionUID = -2851667679971038690L;
public LinkedHashSet() {
super(16, .75f, true);
}
}- 그리고 부모 클래스의 생성자를 따라가보면 LinkedHashMap을 사용한다는 것을 알 수 있다.
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}- 즉, HashSet과 LinkedHashSet 모두 결국 내부적으로는 HashMap을 사용하기 때문에 데이터 조회/삽입/삭제에 대한 시간 복잡도는 O(1)이다.
- HashSet은 HashMap을 사용하기 때문에 초기용량과 로드팩터에 의해 성능이 좌우된다. 그러나 LinkedHashSet은 LinkedHashMap을 사용하기 때문에 초기용량에 대한 설정이 HashSet보다 덜 중요하다.
- LinkedHashSet은 HashSet과 마찬가지로 Thread-safe 하지 않다. 따라서 멀티스레드 환경에서 사용하려면 다음과 같이 사용하면 된다.
Set set = Collections.synchronizedSet(new LinkedHashSet(...));Reference
'CS > Data Structure' 카테고리의 다른 글
| 해시 분포와 해시 충돌, HashMap, LinkedHashMap (1) | 2023.12.06 |
|---|---|
| 우선순위 큐(Priority Queue), 힙(Heap) (1) | 2023.12.06 |
| 스택(Stack), 큐(Queue) (0) | 2023.12.06 |
| ArrayList, LinkedList (0) | 2023.12.05 |