해시 집합(Hash Set)

집합(Set)은 배열과 비슷하지만 두 가지 중요한 차이점이 있는 요소들의 모음이다. 첫째, 집합 내 요소들의 순서는 중요하지 않다. 둘째, 각 요소는 단 한 번만 나타날 수 있다.

다음 예제가 배열이라면 모두 다르게 취급된다. 하지만 이들은 모두 동일한 집합을 나타낸다.

[1 ,2, 3]
[2, 1, 3]
[3, 2, 1]
[1, 2, 2, 3, 1]

각 요소는 단 한 번만 나타날 수 있기 때문에, 요소를 몇 번 적었는지는 중요하지 않다. 단 하나만 유효하다.

참고: 요소들의 순서가 중요하지 않은 경우, 배열 대신 집합을 사용하는 것을 선호한다. 집합을 사용하면 프로그래머에게 요소들의 순서가 중요하지 않다는 것을 명확히 전달할 수 있다. 배열을 사용한다면, 동일한 가정을 할 수 없다.

집합에서 일반적으로 수행하는 연산은 다음과 같다:

요소 삽입
요소 제거
특정 요소가 집합에 포함되어 있는지 확인
다른 집합과 합집합(union) 구하기
다른 집합과 교집합(intersection) 구하기
다른 집합과 차집합(difference) 구하기

합집합, 교집합, 차집합은 두 집합을 하나로 결합하는 방법이다:

Swift 1.2부터 표준 라이브러리에 Set 타입이 포함되어 있지만, 여기서는 직접 구현하는 방법을 보여준다. 실제 프로덕션 코드에서는 사용하지 않겠지만, 집합이 어떻게 구현되는지 이해하는 데 도움이 될 것이다.

간단한 배열을 사용해 집합을 구현할 수 있지만, 이는 가장 효율적인 방법은 아니다. 대신 딕셔너리를 사용한다. Swift의 딕셔너리는 해시 테이블을 기반으로 구현되어 있기 때문에, 우리가 만드는 집합은 해시 집합이 된다.

코드 분석

Swift로 구현한 HashSet의 초기 코드는 다음과 같다:

public struct HashSet<T: Hashable> {
    fileprivate var dictionary = Dictionary<T, Bool>()

    public init() {

    }

    public mutating func insert(_ element: T) {
        dictionary[element] = true
    }

    public mutating func remove(_ element: T) {
        dictionary[element] = nil
    }

    public func contains(_ element: T) -> Bool {
        return dictionary[element] != nil
    }

    public func allElements() -> [T] {
        return Array(dictionary.keys)
    }

    public var count: Int {
        return dictionary.count
    }

    public var isEmpty: Bool {
        return dictionary.isEmpty
    }
}

이 코드는 Swift의 내장 Dictionary를 활용해 매우 간단하게 구현했다. 딕셔너리를 사용한 이유는 딕셔너리의 키가 유니크해야 한다는 점이 집합의 요소와 동일하기 때문이다. 또한 딕셔너리는 대부분의 연산에서 **O(1)**의 시간 복잡도를 가지기 때문에 이 집합 구현도 매우 빠르다.

딕셔너리를 사용하기 때문에 제네릭 타입 T는 Hashable을 준수해야 한다. 해시 가능한 모든 타입의 객체를 이 집합에 넣을 수 있다. (이는 Swift의 기본 Set도 마찬가지다.)

일반적으로 딕셔너리는 키와 값을 연결하는 데 사용하지만, 집합에서는 키만 중요하다. 그래서 딕셔너리의 값 타입으로 Bool을 사용했고, 항상 true로 설정한다. (false로 설정할 일은 없다.) (여기서는 아무 타입이나 사용할 수 있지만, Bool이 가장 적은 공간을 차지한다.)

이 코드를 플레이그라운드에 복사하고 몇 가지 테스트를 추가해 보자:

var set = HashSet<String>()

set.insert("one")
set.insert("two")
set.insert("three")
set.allElements()      // ["one, "three", "two"]

set.insert("two")
set.allElements()      // 여전히 ["one, "three", "two"]

set.contains("one")    // true
set.remove("one")
set.contains("one")    // false

allElements() 함수는 집합의 내용을 배열로 변환한다. 이 배열의 요소 순서는 추가한 순서와 다를 수 있다. 앞서 말했듯이, 집합은 요소의 순서를 고려하지 않는다. (딕셔너리도 마찬가지다.)

집합 결합

집합의 유용성은 주로 여러 집합을 결합하는 방식에서 드러난다. (일러스트레이터나 스케치 같은 벡터 드로잉 프로그램에서 합집합, 차집합, 교집합 옵션으로 도형을 결합해 본 적이 있다면, 이와 같은 개념이다.)

합집합 연산을 위한 코드는 다음과 같다:

extension HashSet {
    public func union(_ otherSet: HashSet<T>) -> HashSet<T> {
        var combined = HashSet<T>()
        for obj in self.dictionary.keys {
            combined.insert(obj)
        }
        for obj in otherSet.dictionary.keys {
            combined.insert(obj)
        }
        return combined
    }
}

두 집합의 합집합은 집합 A와 집합 B의 모든 요소를 포함하는 새로운 집합을 만든다. 물론 중복된 요소는 한 번만 포함된다.

예제:

var setA = HashSet<Int>()
setA.insert(1)
setA.insert(2)
setA.insert(3)
setA.insert(4)

var setB = HashSet<Int>()
setB.insert(3)
setB.insert(4)
setB.insert(5)
setB.insert(6)

let union = setA.union(setB)
union.allElements()           // [5, 6, 2, 3, 1, 4]

두 집합의 합집합은 모든 요소를 포함한다. 3과 4는 두 집합에 모두 존재하지만 한 번만 나타난다.

두 집합의 교집합은 두 집합이 공통으로 갖는 요소만 포함한다. 코드는 다음과 같다:

extension HashSet {
    public func intersect(_ otherSet: HashSet<T>) -> HashSet<T> {
        var common = HashSet<T>()
        for obj in dictionary.keys {
            if otherSet.contains(obj) {
                common.insert(obj)
            }
        }
        return common
    }
}

테스트해 보자:

let intersection = setA.intersect(setB)
intersection.allElements()

결과는 [3, 4]이다. 이 값들은 집합 A와 집합 B에 공통으로 존재하는 유일한 요소다.

마지막으로, 두 집합의 차집합은 공통 요소를 제거한 나머지 요소를 포함한다. 코드는 다음과 같다:

extension HashSet {
    public func difference(_ otherSet: HashSet<T>) -> HashSet<T> {
        var diff = HashSet<T>()
        for obj in dictionary.keys {
            if !otherSet.contains(obj) {
                diff.insert(obj)
            }
        }
        return diff
    }
}

이 연산은 intersect()와 반대 개념이다. 실행해 보자:

let difference1 = setA.difference(setB)
difference1.allElements()                // [2, 1]

let difference2 = setB.difference(setA)
difference2.allElements()                // [5, 6]

다음 단계는?

Swift의 기본 Set 문서를 살펴보면 훨씬 더 다양한 기능을 제공한다는 것을 알 수 있다. HashSet을 SequenceType에 맞게 확장하면 for...in 루프로 반복할 수 있게 된다.

또 다른 방법은 Dictionary를 실제 해시 테이블로 대체하는 것이다. 이때 키만 저장하고 값을 연결하지 않는다. 따라서 Bool 값이 더 이상 필요하지 않다.

특정 요소가 집합에 속하는지 확인하거나 합집합을 구해야 하는 경우가 많다면 union-find 자료 구조가 더 적합할 수 있다. 이 구조는 사전 대신 트리 구조를 사용해 find와 union 연산을 매우 효율적으로 수행한다.

참고: HashSet을 ArrayLiteralConvertible에 맞게 확장해 let setA: HashSet<Int> = [1, 2, 3, 4]와 같이 작성할 수 있도록 하고 싶지만, 현재는 컴파일러가 크래시를 일으킨다.

Swift Algorithm Club을 위해 Matthijs Hollemans가 작성함