Swift) 해시 테이블(Hash Table) 이해하기

 

 

 

안녕하세요 :) 소들입니다!

오늘은 자료구조 중에서 해시 테이블이란 것에 대해 공부해보려고 해요!!!

음..... 사실 Swift에서 굳이 해시 테이블을 직접 구현해서 쓸 일은 거의 없다고 생각해요..

왜냐면 대표적으로 해시로 동작하는 딕셔너리를 사용하면 되거든요! (다다음쯤 포스팅할 예정)

 

그치만! 모든 걸 상위 레벨에서 제공해준다고 해도,

내부 구성이 어떻게 되어 있고, 직접 한번 구현해보는 것도 좋은 것 같아요! 🙃

물론 조금 어려울 수 있고 난해하겠지만.. 생각보다 어렵지 않아요 :ㅇ

 

Swift로 된 코드가 잘 없어서 제가 짜보는 만큼..!

틀릴 수도 있고, 의아한 부분이 있을 수도 있으니, 그런부분을 발견 시 언제든 댓글을 남겨주세요!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 해시 테이블이란?

 

자, 해시 테이블을 공부하기 위해선 먼저 딕셔너리를 생각해보셈

딕셔너리는 Key - Value로 값을 저장하기 때문에,

특정 Key를 던져주면, 그 키에 해당하는 Value가 나오는 형태잖음?

 

딕셔너리가 해시 테이블로 구현되어 있기 때문에,

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

 

근데 그거 아셈??

해시 테이블은 내부적으론 배열로 구현이 되어 있음!!

 

무슨 말이냐면,  우리가 특정 Key - Value를 저장한다고 하면

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

결과 값인 해시 주소 값에 해당하는 해시 테이블 슬롯에 Value를 저장하는 것임!

 

..? 

이렇게 말하면 이해 0.1도 안 갈 거 알고 쓴거임 ㅎㅎ

포기하지 마셈!!! 예제로 보면 쉬움 :)

 

 

만약 다음과 같이 세 개의 Key-Value를 내가 해시 테이블에 저장하려 함

(만약 해시 테이블이 생소하면 딕셔너리로 생각하셈)

 

 

 

 

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

해시 테이블은 데이터가 다음과 같이 순서를 지키지 않고 저장됨

(어떤 방식으로 저장되는지는 바로 뒤에 나오니 일단 결과만 놓고 보자:))

 

 

 

 

해시 테이블에 만약 위와 같이 저장되었다고 했을 때,

우린 "유"라는 Key로 1번 index에 있는 "재석" 값을 얻어옴

마찬가지로 "박"이라는 Key로 0번 index에 있는 "명수" 값을 얻어옴

자, 상식적으로 생각을 해보면 됨

 

우린 오로지 "Key"만 갖고 해시 테이블에 저장된 "값"에 접근해야 함

근데 해시 테이블은 내부적으로 배열로 구성이 되어 있네??

어?? 배열에선 "값"에 접근하려면 index로만 접근할 수 있는데???

아하! 그럼 Key를 통해 해시 테이블의 index를 알 수 있어야만, 해당 Value에 접근이 가능하겠구나!!

 

까지 생각을 해볼 수 있다면 아주아주 잘한 것임!

우린 Value가 저장된 해시 테이블의 index를 모르니까, Key를 통해 index를 알아내야 하는 것임!

이때 해당 Key에 상응하는 index는 항상 동일하게 나와야 꼬이지 않잖음??

 

이것을 해주는 것이 바로 해시 함수 라는 것임!

Key에 대한 산술 연산을 이용하여 해시 주소값(해시 테이블의 index)으로 만들어주는 것!

 

 

 

 

오호!!!!! 이제 원리는 풀렸군.. 해시 테이블이란 것은,

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

해시 주소값(해시 테이블의 index)를 통해 해시 테이블에 접근하여 값을 가져오거나 저장하는 형태임

 

이해가 됐길..!

 

 

 

 

2. 간단한 해시 테이블 구현해보기

 

이번엔 Swift로 간단한 해시 테이블 만들기를 해볼 것임 :)

 

 

 

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
}

 

 

먼저 이해가 안갈 거 같은 부분부터 보겠음

함수의 첫 줄 guard문에서 UnicodeScalar부분이 이해가 안 갈 것 같은데,

우리가 만든 hash 함수는 해시 주소값, 즉 index를 만드는 정수형이기 때문에

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

(만약 Key를 Int형으로 했을 경우엔 위 과정 생략했겠지만)

 

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

해시 주소값에 해당하는 슬롯에 Value를 Upsert 해준 것임!

(비었으면 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]
}

 

 

이렇게 해주면 되겠군 :)

어렵지 않져!!!!!!!!!!!!!!!!!!!1

 

 

 

자, 이제 실제로 위와 같이 만든 사용해보겠음

 

 

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

 

 

이렇게 Key-Value 저장도 잘 되고 :)

 

 

 

 

Key를 통해 Value를 가져오는 것도 잘 됨 :)

자, 근데 이렇게만 하면 완벽해보이지만 문제가 있음!!

 

 

 

 

3. 해시 테이블의 충돌

 

해시 테이블의 가장 큰 문제점은 바로 "충돌" 이라는 것임

우리가 위에서 "유", "박", "김"이라는 Key를 해시할 땐 아무 문제가 없었으나

 

만약, "유" 와 "이" 라는 Key를 해시해보면,

 

 

 

 

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

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

만약 이 경우, Key - Value가 덮어씌어지는 충돌 현상이 발생함..!

 

따라서 해시 테이블의 충돌을 해결하기 위해

가장 대표적인 두 가지 알고리즘을 봐보겠음

 

 

 

3-1. Chaining 기법

 

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

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

 

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

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

 

 

 

 

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

Value 값을 식별하기 위해 Key 값도 같이 저장됨

 

우린 이전 포스팅에서 연결 리스트를 배웠으니 어렵지 않을 거라 생각함:)

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

Chaining 기법임!

 

Swift 코드로 짜도 어렵지 않은데.. 지금은 시간이 없..

만약 추후 누군가 원한다면 짜서 올려놓겠음

 

 

 

3-2. Linear Probing 기법

 

폐쇄 해싱 또는 Close Hashing이라고 부름!

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

 

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

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

이 또한 Key - Value를 같이 저장함

 

 

 

 

이것이 Linear Probing 기법!

이또한 아마 없을듯 하지만 (누군가) 코드를 원한다면 나중에 추가 하겠음

 

 

 

 

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

 

자, 이번엔 해시 테이블의 시간 복잡도를 보겠음

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

 

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

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

해시 테이블의 시간 복잡도는

 

O(1)

 

임! 배열에 비해 매우 빠른 것!

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

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

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

 

 

 

 

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

 

장점	단점
- 데이터 저장/읽기 속도가 빠르다 - 키에 대한 데이터의 중복 확인이 쉽다	- 일반적으로 저장 공간이 많이 필요하다 (충돌 문제를 해결하기 위해 저장공간을 넓게 잡음) - 충돌이 발생 시 해결하기 위한 별도의 자료구조가 필요하다

 

 

이런 장단점이 있는데, 보통 해시 테이블을

시간 복잡도와 공간 복잡도를 맞바꿨다..!! 라고 표현함

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

 

따라서,

 

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

캐쉬를 구현할 때 사용하면 좋다 함:)

 

 

 

 

.

.

.

.

 

오늘은 해시 이해하기 끝 :))

틀렸거나 어렵거나 피드백할 내용 있으며 언제든 댓글 주세요~~~

그럼 20,000~

 

 

 

전체 코드는

 

github.com/sossam/SwiftHashTable

sossam/SwiftHashTable

 

여기서!