Hash Table

1. 해시 테이블이란?

Key - Value로 값을 저장하는 딕셔너리는 해시 테이블로 구현되어 있다.

해시 테이블도 당연히 Key - Value로 값을 저장한다.

해시 테이블은 내부적으로는 배열로 구현되어 있다.

특정 Key - Value를 저장한다고 하면

해당 Key를 해시함수를 통해 해시를 하고,

겺과값인 해시 주소값에 해당하는 해시 테이블 슬롯에 Value를 저장한다는 의미이다.

예를들어 세개의 Key - Value를 해시 테이블에 저장하려고 한다고 하자

만약 순서대로 0, 1, 2에 저장이 된다면 이것은 일반 배열이지 해시 테이블이 아니다.

해시 테이블은 아래 처럼 순서를 지키지 않고 저장된다.

Key만 가지고 해시테이블에 저장된 값에 접근해야 한다.

하지만 해시 테이블은 내부적으로 배열로 구성되어 있기 때문에 index로만 접근이 가능하다.

그렇다면 Key를 통해서 해시 테이블의 index를 알 수 있어야만 해당 Value에 접근이 가능한 것이다.

이것을 가능하게 해주는 것이 해시 함수 이다.

해시 테이블이라는 것은 Key라는 것을 해시 함수를 이용해서 해시 주소값(해시 테이블의 index)으로 바꾸고,

해시 주소값(해시 테이블의 index)를 통해서 해시 테이블에 접근하여 값을 가져오거나 저장하는 형태라는 것을 알 수 있다.

2. 해시 테이블 구현

2-1 해시 테이블 만들기

해시 테이블은 배열로 이루어져 있으니 다음처럼 배열로 만들어보자

var hashTable: [String?] = .init(repeating: nil, count: 3)

Swift는 타입에 민감하기 때문에 Value의 타입을 String으로 지정하고,

딕셔너리의 경우 값이 없으면 nil을 리턴하니까 nil로 초기화된 4개의 슬롯을 가지는 해시 테이블이 생성된다.

2-2 해시 함수 만들기

해시 함수는 보통 SHA256이나 SHA-1 같이 안전한 알고리즘을 채택 한다.

하지만 직접 구현하기에는 어려우므로 해시 테이블의 0, 1, 2이란 해시 주소값 (index)를 갖는 함수를 구현해보자

func hash(key: Int) -> Int {
    return key % 3
}

2-3 해시 테이블에 저장하는 함수 만들기

해시 테이블에 저장해기 위하여 Key - Value쌍을 받아야 하고, 이 값을 해시 테이블에 저장하면 된다.

func updateValue(_ value: String, forKey key: String) {
    guard let key = UnicodeScalar(key)?.value else { return }
    let hashAddress = hash(key: Int(key))
    hashTable[hashAddress] = value
}

2-2에서 만든 해시 함수는 해시 주소값, 즉 index를 만드는 정수형이기 때문에

String을 Int로 바꿔야 해서 하나의 예시로 Unicode를 이용해 Int형으로 만들어준 것이다.

(만약 Key를 Int형으로 했을 경우엔 위 과정 생략가능하다.)

따라서 Key를 해시 함수에 넣어 해시 주소값(index)를 얻고,

해시 주소값에 해당하는 슬롯에 Value를 Upset해준 것이다.

(비어있으면 insert, 이미 존재한다면 update될 것이다.)

2-4 해시 테이블의 값을 얻는 함수 만들기

해시 테이블의 값을 얻기 위해서는 Key가 필요하다.

func getValue(forKey key: String) -> String? {
    guard let key = UnicodeScalar(key)?.value else { return nil }
    let hashAddress = hash(key: Int(key))
    return hashTable[hashAddress]
}

updateValue("재석", forKey: "유")
updateValue("명수", forKey: "박")
updateValue("소들", forKey: "김")

getValue(forKey: "유") // 재석
getValue(forKey: "박") // 명수
getValue(forKey: "김") // 소들

위 처럼 저장도 잘되고 Key를 통하여 Value를 얻는것에도 문제가 없다.

하지만 여기에도 문제가 있다.

3. 해시 테이블의 충돌

해시 테이블의 가장 큰 문제점은 충돌이다.

위 예시에서 "유", "박", "김"이라는 Key를 해시할 때는 문제가 없으나

"유", "이"라는 Key를 해시하면

둘 다 해시 주소값(index)가 0으로 동일하게 나온다.

(Key는 다르지만 해시 함수가 단순해서 결과값인 해시 주소값이 겹치는 문제)

이런 경우 충둘현상이 발생한다.

따라서 해시 테이블의 충돌을 해결하기 위한 두 가지 알고리즘을 살펴보자

3-1 Chaining 기법

개방 해싱 또는 Open Hashing이라고 부르는데,

해시 테이블 저장 공간 외의 공간을 활용하는 방법이다.

충돌이 일어날 경우, 연결 리스트(Linked List)를 이용하여

데이터를 추가로 뒤에 연결 시켜서 저장하는 기법을 말한다.

하나의 해시 주소값에 2개 이상의 Value가 연결 리스트로 이어져 있기 때문에,

Value 값을 식별하기 위해 Key값도 같이 저장된다.

이렇게 연결 리스트를 이용해서 해시 테이블 외의 저장 공간을 활용하는 것이 Chaining 기법이다.

3-2 Linear Probing 기법

폐쇄 해싱 또는 Close Hashing이라고 부른다.

해시 테이블 저장 공간 안에서 충돌 문제를 해결하는 방법이다.

충돌이 일어날 경우, 해당 해쉬 주소값(index부터) 순회하며

가장 처음 나오는 빈 공간에 저장하는 기법이다. (저장 공간의 활용도를 높임)

이 또한 Key - Value를 같이 저장한다.

4. 해시 테이블의 시간 복잡도

해시 테이블은 배열로 구성되어 있지만,

원하는 값을 찾기 위해 0번 index부터 순회해야 하는 배열의 O(n)과 달리,

Key 값을 해시하여 바로 Index에 접근하기 때문에

해시 테이블의 시간 복잡도는 O(1)

(배열에 비해 빠르다는 것을 의미한다.)

다만, 이는 일반적인 경우이고

최악의 경우, 모든 충돌이 다 발생한 경우 배열처럼 O(n)이지만,

해시 테이블은 일반적인 경우를 생각하고 만들기 때문에 O(1)이라고 말할 수 있겠다.

5. 해시 테이블의 장단점 및 용도

보통 해시 테이블을 시간 복잡도와 공간 복잡도를 맞바꿨다. 라고 표현한다.

빠른 속도를 자랑하지만, 그만큼 저장 공간이 낭비되기 때문이다.

따라서,

저장, 검색, 삭제 등 탐색을 많이 하는 경우나

캐쉬를 구현할 때 사용하면 좋다.

참고자료

https://babbab2.tistory.com/89