[자료구조] HashSet이란 무엇인가?

HashSet이란 무엇인가?

---

앞선 포스팅에서 ADT 관점에서 List와 Set의 차이점에 대해 살펴보았다. 하지만 ADT의 구현체인 DS관점에서 HashSet이 내부적으로 어떻게 구현되었는지 살펴보고자 해당 포스팅을 작성한다.

 

Set은 '중복 원소를 허용하지 않는다'가 포인트라고 했다. 그러면 Hash는 왜 붙은 것일까? 이를 알기 위해서는 먼저 Hash에 대한 기본 개념을 알아야하기에 Hash에 대해 알아보자.

 

해싱이란? (Hashing)

Hash, HashTable에 대한 개념은 아래 포스팅에서 자세하게 설명하였으니 참고하기 바란다.

[자료구조] 해시테이블(HashTable)이란?

 

Set은 '중복 원소'를 허용하지 않는다고 했다.

이 말은 우리가 원소를 추가해야 할 때 마다 해당 원소가 중복되는 원소인지 아닌지를 검사해야한다는 것이다. 그럴 때마다 모든 원소를 검사해가면서 한다면 매우 비효율적이다.

 

그렇기에 고안한 방법이 hash함수를 통해 특정 값에 대한 고유의 다이제스트를 얻고 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만 검사하도록 하는 것이다.

 

이 것이 HashSet의 기본 개념이다.

 

그러면 객체의 hash값은 어떻게 얻는지가 문제일 것이다. 그렇다고 굳이 hash함수를 구현할 필요는 없다. 자바에서는 hashCode() 라는 매우 간편한 함수가 있기 때문이다.

 

hashCode()는 객체의 주소값을 이용하여 해시 알고리즘에 의해 생성 된 고유의 정수값을 반환한다. 즉, 객체가 같은 메모리 주소를 가리키고 있다면 같은 정수값을 얻을 것이다.

int a = X.hashCode();

 

여기서 주의할 점은 '객체가 같은 주소'를 가리킬 경우'이다.

 

즉, 객체가 같은 내용을 지니더라도 가리키는 주소가 다르면 다른 값을 지닌다는 것이다.

public class Test {
 
	public static void main(String[] args) {
		
		Custom a = new Custom("aaa");
		Custom b = new Custom("aaa");	// 내용이 같음
		Custom c = a;					// 주소 복사 (shallow copy)
		
		System.out.println("a객체 : " + a.hashCode());
		System.out.println("b객체 : " + b.hashCode());
		System.out.println("c객체 : " + c.hashCode());
	}
	
	static class Custom {
		String str;
		
		public Custom(String str) {
			this.str = str;
		}
	}
}

 

 

보시다시피 new 연산자로 생성된 객체의 경우 서로 다른 객체를 의미한다. 즉, a객체와 b객체는 내용이 같더라도 서로 다른 주소에 할당되기 때문에 다른 값이 나오고, a와 c는 같은 주소를 가리키기 때문에 같은 값을 갖는다.

 

 

 

그래서 우리가 쓰는 String, int, double 등의 자료형들은 hashCode()를 오버라이드(Override)하여 객체 내용이 비교될 수 있도록 재정의를 하고 있다.

 

예를들어 String의 경우 다음과 같이 재정의를 하고 있다.

 

그렇기 때문에 기본적으로 HashSet을 쓸 때 우리가 쓰는 기본 자료형(String, Integer, Double 등등..)으로는 같은 내용일 경우 동일한 값을 갖으나, 만약에 사용자 클래스를 사용하게 될 경우 해당 클래스 내에 hashCode 메소드를 오버라이드를 해주지 않으면 메모리 주소를 기반으로 해싱된 값이 나오기 때문에 객체 내용을 비교해주기 위해서는 반드시 hashCode()를 오버라이드 해주어야 한다.

 

 

해시 충돌

위 개념 말고 추가로 반드시 알아야 하는 개념이 있다. 바로 해시 충돌이라는 것이다.

 

위 hashCode()를 사용하더라도 1차적인 문제점이 있다. 일단 int형의 범위다. int형은 32bit(4byte)로 표현되는 자료형이다.

즉, 2^32 경우의 수를 갖을 수 있다는 의미다.

 

하지만, 우리가 생성가능한 경우의 수는 훨씬 많을 것이다. 2^32로 모든 객체를 다 표현할 수 없다는 한계가 있다는 것이다.

예를들어 다음과 같은 경우가 있다.

public static void main(String[] args) {
	String str1 = "0-42L";
	String str2 = "0-43-";
 	
    System.out.println(str1.hashCode()); // 45721201
    System.out.println(str2.hashCode()); // 45721201
    
	System.out.println((str1.hashCode() == str2.hashCode()));	// true가 나온다.
}

위와같이 서로 다른 문자열임에도 해싱된 값이 같은 경우를 해시 충돌이라고 한다.

 

 

 

설령 생성되는 객체가 우연하게 모두 2^32로 표현 가능 하더라도 문제가 되는 점은 그만큼의 버킷(배열) 공간을 생성해야한다는 점이다. 이는 메모리낭비가 심할뿐더러 Java에서는 대략 단일 배열에 대해 약 21억 크기까지만 생성이 가능하다.

 

그렇기 때문에 메모리의 낭비를 줄이기 위해 배열의 사이즈를 줄여서 사용한다.

 

예를들어 M개의 인덱스를 갖고있는 배열(테이블)이 있을 때 다음과 같이 인덱스를 지정하는 것이다.

int index = X.hashCode() % M;

이 때, 자바에서는 hashCode()가 음수 값이 나올 수도 있다.

그렇기 때문에 hashCode()를 사용하는 경우 절댓값으로 변환하여 음수의 경우 양수로 변환해주는 것이 필요하다.

int index = Math.abs(X.hashCode()) % M;

위와 같이 해주어도 앞서 말했듯이 해시충돌의 경우와 버킷(배열)의 크기에 따른 같은 index를 참조하는 일이 발생할 수 밖에 없다. 

 

이럴 때 해결 할 수 있는 방법은 크게 두 가지로 나뉜다.

 

 

 

 

 

 

위와 같이 Open Addressing 방식과 Separate Chaining 방식이 있다. (물론 그 외에도 이중 해싱 등 다양한 방식이 있긴 하다.)

각각의 장단점은 이러하다.

	장점	단점
Open Addressing	해시충돌이 일어날 가능성이 적기 때문에 데이터의 개수가 작을수록 속도가 빨라진다.  연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋아진다.	해시충돌이 발생하면 해당 객체의 인덱스 값이 바뀌어 버린다. 부하율(load factor) 즉, 테이블에 저장된 데이터의 개수가 많아질수록(=밀도가 높아질수록) 성능이 급격히 저하된다.
Separate Chaining	해시충돌이 일어나더라도 연결리스트로 노드가 연결되기에 index가 변하지 않는다. 테이블의 각 인덱스는 연결리스트로 구현되기 때문에 데이터 개수의 제약을 거의 받지 않는다.	부하율(load factor)에 따라 선형적으로 성능이 저하 됨. 즉, 부하율이 작을 경우에는 Open Addressing 방식이 빠르다.

 

그럼 Java에서는 무엇을 채택했을까?.. 바로 Separate Chaining이다.

 

그리고 마지막으로 몇 가지만 더 설명하고 가도록 하겠다.

위에서 설명했듯이 부하율(load factor)에 대해 말하자면, 보통 데이터가 0.7~0.8(70% ~ 80%) 정도 채워질 경우 성능이 저하된다고 한다. 그래서 Java에서도 load factor 값을 0.75 로 두고 있다.

 

위키피디아에서 다음과 같이 그래프로 보여주고 있다. (참고자료로만 보시길 바란다.)

 

https://en.wikipedia.org/wiki/Hash_table

 

 

또한 최악의 경우 해시충돌에 의해 한 개의 인덱스에 여러개의 노드가 연결 될 경우도 있다. 자바 내부에서는 이럴 경우 해당 인덱스의 LinkedList를 Binary Tree(이진트리)로 변환하여 데이터의 색인 속도를 높인다.

 

 

 

 

코드로 살펴보는 HashSet

---

위에서 HashSet에서 Hash가 무엇인지 살펴보았다. 이제는 HashSet 내부적으로 어떻게 구현되어있는지 살펴보자.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {}

HashSet은 Set 인터페이스를 구현하고 있는 가장 대표적인 클래스다.

 

먼저 Set의 특징을 다시 한번 더 정리해보자.

• 배열과 연결 노드를 결합한 자료구조 형태
• 중복되지 않은 원소들을 저장하고 null을 허용한다.
• 추가, 삭제, 검색, 접근성이 모두 뛰어나다
• 가장 빠른 임의 검색 접근 속도를 가진다
• 내부적으로 HashMap을 사용한다.
• 순서를 유지하지 않는다
• Thread-Safe 하지 않다.

 

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 객체를 만들면 내부적으로 HashMap 객체를 만들어서 사용한다.

 

Constructs a new, empty set; the backing

HashMap

instance has default initial capacity (16) and load factor (0.75).

 

그리고 문서에도 위와 같이 적혀있는데 해석해보면 기본 초기 용량 = 16, 로드팩터 = 0.75라고 하는 것을 볼 수 있다.

 

load factor 란 무엇인가?

• 로드팩터는 (데이터의 개수)/(저장공간)을 의미합니다.

적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N 이라고 했을 때 적재율은 K/N 이다.

 

데이터의 개수가 증가해서 Load Factor의 값이 원래 Load Factor의 값보다 커지게 되면 저장 공간의 크기는 증가되고 해시 재정리 작업(refresh)을 해야만 한다. Load Factor라는 값이 클수록 공간은 넉넉해지지만, 데이터를 찾는 시간은 증가한다.

 

따라서 초기 공간 개수와 Load Factor는 데이터의 크기를 고려하여 산정하는 것이 좋다. (즉, Load Factor는 데이터를 효율적으로 관리하기 위해서 처음에 설정하는 값이라고 생각하면 된다.)

 

그리고 데이터가 어느정도 쌓이면 버킷 사이즈를 resized 해야할 지에 대한 기준이라고 생각할 수 있다

왜냐하면 초기크기가 (데이터의 개수)/(Load Factor) 보다 클 경우에는 데이터를 쉽게 찾기 위한 해시 재정리 작업이 발생하지 않기 때문이다. 따라서 대량의 데이터를 여기에 담아 처리할 때에는 초기 크기와 Load Factor의 값을 조절해 가면서 가장 적당한 크기를 찾아야만 한다.

 

---

 

그러면 이제 HashSet API들을 몇 개 살펴보자.

 

add() 메소드

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 boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

add() 메소드 내부를 보면 Map을 이용해서 데이터를 넣는데 데이터가 없을 경우에 true, 데이터가 존재한다면 false를 반환하는 것을 볼 수 있다.

 

요약하자면?

• 해시 맵은 기본 용량이 16개 요소인 버킷의 배열로, 각 버킷은 다른 해시 코드 값에 해당한다.
• 여러 개체가 동일한 해시 코드 값을 갖는 경우 단일 버킷에 저장된다.
• 로드 팩터에 도달하면 새 배열이 이전 배열의 두 배 크기로 생성되고 모든 요소가 새 해당 버킷으로 재할당된다.
• 값을 검색하려면 키를 해시 하고, 해당 버킷으로 찾아간다. 만약 해당 버킷에 둘 이상의 개체들이 있다면 LinkedList 탐색하듯이 탐색하게 된다.

 

 

 

그러면 어떻게 Set은 중복되지 않은 원소들을 유지할 수 있을까?

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 boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

객체를 해시 집합에 넣으면 객체의 해시 코드 값을 사용하여 요소가 집합에 있는지 없는지 확인한다. 위에 실제 HashSet 클래스를 보면 내부적으로 Map을 사용하고 put을 할 때 value 자리에 Object 값을 넣어주는 것을 볼 수 있다.

 

해시 코드로 계산된 해시 값은 특정 버킷 위치에 해당한다. 하지만 동일한 해시 코드를 가진 두 객체가 같지 않을 수도 있다.

그래서 동일한 버킷에서는 equals() 메소드를 이용해서 체크한다. (따라서 equals(), hashCode() 메소드가 매우 중요하다.)

 

 

HashSet의 성능

HashSet의 성능은 초기 용량, 로드 팩터에 의해 결정된다.

 

Set에 원소를 add 하는 과정은 일반적으로 시간복잡도 O(1)에 의해서 가능하지만, 최악의 경우는 O(n) 까지 나빠질 수 있다. 따라서 HashSet의 초기 용량을 설정하는 것이 중요하다.

 

한마디로 요약하면, 로드 팩터는 저장용량 대비 데이터를 이정도까지 채워야 탐색시간, 버킷 resize 등을 효율적으로 할 수 있다라고 미리 설정해놓는 것이다.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;

    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
}

HashSet 클래스의 생성자를 보면 초기용량을 받는 것, 초기용량, 로드팩터, 매개변수가 없는 생성자들이 존재하는 것을 볼 수 있다.

Set<String> hashset = new HashSet<>();         // 기본용량 16, 로드팩터 0.75
Set<String> hashset = new HashSet<>(20);
Set<String> hashset = new HashSet<>(20, 0.5f);

 

초기 용량을 설정하는 기준

• 초기 용량을 작게 설정하면 메모리면에서는 좋지만, 버킷사이즈를 더 크게 만드는 과정이 있기 때문에 효율적이지 않다.
• 초기 용량을 크게 설정하면 초기 메모리를 소모한다는데 단점이 있다.

 

원칙적으로

• 초기 용량이 크면 재할당이 상대적으로 적게 일어난다. 하지만 무턱대로 크게 잡으면 메모리 낭비가 될 수 있다.
• 초기 용량이 낮으면 재할당이 많이 일어나게 된다. 재할당 비용도 매우 크기 때문에 적절한 용량 설정이 필요하다.

 

마무리 결론

 

초기용량, 로드팩터 사이의 정확한 균형을 맞추는 것이 매우 중요하다. 일반적으로 기본 구현은 최적화되어 있으며 잘 작동하며, 요구 사항에 맞게 이러한 매개 변수를 조정해야 할 필요성을 느낄 경우 신중하게 수행해야 한다.

 

이렇게 HashSet에 대해서 알아보았다. 코드를 살펴 본 결과 HashSet은 HashMap을 내부에 구현하여 중복이 일어나지 않도록 한다는 사실을 알 수 있었다. 다른 Collection의 자료구조들과 다르게 HashSet은 대부분 HashMap을 이용하기 때문에 코드가 길지 않다.

 

 

 

---

참고

• https://devlog-wjdrbs96.tistory.com/242
• https://sabarada.tistory.com/65