[Java] HashMap, HashSet 이란? - (4) HashSet이란?

이번 글에서는 1편, 2편, 3편에 이어 HashSet에 대해 작성한다.

 

아래 글을 읽기 전에 위 세 글을 순서대로 읽고 오는 것을 추천한다.

 

---

 

HashSet 이란?

개념

HashMap의 개념과 마찬가지로,

내부적으로 Hash(해시)를 사용하는 Set 인터페이스의 구현체이다.

 

Set(집합) 이라는 단어를 포함한 만큼 집합적인 개념의 데이터 구조이다.

 

구현

아래처럼 HashSet이 구현되어 있는 Java 코드를 보면 놀랍게도 HashMap을 사용한다.

 

// predefined HashSet class
public class HashSet
{
    // A HashMap object 
    private transient HashMap map;

    // A Dummy value(PRESENT) to associate with an Object in the Map
    private static final Object PRESENT = new Object();
    
    // default constructor of HashSet class
    // It creates a HashMap by calling 
    // default constructor of HashMap class
    public HashSet() {
        map = new HashMap<>();
    }

    // add method 
    // it calls put() method on map object
    // and then compares it's return value with null
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
 
    // Other methods in Hash Set
}

 

그래서 HashSet 자료구조는 HashMap을 사용하여 데이터의 중복을 없앰을 알 수 있다.

 

특징

HashMap처럼 순서에 의미를 두지 않으며, 데이터의 중복이 없다.

(내부적으로 HashMap을 사용하여 구현되어 있기 때문에, 어찌보면 당연한 이야기..)

 

또한 오직 객체(Object)만 저장 가능하며, 그래서 HashMap보다 느리다.

 

왜냐하면 HashMap은 삽입되는 데이터의 형태가 각 Value들이 Unique한 Key에 mapping 되어 있지만,

HashSet은 삽입되는 object를 Key 값으로, 내부 구현 코드에서 필드로 선언한 객체를 Value 값으로 사용하기 때문에

해당 필드 객체의 해시 값 계산도 해야하기 때문이다.

(참고 사이트)

 

데이터를 저장할 때는 add() 메서드를 사용하는데,

이때, equals() 메서드와 hashCode() 메서드가 사용되어 중복된 객체가 있는지 확인한다.

 

equals() & hashCode() - HashSet

equals()와 hashCode()에 대해서는 추후 자세히 글을 작성할 예정이므로 여기서는 간단하게만 알아본다.

 

먼저, 이전에 작성한 글들을 읽고 왔으면 hashCode() 메서드는 익숙할 것이라 생각한다.

 

hashCode() 메서드는 해시 함수를 갖고 있는 함수로,

임의의 길이의 임의의 데이터를 넣었을 때 고정된 길이의 데이터를 return 한다.

 

그래서 HashSet에서 삽입되는 객체는 hashCode() 를 통해 해시 값을 생성하고,

equals() 메서드를 통해 기존에 저장되어 있던 데이터들의 해시 값과 새로 삽입되는 객체의 해시 값을 비교하여

중복된 객체가 있는지 체크한다.

 

(다들 알겠지만, equals() 메서드는 두 객체가 같은 '값'을 갖고 있는지 판단한다)

 

equals() & hashCode() - HashSet

사실 HashMap도 equals()와 hashCode() 메서드를 사용한다.

 

그럼에도 불구하고,

이전 글에서 HashMap에 대해 작성할 때 이 내용을 포함시키지 않은 것은 단순히 이전 글의 양이 너무 많아졌기 때문이다..

 

먼저, hashCode() 메서드에 Key로 삽입되는 데이터를 넣어 해시 값(해시 버킷의 인덱스)을 생성한다.

 

생성된 해시 값을 사용하여 해시 버킷에 접근했을 때,

해당 해시 버킷에 데이터가 없다면 넣고 끝나지만, 데이터가 있다면 충돌이 발생한다.

 

이때, 두 가지 선택지가 존재하는데,

 

(1) 이미 존재하는 데이터의 Key 값이 새로 넣으려는 데이터의 Key 값과 같으면,

이미 존재하는 데이터의 Value 값을 새로 넣으려는 데이터의 Value 값으로 교체하거나

 

(2) 이미 존재하는 데이터의 Key 값이 새로 넣으려는 데이터의 Key 값과 다르면,

이미 존재하는 데이터의 뒤에 새로 넣으려는 데이터를 연결하여 삽입한다.

(충돌 처리 방식이 Seperate Chaining + Linked List인 경우)

 

 

(1)과 (2) 방식 모두,

이미 존재하는 데이터의 Key 값과 새로 넣으려는 데이터의 Key 값을 비교해야 하는데,

이때 equals() 메서드가 사용된다.

 

GeeksforGeeks에서 발행한 article 중

Internal Working of HashMap in Java 를 보면 더욱 이해가 잘 간다.

 

---

 

여기까지 HashMap과 HashSet에 대해 자세히 알아보았다.

 

드디어 원래 목표였던 HashMap과 HashSet의 차이점에 대해 다음 글에서 작성한다.

 

 

끝!