Set 자료구조가 검색이 빠른 이유

Set은 List와 달리 중복을 허용하지 않고 순서를 보장하지 않으며 수학에서 집합과 같은 개념을 구현한 자료구조다.

 

특히 List의 검색은 O(N)인 반면 Set의 검색은 O(1)의 복잡도를 갖는다.

 

Set의 검색이 항상 O(1)을 보장하진 않지만 전반적으로 굉장히 빠르다.

 

어떻게 O(1)이 될 수 있는지 그리고 항상 O(1)을 보장할 수 없는 이유를 알아보자.

 

O(1)의 시간복잡도

O(1)의 시간 복잡도를 갖는 자료구조로 가장 유명한 것은 배열이다.

 

배열을 사용하면 인덱스를 통해 한 번에 자료에 접근이 가능하기 때문이다.

 

한 번이라는 의미는 연산이 한 번 일어난다는 의미다.

 

배열에 대한 이야기는 아래 포스팅에 적어 두었다.

ArrayList의 배열 리사이징

 

 

Set 역시 이 배열 구조를 사용하고 Hasing과 HashIndex를 이용해 O(1)의 검색, 추가, 삭제가 가능하다.

 

HashIndex

아래는 정수형 데이터를 저장하는 크기가 10인 배열이다. 두 번째 행은 인덱스를 의미한다.

0	1	2	3	4	5	6	7	8	9

 

1. 정수 8을 입력

 

- 8(입력) % 10(배열의 크기) = 8(HashIndex)

 

								8
0	1	2	3	4	5	6	7	8	9

 

 

2. 정수 100을 입력

 

- 121 % 10 = 1

 

	121							8
0	1	2	3	4	5	6	7	8	9

 

 

HashIndex는 위에서 보이듯 나머지 연산을 통해 인덱스를 구하고 자료를 저장한다.

 

위 예시에선 정수를 저장하고 있지만 실제론 사용자 정의 객체, 문자열 등 다양한 자료를 저장해야한다.

 

객체나 문자열은 숫자가 아니기 때문에 나머지 연산이 불가능하다.

 

그래서 Hash 함수를 이용해 Hash 값(정수)을 구하고 나머지 연산으로 인덱스를 구해 저장한다. (인간은 참... 똑똑하다)

 

Hashing

Hashing은 임의의 길이의 데이터를 넣어 고정된 길이의 데이터를 뱉어내는 과정을 의미한다.

 

 

 

"hashcode"라는 문자열을 Object 클래스가 제공하는 hashCode함수를 통해서 hash값을 구하면 148649979라는 값이 나온다.

 

이 hash값을 이용해 나머지 연산을 적용해 인덱스를 구할 수 있다.

 

hashCode()함수는 객체의 참조값을 기반으로 생성해내기 때문에 사용자가 정의한 객체도 적절한 hashCode를 구현해주면

 

HashSet자료구조에 얼마든지 저장할 수 있다.

 

hashcode라는 문자열을 저장해보면

 

148649979 % 10 = 9(인덱스)

 

	121							8	"hashcode"
0	1	2	3	4	5	6	7	8	9

 

 

위 표와 같이 hashcode라는 문자열은 9번 인덱스에 들어간다.

 

99를 저장해볼까?

99를 나머지 연산하면 9가 나오고 이 값이 인덱스가 된다.

 

"hashcode" 문자열과 해쉬값이 동일하고 이를 해쉬충돌이라 부른다.

 

이 해쉬값은 같은 데이터에 대해서 항상 같은 해쉬값을 뱉어주지만 다른 데이터에 대해서도 같은 해쉬값을 뱉을 수 있다.

 

	121							8	"hashcode" , 9(?)
0	1	2	3	4	5	6	7	8	9

 

단순 배열로 Set자료구조를 사용하면 해쉬 충돌 시 자료를 저장할 수 없다.

 

다른 방법이 필요하다.

 

LinkedList 개념을 활용해 같은 Hash값도 같이 저장하자.

자바의 HashSet을 들어가 살펴보면 조금 신기한 부분을 볼 수 있다.

 

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    @java.io.Serial
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

 

내부에서 HashMap을 사용하고 있다.

 

HashMap과 HashSet은 아주 많이 닮아 있기 때문에 자바에서 HashSet 내부에서 HashMap을 가져와 사용한다.

 

HashMap이란 Key , Value 쌍을 저장하는 자료구조인데, HashMap에서 Key값은 중복이 불가능하며 순서를 보장하지 않는다.

 

즉 HashMap의 key는 Set 자료구조 그 자체라 봐도 무방하다.

 

그래서 자바는 HashMap의 Value만 사용하지 않고 Key부분만 사용해 HashSet을 구현했다.

 

HashMap이 어떻게 구현돼 있는지 알아보면 HashSet도 자연스럽게 알 수 있다.

 

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

 

transient Node<K,V>[] table;

 

내부에 Node 객체 배열을 통해서 값을 저장한다.

 

 

tab[i = (n-1) & hash] 부분이 나머지 연산을 하는 부분이다.

 

n-1 & hash는 hash%n과 같은 결과를 갖는다.

 

이렇게 새로운 노드를 삽입하고 Key값이 다른데 Hash값이 같다면(해쉬충돌) 아래와 같이 새로운 노드를 연결한다.

 

 

	121							8	"hashcode" -> 9
0	1	2	3	4	5	6	7	8	9

 

해쉬 충돌이 계속 발생한다면

해쉬 충돌이 빈번하게 발생하면 HashSet의 성능이 낮아진다.

 

위 표에서 보이듯 하나의 인덱스에 Node가 계속해서 연결되면 O(1)의 시간 복잡도를 유지하기 어려워진다.

 

배열의 크기가 작다면 당연히 해쉬충돌이 빈번하게 발생할 것이기 때문에

 

자바는 배열 크기에 75%에 도달하면 배열을 2배씩 확장시킨다.

 

이렇게 보통 Linked List 방식으로 해쉬 충돌을 해결하는 것을 Separate Chaining 방식이라 부른다.

 

다음 포스팅에서 자바 해쉬충돌을 어떻게 해결하는지 더 자세히 알아보고, 다른 방식도 같이 알아보려한다.