Set, MutableSet 은 어떻게 원소에 빠르게 접근할 수 있을까?
Kotlin의 Set은 원소에 접근하는데 걸리는 시간이 평균적으로 O(1)이고 중복을 체크하는데 걸리는 시간도 O(1)이다. 이 때문에 많은 Set을 사용하면 매우 효율적으로 원소에 접근할 수 있다. 이번 글에서는 그 이유를 알아보고자 한다.
Kotlin의 Set, MutableSet에서 사용하는 자료 구조
Kotlin의 Set, MutableSet은 모두 인스턴스를 만들기 위해 LinkedHashSet을 사용한다.
Set의 내부 구현 살펴보기
Set의 모든 생성자를 보는데는 너무 시간이 많이 걸리므로 Set을 만드는 대표적인 함수인 setOf 함수만 보도록 하자. Kotlin에서 setOf를 사용해 Set 생성하는 부분을 보면 아래와 같이 구현되어 있다.
public fun <T> setOf(vararg elements: T): Set<T> = if (elements.size > 0) elements.toSet() else emptySet()
public fun <T> Array<out T>.toSet(): Set<T> {
return when (size) {
0 -> emptySet()
1 -> setOf(this[0])
else -> toCollection(LinkedHashSet<T>(mapCapacity(size)))
}
}LinkedHashSet을 만든 후 설정된 모든 값들을 추가하는 것을 볼 수 있다.
MutableSet의 내부 구현 살펴보기
MutableSet도 모든 생성자를 볼 수는 없으므로 비교적 간단하게 구현된 mutableSetOf()를 살펴보도록 하자. Kotlin에서 mutableSetOf()의 구현을 보면 LinkedHashSet의 인스턴스를 생성하는 것을 볼 수 있다.
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> mutableSetOf(): MutableSet<T> = LinkedHashSet()
LinkedHashSet은 어떤 특징을 가지는가?
자 이제 LinkedHashSet을 사용하는 것을 알았으니, LinkedHashSet이 어떤 특징을 가지길래 원소에 접근하는데 평균 O(1)의 시간 복잡도로 원소 접근, 추가, 삭제가 가능한지 살펴보자.
Kotlin에서 말하는 LinkedHashSet은 Java에서 사용하는 LinkedHashSet과 같다. 정확히는 java.util 패키지의 LinkedHashSet을 말한다.
@SinceKotlin("1.1") public actual typealias LinkedHashSet<E> = java.util.LinkedHashSet<E>
LinkedHashSet은 원소의 중복을 확인하기 위해 내부에서 HashMap을 사용한다
LinkedHashSet은 HashSet을 상속한다.
public class LinkedHashSet<E> extends HashSet<E>
이 HashSet은 내부에서 HashMap 자료구조를 사용해 원소를 저장한다. 만약 우리가 Set<Integer> 이라는 Set을 생성하면 내부에서는 HashMap<Integer, Object> 라는 자료 구조가 사용 되는 것이다.
이를 통해 원소가 삽입되면 map에 넣으면 되기 때문에 평균 O(1)이 걸리고, 접근도 map에 Key에 해당하는 값이 있는지 조회하기 때문에 O(1)이 될 수 있다.
HashSet에서 중복 확인을 위해 메모리를 추가로 절약하는 방법
HashSet에서는 Map에 원소가 삽입되면 해당 원소를 Key로 쓰고, 해당 Key에 대한 Map의 Value 값을 PRESENT라는 static한 변수로 변경한다.
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
이는 우리가 Kotlin에서 중복을 체크할 때 메모리를 절약하기 위해 MutableMap<Key Class, Unit>를 사용하는 것과 매우 비슷하다. 이 렇게 사용하면 원소를 삽입할 때 Map의 Key에 해당 하는 값에 Unit을 넣음으로써 Value에 Unit을 제외한 다른 변수를 할당하지 않음으로써 메모리를 절약할 수 있고, 조회 할 때는 만약 Key에 해당하는 값 존재하면 이미 해당 Key가 삽입되어 있음을 확인할 수 있다.
val map: Map<Char, Unit> = mapOf('a' to Unit)
map['a'] // Unit 출력
map['b'] // null 출력
HashSet의 원소 접근, 추가, 삭제에 걸리게 되는 시간이 O(1)이 아니게 되는 경우 : 해시 충돌(Hash Collision)
만약 HashSet 내부의 HashMap에 원소가 들어갈 때 Hashing 함수가 생성해내는 Hash 값이 단 하나라고 해보자(Hash Collision이 무조건 일어나는 상황). 그러면 원소에 접근하기 위해 하나하나 모두 확인해야 한다. 이때는 HashMap에 이미 들어가있는 Key가 N개라고 했을 때 원소 접근, 추가, 삭제에 평균 O(N)의 시간이 걸린다.
만약 Hashing 함수가 생성해낼 수 있는 Hash값이 최대 M개여서, 1/M의 확률로 충돌을 일으킨다고 하면 원소 접근, 추가, 삭제에 평균 O(N/M)의 시간이 걸린다.
따라서 Hash 충돌이 일어나는 것을 최대한 방지해야 좋은 성능을 낼 수 있다.
정리
- Kotlin의 Set, MutableSet은 내부적으로 HashMap을 사용해 원소를 보관한다.
- HashMap을 사용할 때, Key-Value 쌍의 Value 값으로는 static한 Object 인스턴스를 사용해 메모리를 절약한다.
- Set, MutableSet은 대부분의 경우 O(1)로 접근, 추가, 삭제가 가능하지만, Hash Collision이 일어나는 경우 그렇지 않을 수 있다.
