안녕하세요.
이번 글은 자료구조 중 하나인 Hash Table에 대해 알아보고 정리한 글입니다.
Hash Table
해시 테이블은 Key를 통해 Value를 저장 및 읽어올 수 있는 자료구조이다.
Swift에서는 딕셔너리가 Key - Value 쌍으로 값을 저장할 수 있는 타입인데 이는 딕셔너리가 해시 테이블을 기반으로 구현된 컬랙션 타입이기 때문이다.
해시 테이블의 대표적인 특징으론 Key를 통해 Value를 읽어올 때 시간복잡도가 O(1)이다.
(하지만, 최악의 경우는 O(n)이다. 이유는 아래에서)
해시 테이블은 값을 저장하기 위해 내부적으로 배열을 사용한다. 그럼 어떻게 Key를 통해 저장하냐?
Key 값을 해시 함수를 통해 고유한 정수 값으로 변환하고, 해당 값을 Index로 사용해 배열에 저장하는 방식이다.
그럼 직접 구현해보며, 하나씩 뜯어보자!!
해시 함수
해시 함수는 앞써 언급한대로 Key 값을 고유한 정수 값으로 변환해주는 역할을 한다.
일반적으론, SHA256와 같은 알고리즘 등을 이용해 안전하면서 고유한 값으로 변환하는 것이 맞지만, 간단하게 구현하기 위해 아래와 같이 Hashable의 hashValue를 절대값으로 만들고, Table의 크기만큼 나머지 연산을 통해 정수값을 가져올 수 있도록 했다.
(참고로, hashValue의 경우 빌드할 때 마다 값이 달라진다.)
let TABLE_SIZE = 4
struct HashTable<Key: Hashable, Value> {
typealias Element = (key: Key, value: Value)
init() {
self._buckets = Array(repeating: [], count: TABLE_SIZE)
}
func hashFunction(for key: Key) -> Int { <--
return abs(key.hashValue) % TABLE_SIZE
}
}사파리, 홍길동, 캡틴을 해시 함수를 통해 다음과 같이 실행해보면,
print("Key 값이 사파리 일 때 결과값: ", table.hashFunction(for: "사파리"))
print("Key 값이 홍길동 일 때 결과값: ", table.hashFunction(for: "홍길동"))
print("Key 값이 캡틴 일 때 결과값: ", table.hashFunction(for: "캡틴"))
- 사파리는 배열의 3번 자리에 저장
- 홍길동는 배열의 1번 자리에 저장
- 캡틴는 배열의 0번 자리에 저장
이 처럼, 해시 함수를 통해 Key -> Index로 변환 시켜 저장 및 읽기가 가능해지며, 이 때 시간 복잡도는 O(1)되게 된다.
해시 테이블의 충돌
위 예시에선 운이 좋게 각 다른 자리에 저장되었지만, 특정 Key 값은 해시 함수를 통해 변환했을 때 동일한 정수 값을 가질 수도 있다.
예를들어, 이번엔 나비, 고양이, 강아지를 해시 함수를 통해 변환해 보면,
위와 같이 나비와 강아지가 같은 Index 값을 가진다. 이 처럼 동일한 자리에 저장될 수 밖에 없는 경우를 해시 테이블 충돌이라고 한다.
충돌을 해결하기 위한 대표적인 방법으로 Chaining과 Linear Probing이 있다.
Chaining
Chaining(또는 Open Hashing)은 충돌이 발생했을 때 연결 리스트를 사용해 해당 Index에 추가로 데이터를 저장시키는 방법이다.
위 이미지 처럼 21, 14, 7이 동일한 Index를 가진다면, 한 Index에 연결 리스트를 활용해 줄줄이 데이터를 저장한다.
읽어올 땐 Value와 함께 저장된 Key값을 읽고 싶은 Key값과 앞에서 부터 순차적으로 비교하며 탐색한다.
Linear Probing
Linear Probing(또는 Close Hashing)은 충돌이 발생했을 때 해당 Index의 다음 Index에 값을 저장한다.
위 이미지 처럼 이미 3에 값이 존재 한다면, 3에 저장하는 것이 아닌 그 다음 Index 즉, 4에 저장한다.
읽어올 땐 3에 저장된 Key값과 읽어올 값을 Key 값을 비교 후 만약 틀리다면, 다음 인덱스의 Key 값을 비교하며 원하는 Value 값을 찾는다.
근데 Linear Probing의 경우 값이 삭제됐을 때 문제가 될 수 있다.
예를들어, 만약 'delete'라는 Key 값을 가진 Value를 제거하면, 'int'라는 값을 찾을 때 3 Index가 비어있기 때문에 정상적으로 탐색할 수 없다.
때문에 삭제되었음을 표시해줘야 한다.
충돌 시 시간 복잡도
앞써 해쉬 테이블의 저장 및 읽기에 대한 시간 복잡도가 O(1)된다고 언급했다. 하지만 이는 출동 없이 모든 값이 이상적으로 저장될 때의 시간 복잡도이다.
반대로 모든 데이터가 출동이 발생하는 최악의 경우엔 O(n)이 될 수 있다.
구현 코드
/// size가 커질 수록
/// 공간복잡도는 up
/// 충돌 가능성은 down
let TABLE_SIZE = 4
struct HashTable<Key: Hashable, Value> {
typealias Element = (key: Key, value: Value)
/// Chaining을 위해 연결 리스트 대신 2중 배열 사용
private var _buckets: [[Element]]
private(set) var count: Int = 0
init() {
self._buckets = Array(repeating: [], count: TABLE_SIZE)
}
subscript(key: Key) -> Value? {
get {
get(key)
} set {
if let newValue = newValue {
set(newValue, for: key)
} else {
remove(key)
}
}
}
func hashFunction(for key: Key) -> Int {
return abs(key.hashValue) % TABLE_SIZE
}
mutating func set(_ value: Value, for key: Key) {
let i = hashFunction(for: key)
if let index = _buckets[i].firstIndex(where: { $0.key == key }) {
_buckets[i][index].value = value
return
}
_buckets[i].append((key, value))
count += 1
}
func get(_ key: Key) -> Value? {
let i = hashFunction(for: key)
return _buckets[i].first(where: { $0.key == key })?.value
}
@discardableResult
mutating func remove(_ key: Key) -> Value? {
let i = hashFunction(for: key)
guard let elementIndex = _buckets[i].firstIndex(where: { $0.key == key }) else { return nil }
return _buckets[i].remove(at: elementIndex).value
}
}