해시 테이블은 "키"를 기반으로 객체를 저장하고 검색할 수 있게 해준다.
해시 테이블은 딕셔너리, 맵, 연관 배열과 같은 자료구조를 구현하는 데 사용된다. 이러한 자료구조는 트리나 일반 배열로도 구현할 수 있지만, 해시 테이블을 사용하면 더 효율적이다.
이것이 바로 Swift의 내장 Dictionary 타입이 키가 Hashable 프로토콜을 준수해야 하는 이유를 설명한다. 내부적으로 해시 테이블을 사용하기 때문이다. 이 장에서 배울 해시 테이블과 동일한 원리다.
해시 테이블은 기본적으로 배열이다. 처음에는 이 배열이 비어 있다. 특정 키 아래에 값을 넣으면, 키를 사용해 배열의 인덱스를 계산한다. 다음은 간단한 예제다:
hashTable["firstName"] = "Steve"
hashTable 배열:
+--------------+
| 0: |
+--------------+
| 1: |
+--------------+
| 2: |
+--------------+
| 3: firstName |---> Steve
+--------------+
| 4: |
+--------------+이 예제에서 키 "firstName"은 배열의 인덱스 3에 매핑된다.
다른 키로 값을 추가하면 또 다른 배열 인덱스에 위치한다:
hashTable["hobbies"] = "Programming Swift"
hashTable 배열:
+--------------+
| 0: |
+--------------+
| 1: hobbies |---> Programming Swift
+--------------+
| 2: |
+--------------+
| 3: firstName |---> Steve
+--------------+
| 4: |
+--------------+여기서 핵심은 해시 테이블이 어떻게 배열 인덱스를 계산하는지다. 이 부분에서 해싱이 등장한다. 다음과 같은 코드를 작성하면,
hashTable["firstName"] = "Steve"해시 테이블은 키 "firstName"을 가져와 hashValue 프로퍼티를 요청한다. 따라서 키는 반드시 Hashable을 준수해야 한다.
"firstName".hashValue를 호출하면 큰 정수인 -4799450059917011053을 반환한다. 마찬가지로 "hobbies".hashValue는 4799450060928805186을 반환한다. (실제 값은 다를 수 있다.)
이 숫자들은 배열의 인덱스로 사용하기에는 너무 크고, 그중 하나는 음수다. 이런 큰 숫자를 적절하게 사용하는 일반적인 방법은 먼저 해시 값을 양수로 만든 다음 배열 크기로 나머지 연산을 수행하는 것이다.
배열의 크기가 5이므로, "firstName" 키의 인덱스는 abs(-4799450059917011053) % 5 = 3이 된다. "hobbies"의 배열 인덱스는 1로 계산할 수 있다.
이런 방식으로 해시를 사용하는 것이 딕셔너리를 효율적으로 만든다. 해시 테이블에서 엘리먼트를 찾으려면 키를 해싱해 배열 인덱스를 얻고, 그 인덱스로 배열에서 엘리먼트를 조회한다. 이 모든 작업은 상수 시간이 소요되므로 삽입, 검색, 삭제 모두 **O(1)**의 시간 복잡도를 가진다.
참고: 배열에서 객체가 어디에 위치할지 예측하기 어렵다. 따라서 딕셔너리는 해시 테이블 내 엘리먼트의 순서를 보장하지 않는다.
한 가지 문제가 있다. 해시 값을 배열의 크기로 나눈 나머지를 사용하기 때문에, 두 개 이상의 키가 동일한 배열 인덱스에 할당될 수 있다. 이를 충돌이라고 부른다.
충돌을 방지하는 한 가지 방법은 배열의 크기를 크게 만들어서 두 키가 동일한 인덱스에 매핑될 가능성을 줄이는 것이다. 또 다른 방법은 배열의 크기를 소수로 설정하는 것이다. 하지만 충돌은 어쩔 수 없이 발생하기 때문에, 이를 처리할 방법을 찾아야 한다.
우리의 테이블이 작기 때문에 충돌을 쉽게 보여줄 수 있다. 예를 들어, "lastName" 키의 배열 인덱스도 3이지만, 이미 이 인덱스에 있는 값을 덮어쓰고 싶지는 않다.
충돌을 처리하는 일반적인 방법은 체이닝을 사용하는 것이다. 배열은 다음과 같이 생겼다:
buckets:
+-----+
| 0 |
+-----+ +----------------------------+
| 1 |---> | hobbies: Programming Swift |
+-----+ +----------------------------+
| 2 |
+-----+ +------------------+ +----------------+
| 3 |---> | firstName: Steve |---> | lastName: Jobs |
+-----+ +------------------+ +----------------+
| 4 |
+-----+체이닝을 사용하면 키와 값이 배열에 직접 저장되지 않는다. 대신, 각 배열 요소는 0개 이상의 키/값 쌍으로 이루어진 리스트다. 배열 요소를 일반적으로 버킷이라고 부르고, 리스트를 체인이라고 부른다. 여기서는 5개의 버킷이 있고, 이 중 두 개의 버킷에 체인이 있다. 나머지 세 개의 버킷은 비어 있다.
해시 테이블에서 항목을 검색하기 위해 다음과 같은 코드를 작성하면,
let x = hashTable["lastName"]먼저 "lastName" 키를 해시하여 배열 인덱스인 3을 계산한다. 버킷 3에 체인이 있으므로, 리스트를 따라가면서 "lastName" 키에 해당하는 값을 찾는다. 이는 문자열 비교를 통해 키를 확인하는 방식으로 이루어진다. 해시 테이블은 체인의 마지막 항목에 키가 있는지 확인하고, 해당 값인 "Jobs"를 반환한다.
이 체이닝 메커니즘을 구현하는 일반적인 방법은 연결 리스트나 다른 배열을 사용하는 것이다. 체인 내 항목의 순서는 중요하지 않으므로, 리스트 대신 집합으로 생각할 수도 있다. (이제 "버킷"이라는 용어가 어디서 유래했는지 상상할 수 있다. 모든 객체를 버킷에 그냥 던져 넣는 것이다.)
체인이 길어지면 해시 테이블에서 항목을 찾는 과정이 느려지기 때문에, 체인이 길어지지 않도록 해야 한다. 이상적으로는 체인이 전혀 없어야 하지만, 실제로는 충돌을 피할 수 없다. 고품질의 해시 함수를 사용하고 충분한 수의 버킷을 제공함으로써 가능성을 높일 수 있다.
참고: 체이닝 대신 "개방 주소법"을 사용할 수도 있다. 이 방식은 배열 인덱스가 이미 사용 중이면 다음 사용 가능한 버킷에 요소를 넣는 방식이다. 이 접근 방식은 장단점이 있다.
Swift에서 해시 테이블의 기본 구현을 단계별로 살펴보자.
public struct HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket]
private(set) public var count = 0
public var isEmpty: Bool { return count == 0 }
public init(capacity: Int) {
assert(capacity > 0)
buckets = Array<Bucket>(repeatElement([], count: capacity))
}
HashTable은 제네릭 컨테이너이며, 두 가지 제네릭 타입은 Key(Hashable을 준수해야 함)와 Value이다. 여기서 Element는 체인에서 사용할 키/값 쌍이고, Bucket은 이러한 Element의 배열이다.
주요 배열은 buckets이다. 이 배열은 init(capacity) 메서드에서 제공하는 고정된 크기(즉, 용량)를 가진다. 또한 count 변수를 통해 해시 테이블에 추가된 아이템의 수를 추적한다.
새로운 해시 테이블 객체를 생성하는 예제는 다음과 같다:
var hashTable = HashTable<String, String>(capacity: 5)아직 해시 테이블은 아무 기능도 하지 않으므로, 나머지 기능을 추가해 보자. 먼저 주어진 키에 대한 배열 인덱스를 계산하는 헬퍼 메서드를 추가한다:
private func index(forKey key: Key) -> Int {
return abs(key.hashValue % buckets.count)
}이 메서드는 앞서 본 계산을 수행한다: 키의 hashValue를 buckets 배열의 크기로 나눈 나머지의 절대값을 반환한다. 이 메서드는 여러 곳에서 사용되므로 별도의 함수로 분리했다.
해시 테이블이나 딕셔너리에서 주로 수행하는 네 가지 작업은 다음과 같다:
이 작업들의 구문은 다음과 같다:
hashTable["firstName"] = "Steve" // 삽입
let x = hashTable["firstName"] // 조회
hashTable["firstName"] = "Tim" // 업데이트
hashTable["firstName"] = nil // 삭제이 모든 작업을 subscript 함수로 처리할 수 있다:
public subscript(key: Key) -> Value? {
get {
return value(forKey: key)
}
set {
if let value = newValue {
updateValue(value, forKey: key)
} else {
removeValue(forKey: key)
}
}
}이 함수는 실제 작업을 수행하는 세 가지 헬퍼 함수를 호출한다. 먼저 해시 테이블에서 객체를 조회하는 value(forKey:)를 살펴보자.
public func value(forKey key: Key) -> Value? {
let index = self.index(forKey: key)
for element in buckets[index] {
if element.key == key {
return element.value
}
}
return nil // 키가 해시 테이블에 없음
}먼저 index(forKey:)를 호출해 키를 배열 인덱스로 변환한다. 이렇게 하면 버킷 번호를 얻을 수 있지만, 충돌이 발생한 경우 이 버킷은 여러 키가 사용할 수 있다. value(forKey:)는 해당 버킷의 체인을 순회하며 키를 하나씩 비교한다. 키를 찾으면 해당 값을 반환하고, 그렇지 않으면 nil을 반환한다.
새 요소를 삽입하거나 기존 요소를 업데이트하는 코드는 updateValue(_:forKey:)에 있다. 이 코드는 조금 더 복잡하다:
public mutating func updateValue(_ value: Value, forKey key: Key) -> Value? {
let index = self.index(forKey: key)
// 버킷에 이미 이 키가 있는지 확인
for (i, element) in buckets[index].enumerated() {
if element.key == key {
let oldValue = element.value
buckets[index][i].value = value
return oldValue
}
}
// 버킷에 아직 이 키가 없음; 체인에 추가
buckets[index].append((key: key, value: value))
count += 1
return nil
}다시 한 번, 첫 번째 단계는 키를 배열 인덱스로 변환해 버킷을 찾는 것이다. 그런 다음 해당 버킷의 체인을 순회한다. 체인에서 키를 찾으면 새 값으로 업데이트한다. 키가 체인에 없으면 새로운 키/값 쌍을 체인 끝에 추가한다.
여기서 알 수 있듯이, 체인을 짧게 유지하는 것이 중요하다(해시 테이블을 충분히 크게 만들어서). 그렇지 않으면 for...in 루프에서 과도한 시간을 소모하게 되고, 해시 테이블의 성능이 **O(1)**이 아니라 **O(n)**에 가까워진다.
요소 제거도 비슷하게 체인을 순회한다:
public mutating func removeValue(forKey key: Key) -> Value? {
let index = self.index(forKey: key)
// 버킷의 체인에서 요소를 찾아 제거
for (i, element) in buckets[index].enumerated() {
if element.key == key {
buckets[index].remove(at: i)
count -= 1
return element.value
}
}
return nil // 키가 해시 테이블에 없음
}이것이 해시 테이블의 기본 기능이다. 이 모든 기능은 같은 방식으로 동작한다: 키를 해시 값으로 배열 인덱스로 변환하고, 버킷을 찾은 다음, 해당 버킷의 체인을 순회하며 원하는 작업을 수행한다.
이 코드를 플레이그라운드에서 테스트해 보자. Swift의 표준 Dictionary처럼 동작할 것이다.
현재 HashTable은 항상 고정된 크기 또는 용량의 배열을 사용한다. 해시 테이블에 저장할 항목이 많은 경우, 용량은 항목의 최대 수보다 큰 소수를 선택한다.
해시 테이블의 로드 팩터는 현재 사용 중인 용량의 비율을 나타낸다. 해시 테이블에 5개의 버킷이 있고 3개의 항목이 저장되어 있다면, 로드 팩터는 3/5 = 60%가 된다.
해시 테이블이 작고 체인이 길면 로드 팩터가 1을 초과할 수 있다. 이는 바람직하지 않다.
로드 팩터가 75%를 초과하면 해시 테이블의 크기를 조정할 수 있다. 이 조건을 처리하는 코드를 추가하는 것은 독자의 연습문제로 남긴다. 버킷 배열의 크기를 늘리면 키가 매핑되는 배열 인덱스가 바뀐다는 점을 명심하자. 배열 크기를 조정한 후에는 모든 요소를 다시 삽입해야 한다.
HashTable은 상당히 기본적인 구조다. 이를 Swift 표준 라이브러리와 통합하려면 SequenceType으로 만드는 것이 효율적일 수 있다.
Swift 알고리즘 클럽을 위해 Matthijs Hollemans가 작성함