Set.contains의 시간복잡도가 O(1)인 이유 (Hashable)

 

최근에 새로운 사이드 프로젝트와 겸해서 다른 작은 프로젝트를 만들었는데, 다 만들고 나니 아차 싶었던 게 꽤 많이 보인다. 이래서 프로젝트엔 완성이 없고 방망이 깎듯이 계속 다듬고 깎아나가야 하는 듯하다. 불과 며칠 전에 한 프로젝트인데도 다시 리뷰하는데 아쉽다.

가장 아쉬운 것은 중복 값을 담지 않는 시퀀스를 담는 것으로 Array를 사용한 것이다. 거기다가 검색하는 데에 .contains를 사용했으니, 시간복잡도는 O(n)이 무조건 나오게 된다. (Array 특성상 contains를 하면 타겟 값을 찾아낼 때까지 모든 요소와 비교하기 때문에)

Set을 썼다면 좋았을 텐데, 그거 고치는 거 얼마 걸리지도 않는데... 싶어 아쉬워하다가 오늘은 즉흥적으로 Set contains 시간복잡도가 왜 O(1)인지 적어본다.

 

한줄요약 : Array는 요소를 전부 순회하며 찾기 때문에 O(n)이지만, Set은 내부적으로 해시 테이블을 사용하는 것으로 추정되어 O(1)이다.

 

우선 Array와의 공통점, 차이점부터 이해하는 것이 좋겠다.

 

 

Set과 Array의 공통점

둘 모두 Sequence, Collection을 서브클래싱하고 있다. 따라서 Sequence, Collection의 메소드와 프로퍼티인 isEmpty, for ... in 문 등을 사용할 수 있다.

또한 Struct로 구현된 것 역시 공통점이다.

@frozen
struct Set<Element> where Element : Hashable

@frozen
struct Array<Element>

 

 

근본적인 차이점

	Array	Set
요소 값의 중복 허용	O	X
요소 간 순서 보장, 인덱스로 접근 가능	O	X
요소 타입에 제한	X	O (Hashable한 타입이어야 함)

이런 차이점이 있다.

흔히 중복 허용 여부와 순서 보장을 차이점으로 꼽게 되는데, 이 글에서 다룰 .contains 시간 복잡도는 Set의 요소 타입이 Hashable로 제한되어 있다는 데에 핵심이 있다.

 

 

Hashable

Equatable을 준수하는 프로토콜로, Hashable 프로토콜을 준수하는 타입들은 Hasher에 의해 해싱되어 해시값을 만들 수 있음을 의미한다. Hashable한 타입들은 set의 요소가 될 수 있으며, 딕셔너리의 key가 될 수 있다.

Swift에서 기본으로 제공되는 String, Int, Float, Bool 등의 타입들은 모두 Hashable을 준수한다.

 

 

그래서 Hashable이 왜 필요한가?

Set은 내부적으로 해시 테이블로 구현되어 있기 때문이다.

해시 테이블은 빠른 검색 속도가 특징인 자료구조이다. [key: value] 구조(딕셔너리가 이렇게 구현되어 있다)로 이뤄져 있는데, key를 해시 함수에 넣어 고유한 인덱스를 만들어서 버킷(배열)의 해당 인덱스에 값을 집어넣는 원리다.

 

도서관에 가보면 모든 책은 고유한 청구 기호를 갖는다(똑같은 책이 여러 권 있는 경우를 제외하면).

도서관은 나름의 해시 함수를 돌려서 해당 제목과 장르(key)의 책(value)이 서가(버킷)의 어느 자리(인덱스)에 위치할지 청구 기호(해시값)를 결정한다.

예를 들어 어떤 책(value)의 장르가 철학서(key)라면 100번대(index)일 것이고, 클래식 음악가를 다룬 책이라면 600번대, 문학이라면 800번대 청구기호로 빠질 것이다. 

 

해시 함수도 이와 같은 원리이다. 해시 함수를 거치는 모든 값들은 고유한 해시값을 갖게 된다.

해시값은 중복되지 않는다(사실 그런 일은 일어나긴 한다. 해시 충돌이 일어나면, key로 접근했을 때 저장했던 value가 아닌 의도하지 않은 값이 나올 것이다. 학부 과정에서 해시 충돌에 대한 해결법으로 버킷 이외에 다른 메모리를 추가로 써서 버킷에는 실제 value가 아니라 레퍼런스만 용도로 사용하는 체이닝 솔루션 등을 다루지만, 이 글에서는 논외로 한다).

 

이런 이유로 key값은 고유해야 한다. 상술했듯 그 이유는 특정 키를 해시 함수 처리한 값이 고유한 인덱스를 갖기 때문이다. 그래야 키를 기반으로 값을 검색했을 때 O(1) 시간복잡도로 제공할 수 있게 된다.

Hash table - Wikipedia

 

 

해시 함수를 사용하는 Set

Set도 이와 마찬가지다. Set의 내부 구현이 정확히 공개되어 있지는 않지만, Hashable 프로토콜을 준수하는 타입만을 요소로 받는 것으로 보아 내부적으로 해시 테이블 방식으로 구현되어 있을 것으로 추정된다.

Swift의 Collection 모음을 정의해놓은 파일에 가서 찾아보면 Sequence 프로토콜을 준수하는 Set의 .contains 메소드는 O(1) 시간복잡도라고 쓰여 있다.

extension Set : Sequence {

    /// Returns an iterator over the members of the set.
    @inlinable public func makeIterator() -> Set<Element>.Iterator

    /// Returns a Boolean value that indicates whether the given element exists
    /// in the set.
    ///
    /// This example uses the `contains(_:)` method to test whether an integer is
    /// a member of a set of prime numbers.
    ///
    ///     let primes: Set = [2, 3, 5, 7]
    ///     let x = 5
    ///     if primes.contains(x) {
    ///         print("\(x) is prime!")
    ///     } else {
    ///         print("\(x). Not prime.")
    ///     }
    ///     // Prints "5 is prime!"
    ///
    /// - Parameter member: An element to look for in the set.
    /// - Returns: `true` if `member` exists in the set; otherwise, `false`.
    ///
    /// - Complexity: O(1)
    @inlinable public func contains(_ member: Element) -> Bool
}

좀 더 명확한 증명을 위해 이번에는 Set의 요소가 될 수 있는 Hashable한 타입인 Int를 찾아본다.

Hashable한 타입들은 내부적으로 hash(into:) 함수와 hashValue 값을 갖고 있다. 

extension Int : Hashable {

    /// Hashes the essential components of this value by feeding them into the
    /// given hasher.
    ///
    /// - Parameter hasher: The hasher to use when combining the components
    ///   of this instance.
    @inlinable public func hash(into hasher: inout Hasher)

    /// The hash value.
    ///
    /// Hash values are not guaranteed to be equal across different executions of
    /// your program. Do not save hash values to use during a future execution.
    ///
    /// - Important: `hashValue` is deprecated as a `Hashable` requirement. To
    ///   conform to `Hashable`, implement the `hash(into:)` requirement instead.
    ///   The compiler provides an implementation for `hashValue` for you.
    public var hashValue: Int { get }
}

1부터 10까지의 hashValue를 조회해본다. 

for i in 1...10 {
	print(i.hashValue)
}

1339780911849299071
416147855816999300
4401088619744177936
5007427146145620810
4721801425092769755
-6243740974086856334
-8706920861031170862
-6496063942777028032
-8682395946424165833
-1692729095397438653

겹치기도 힘들 규모의 꽤 극단적인.. 숫자가 나온다. 

이것들이 Set에 들어가면 어떻게 될까? 1은 key가 된다.

즉 Set.contains(1)을 했을 때, Array처럼 Set의 모든 요소들을 순회하며 1을 찾아나가는 게 아니라 1을 해싱한 133978...번째 인덱스를 버킷에서 조회해, 조회 결과 값의 유무에 따라 true/false를 반환하게 될 것으로 추정된다. 

 

끝!