Hashing (Dictionary의 키는 왜 Hashable 타입인가요?)

이번글의 목표

Dictionary의 키는 왜 Hashable 타입인가요?

• 왜 Dictionary/Set의 탐색은 O(1)인가?
• 왜 Dictionary 탐색의 최악의 경우는 O(n)인가?
• Hashable의 hashValue는 왜 Int 인가?
• Hashing을 왜 하는가?
• 좋은 해싱 알고리즘이 필요한 이유는?

https://soojin.ro/blog/hashable

 

이번 글의 목표는 위의 질문들에 답변하는 것이 목표입니다. 바로 답을 하진 않을거고, Hashing에 대해서 쭉 살펴본 후에 Swift에서의 hash table 충돌 해결방법을 알아보고, 해당 방법으로 직접 Dictionary를 구현해본 후에 질문에 답을 해보도록 하겠습니다! 레츠고

 

만약 답변만 보고싶으시다 하시면 쭈욱 내려가서 맨 아래쪽 '답변타임'만 확인해주시면 될 것 같습니다 !!!!!

 

---

Hashing

딕셔너리랑 Set을 써봤다면 이미 우리는 hashing을 사용하고 있는 것입니다.

Hash의 마법을 느끼기 위해서 우선 딕셔너리를 예시로 딕셔너리 구현하는 방법별 삽입, 검색, 삭제에 대한 시간복잡도를 먼저 알아봅시다.

Dictionary구현	삽입	검색	삭제
BST	O(log n)	O(log n)	O(log n)
Unsorted	O(1)	O(n)	O(n)
Sorted	O(n)	O(log n) : 이분탐색	O(n)
Hash	O(1)	O(1)	O(1)

 

모든것이 O(1)로 가능한 Hash의 마법을 한번 알아보겠습니다.

---

Hashing

키가 K인 아이템을 상수 시간에 찾을 수 있을까? 🤔
가능하다. Hash와 함께라면 !

 

Hash의 구성요소를 먼저 살펴봅시다.

• Hashing의 구성요소
  • Hash Table (HT): 아이템을 담는 배열. 크기가 M.
  • Hash Function (h): 키 K를 0 ~ M-1의 값으로 매핑하는 함수
    • 예시) h(K) = K % M
    • 예시일뿐. hash function은 여러가지가 있습니다.
  • Hashing은 키가 K인 아이템을 HT[h(K)]에 넣습니다.
    • 찾을 때도 HT[h(K)]에서 찾습니다.

Hashing 언제 쓸 수 있을까?

• Hashing은 키의 개수에 비해서 키의 범위가 클 때 유용합니다.

예를 들어 <Key: Int, Value: Int>인 값을 저장하고자 할 때 키의 개수가 3개라고 해봅시다.

 

<10, x>, <240, y>, <100000, z>

 

이렇게 3개가 있다고 했을 때 만약 배열로 딕셔너리를 만든다고 했을 때는 배열의 크기가 적어도 10만은 되어야 저장할 수 있을테고 낭비되는 공간이 너무 많습니다. 이런 경우에 Hash만큼 적절한 것이 없습니다.

M개의 키가 0부터 M-1까지 순차적으로 있다면?

 

이런 상황은 그냥 배열을 쓰면 됩니다. 알다시피 배열은 연속적인 수를 다루는데에 있어서 더할나위없이 좋죠.

M개의 키가 X부터 X+M-1까지 순차적으로 있다면?

 

이건 X를 뺀다면 사실상 0부터 M-1까지 이기에 똑같이 배열을 쓰기 좋은 상황입니다.

M개의 키가 0부터 N (M << N)사이에 듬성듬성 있다면?

 

키의 개수보다 N, 즉 수의 범위가 압도적으로 큰 상황입니다. 이는 첫번째로 우리가 살펴봤던 상황이고, 이럴 때 Hash를 사용하면 유용합니다.

키가 문자열이라면?

 

문자열도 사실상 듬성듬성 있다고 볼 수 있습니다. abcdefg…이렇게 나열되어있는 문자열 set에서 듬성듬성 가져와 이를 조합해서 만들어진 것이기 때문입니다. 위의 상황과 비슷한 상황이기에 Hash가 또 유용합니다.

Collision

하지만 Hash도 모든 것이 완벽한 것만은 아닙니다..

 

한번 예를 들어보겠습니다.

 

10의 크기를 가진 hash table이 있고, hash function은 h(x) = x % 10이라고 해봅시다.

이 때 2개의 Int타입의 키가 있는데 키는 각각 25, 35라고 한다면 두 키에 대한 h(K)의 결과값은 모두 5로 동일합니다. 이렇게 되면 어떻게 될까요 ??

 

hash table의 5번 인덱스에 있는 값이 덮어씌워지게 되면서 이전의 값이 날라가게 됩니다.

즉, 이렇게 서로 다른 키 값이 같은 해시값을 공유하는 상황을 hash collision, 해시 충돌이라고 부릅니다.

h(k1) == h(k2)

Hash Functions

충돌을 해결하는 방법에 대해 알기 이전에 hash function에 대해서 먼저 살펴보고 넘어갑시다.

 

일단 어떤 hash function이 좋은 hash function일까 ?? 🤔

 

우선 앞서 충돌 상황을 봤습니다. 충돌 확률이 적은 hash function이 좋은 hash function이 되지 않을까요 ?

충돌을 해결할 필요없이 해시값에 따라 충돌없이 바로바로 값을 넣을 수 있기 때문이죠. (찾을 때도 한번에 찾을 수 있고)

 

충돌이 가장 최소로 발생하는 함수, hash function, 즉 들어오는 데이터에 상관 없이 모든 slot에 고르게 할당하는 함수가 좋은 hash function이라고 할 수 있습니다.

 

한가지 더 예시를 들어보겠습니다.

hash table의 크기 M이 16이고, hash function이 h(K) = K % 16이라면, h(K)는 좋은 hash function일까요 ??

• 만일 키가 모두 짝수라면?

키가 모두 짝수라면 해시값 또한 모두 짝수만 나오게 됩니다. 따라서 충돌이 많이 생기게 될 것이고 테이블의 공간을 절반만 활용하고 있는 상황이기에 안좋은 hash function이라고 할 수 있습니다.

• 만일 키의 하위 4개 bit(2^4=16)가 모두 동일하다면??

00110100 | 0000

 

이런 경우에 해당하는 모든 경우에서 0으로 갈 것이기에 좋은 hash function이 아닙니다.

사실 % 16이라는 것 자체가 2진수의 bit로 표현된 곳에서 뒤에 4bit만 보고 앞은 모두 무시하겠다는 말과 동일합니다.

• 10100111010 1101

이는 데이터의 극히 일부만 보기 때문에 생기는 문제라고 말할 수 있습니다.

 

여기서 키의 모든 비트를 사용하는 방향으로 가는 해결방법들이 나옵니다.

1. Mid-square method

key를 제곱한 후에 가운데 r개의 비트를 M(테이블의 크기)으로 나눈 나머지를 구한다.

		00110101 10100111
x		00110101 10100111
----------------------------------
000010110011**11101001**001011110001

 

가운데에서 r비트를 뽑아 쓰는 이유는 맨 앞과 맨 뒤보다 가운데 부분이 수가 가장 많이 섞여있는 부분이기 때문입니다.

 

가운데 r비트가 hash table의 크기인 M과 맞지 않을 것이기 때문에 여기서 % M 연산을 통해 테이블 사이즈에 맞춰주는 작업까지 해주고 해당 인덱스에 값을 넣는 방법입니다.

2. Folding approach

t개씩 비트를 잘라서 합한 후 M으로 나눈 나머지를 구한다.

이런 방법으로도 모든 비트가 다 사용되게끔 할 수 있습니다.

(K * 소수) % 소수

K * 소수를 하게 되면 비트들이 불규칙적으로 퍼지게 될 것이고, 이를 또 다른 소수로 모듈러 연산을 해주게 되면 해시 테이블의 모든 영역에 고르게 퍼지게 되는 효과가 생깁니다.

Collision Resolution

보통 키의 범위가 slot의 수 보다 많기 때문에 Collision자체는 피하기 힘듭니다.

(비둘기 집의 원리(Pigeonhole principle), 생일 문제(Birthday paradox))

 

“비둘기 집의 원리”라는 굉장히 거창해 보이는 원리가 나왔지만 사실 별거 아닙니다.

 

위 그림처럼 비둘기의 집이 M개 있고, 비둘기가 M+1마리가 있고, 비둘기들도 한마리씩 살고싶어한다고 합니다.

그럼 당연히 비둘기가 집의 개수보다 한마리가 더 많기 때문에, 집의 공간이 부족하겠죠?

그럼 우리는 이 때 “아 어딘가의 한 공간에는 비둘기가 2마리 있겠구나”라고 말할 수 있습니다.

 

이를 그대로 해시 테이블에 적용해보면 M의 크기를 가진 해시 테이블에, M+1개의 Key들이 있다고 한다면 “아 collision이 적어도 한번 이상은 있겠구나”라고 생각할 수 있을 겁니다.

 

“생일 문제(Birthday paradox)”는 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제입니다.

이는 사람이 Key고, h(사람) = 생일 인 hash function을, 그리고 365 크기의 hash table을 만든 것과 같은 상황입니다.

 

충돌은 피하기 힘들다는 것을 인정해야합니다. 그렇다면 이제 우리가 찾아봐야할 것은 '충돌을 어떻게 해결해야할까?' 입니다.

충돌 해결 방법 (Collision Resolutions)

1. Open hashing (seperate chaining)

“Hash Table + a 로 메모리공간을 더 쓴다.”라는 의미에서 open.

메모리 공간을 더 쓴다는 게 어떤 의미인지 알아보겠습니다.

 

Hash table의 각 각의 slot에 Linked List를 연결해서 삽입시에 Collision이 발생하면 해당 slot의 Linked List에 추가합니다.

Linked List에서 충돌 발생시 Node가 추가되기에 메모리 공간을 더 활용하게 됩니다.

💡 LinkedList가 아닌 Array도 괜찮지 않을까 ?
오히려 더 좋을 수도? 하지만 Array도 어느 순간에 가득차게 되면 Doubling등의 기법을 통해 공간을 늘려야하기 때문에 메모리 공간을 추가적으로 더 활용하게 된다는 점에서는 동일.

추가적으로 Ddos공격과 같은 단점이 존재한다고 합니다.

Hash DoS 공격

Hash DoS 공격

2. Closed hashing (open addressing, 주소개방법)

“Hash Table 안에서 다 처리한다”라는 의미에서 closed.

 

주소개방법, open addressing의 의미는 뭘까

“남의 주소를 내가 쓸 수 있다”라는 의미를 가지고 있습니다.

우리집에 내가 살 수 없으면 남의 집에 사는 겁니다 (이게 무슨,,) 말그대로 주소를 개방하는 것입니다.

 

이를 해시 상황으로 정리하면 아래와 같습니다.

 

“삽입시 Collision이 발생하면 hash table의 다른 slot에 아이템을 저장한다”

 

이것을 위한 여러 기법들 중 몇가지를 살펴보겠습니다.

2-1. Bucket Hashing

Bucket hashing은 hash table을 여러개의 Bucket으로 그룹화를 하는 것 입니다.

위의 사진에서는 10개 사이즈의 hash table을 5개의 Bucket으로 그룹화를 하였습니다.

• 각 Bucket는 하나의 인덱스를 가지고 안에는 두가지의 키를 보관할 수 있습니다.
• 키들을 해시값으로 얻은 인덱스를 통해서 알맞은 Bucket에 보관합니다.
• 만약 Bucket이 가득 차있다면 Overflow 배열에 넣습니다.
• Overflow배열은 모든 Bucket이 공유하는 배열입니다.

예시 그림에서 빨간색으로 표시된 1057은 h(1057) = 2라는 해시값을 얻게 됩니다.

2번 Bucket에 1057 키를 넣을려고 하니 가득차있기에 Overflow배열에 넣습니다.

그렇다면 1057키를 찾을 때는 어떻게 할까요 ?

 

똑같이 hash function을 통해서 2라는 값을 얻겠죠. 그 후에 2번 Bucket에서 하나씩 확인하면서 1057를 찾습니다. Bucket에 있다면 리턴되겠지만 현재 Bucket에서 보이지 않네요. 그럼 이제 Overflow배열을 확인하러 갑니다. 오버플로우 배열을 하나씩 돌면서 확인하고 1057을 찾습니다.

 

이 방법의 단점으로는 사용할 수 있는 공간은 10만큼 있지만, 주소는 5개뿐입니다.

주소가 작다는 것은 그 만큼 Collision이 발생할 확률이 늘어남을 말합니다.

 

그래서 각각의 칸에도 주소를 모두 풀어버리는 변형 방법이 존재합니다.

 

주소는 모두 풀되 Bucket단위로 묶여있는 것은 동일합니다.

 

예시를 보면 9877을 h(9877) = 9877 % 10 = 7이기에 7번 인덱스로 키가 들어갑니다.

그 후에 2007도 똑같이 해시값이 7이기에 충돌이 생깁니다. 이 때는 Bucket의 빈공간으로 들아가서 위에 그림 처럼 됩니다.

이 예시는 Bucket안에 공간이 두 개 뿐이여서 좀 더 자세한 이해를 위해 버켓의 공간을 4칸으로 늘려보겠습니다.

 

9877을 넣고 2007을 넣으려고 할 때, 다음칸을 먼저 살핍니다. 하지만 다음칸은 버켓의 경계를 벗어나기 때문에 갈 수 없습니다.

 

따라서 마치 Circular처럼 돌아서 맨 첫번째 칸에 2007을 넣습니다. 이제 다음 삽입하고 싶은 키 값은 3007이라고 가정해봅시다.

 

3007도 마찬가지로 해시값이 7이기 때문에 (h(K) = K % 10) 9877부터 순환해서 다음, 다음으로 넘어가면서 빈칸을 찾습니다. 그림과 같이 2007다음 빈칸에 들어갑니다.

 

이제 다음 키값은 4007입니다.

 

4007도 3007을 넣었을 때와 마찬가지로 동작하고 빈칸을 찾아 들어갑니다. 이 후 해시값이 7인 5007을 넣을려고 합니다.

 

하지만 버켓에 더 이상의 공간이 없기 때문에 그제서야 5007은 Overflow배열에 저장됩니다.

---

Bucket hashing vs open hashing(chaining)

• Bucket hashing이 주소를 더 적게 쓰기 때문에 충돌이 open hashing보다 더 잦습니다. → 탐색 시간이 더 길어질 수 있습니다.
• 하지만 Bucket hashing은 추가 공간을 덜 차지한다는 상대적인 장점이 있습니다.

Bucket hashing의 한계

hash table에 비어있는 다른 공간들이 많음에도 bucket이 가득차면 overflow배열에 값을 넣게 된다는 점이 일단 비효율적입니다.

3. Linear Probing

가장 많이 쓰이는 충돌 해결 기법 !

• linear: 선형의
• probe: 탐사하다

즉, 선형 탐색하는 것을 의미합니다. Bucket없이 closed hashing하면 됩니다. 즉, Bucket처럼 모든 경계 없이 공간이 차있으면 그냥 선형으로 빈공간을 탐색해서 다음 빈공간에 값을 넣습니다. 쉽고 간단한 아이디어입니다.

 

일단 overflow가 필요가 없습니다. 만약에 hash table이 정말 가득 다 찬다면, doubling처럼 공간을 늘린 후에 값을 다시 넣어주는 식으로 동작합니다.

Linear probing의 문제점

Primary clustering

값들이 점점 뭉치게 됩니다.

이게 무슨 뜻이냐면 애초에 아이디어 자체가 값을 넣으려고 할 때 이미 해당 인덱스에 갑이 있다면 (Collision발생) 다음으로 첫번째로 발견되는 빈공간에 값을 넣기 때문에 값들이 서로서로 뭉쳐져서 공간을 매꾸게 됩니다.

이렇게 값이 뭉쳐있게 된다면 우리가 의도치 않아도 어떤 값을 새로 넣을 때 뭉쳐져있는 값만큼 Collision이 발생하고 그 cluster되어 있는 값의 묶음을 모두 지나가야지만 빈공간을 찾을 수 있게 되겠죠. 이것이 성능을 상당히 저하시키게 됩니다.

개선방법 모색

한칸씩 띄어가면서 빈공간을 찾는게 문제 아닌가요 ?

1. 상수배 만큼 곱한만큼의 공간을 띄어가면서 공간을 찾아 보자

근데 cluster가 안생길까? 눈에만 안그래보일 뿐이지 어차피 곱해진만큼의 공간을 띄어가면서 빈공간을 찾는 건 동일하기 때문에 clustering효과는 여전합니다.

2. Pseudo-random probing

미리 몇칸씩 띄울지 정하고 시작하자.

근데 몇칸씩 띄울지에 대한 정보를 1~M-1사이의 값을 섞어서 가지고 있는 배열에 담아놓고 거기 값대로 띄우자 !

[3, 4, 7, 1, 6, 8, 2, 9, 5] // 몇 칸 띄울지에 대한 정보를 담은 배열

 

M이 10이고 1부터 9까지의 값을 섞어서 위와 같이 가지고 있으면, 값을 넣을려고 할 때 Collision이 발생한다? 그러면 해당 배열에서 첫번째 값인 3 만큼 공간을 띄고, 만약 거기서 또 Collision이 발생할 때에는 3 다음 값인 4만큼의 공간을 띄우고 공간을 찾는식으로 반복하는 것입니다.

 

하지만 이 방법에도 문제가 있긴 합니다.

문제: Secondary clustering

primary clustering 사라지는데 secondary clustering 문제가 발생합니다.

Secondary clustering

• 해시 함수가 특정 slot에 대하여 cluster를 형성하는 것을 말합니다.

결국에 우리가 배열에 얼만큼 띄울지에 대한 정보가 있고, 이 정보에 따라 움직이기 때문에 규칙성이 존재합니다.

결국에 우리는 3, 4, 7, 1 … 처럼 정해진 규칙에 따라서 공간을 찾게 되는 것이죠.

결국 해당 slot에 관해서는 clustering이 존재한다는 것을 뜻합니다.

Improving linear probing

Doubling hashing

지금까지 얼만큼 점프할지에 대한 횟수에 대한 정보만 배열에 저희는 담고 있었습니다.

거기에 키 값도 같이 사용하는 겁니다.

키 값에 또 새로운 다른 hash function을 먹여서 얻은 해시값을 해당 횟수에 곱해주는 겁니다.

만약 새로운 해시 함수를 먹여서 얻게 되는 해시값이 2라고 할 때

[3, 4, 7, 1, 6, 8, 2, 9, 5] // 몇 칸 띄울지에 대한 정보를 담은 배열

이랬던 배열이

[6, 8, 14, 2, 12, 16, 4, 18, 10] // 몇 칸 띄울지에 대한 정보를 담은 배열

이렇게 되고 여기에 % M 연산을 통해서 (M=10)

[6, 8, 4, 2, 2, 6, 4, 8, 0] // 몇 칸 띄울지에 대한 정보를 담은 배열

이런 배열이 되게 되는 것입니다.

이제 이렇게 되면 들어오는 키마다 점프하는 sequence가 다 다르게 됩니다.

따라서 clustering이 안생기게 됩니다.

---

Swift에서는 어떻게 Collision을 해결할까?

https://github.com/apple/swift/blob/main/stdlib/public/core/Dictionary.swift

 

결론부터 말하고 들어가자면 Open addressing과 Linear probing을 활용해서 충돌을 해결한다고 합니다.

 

호오..그렇다면 Open addressing과 Linear probing을 활용한 Dictionary를 구현해보도록 하겠습니다.

간단하게 Key와 Value 모두 String타입이라 해놓고 한번 구현해보겠습니다.

 

아래 메서드를 구현해보겠습니다. 또한 Hashable타입을 사용하지 않고 Array만을 사용해서 구현할 예정입니다.

func value(forKey key: Key) -> Value?
func insert(_ value: Value?, forKey key: Key)
var count: Int { get }

 

 

struct Bucket {
    let key: String
    let value: String
}


final class MJDictionary {
    var array: [[Bucket]]
    
    init(capacity: Int) {
        self.array = Array(repeating: [], count: capacity)
    }
    
    var count = 0
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    private func hash(_ key: String) -> Int {
		return Int(value)! % array.count
    }
    
    func value(forKey key: String) -> String {
        // 찾을 때 그 자리에 바로 원하는 key값이 있다면 가져옴.
        // 하지만 collision이 발생해서 다른 집에 들어가있다면 탐색해야함.
        var index = hash(key)
        
        if array[index][0].key == key {
            return array[index][0].value
        }
        
        repeat {
            index += 1
            index %= array.count
        } while array[index][0].key != key
        
        return array[index][0].value
    }
    
    
    func insert(_ value: String, forKey key: String) {
        if array.count == count { // Array가 가득차면 doubling
            array += Array(repeating: [], count: count)
        }
        
        var index = hash(key)
        
        let toInsert = Bucket(key: key, value: value)
        if !array[index].isEmpty { // Collision 발생.
            if array[index][0].value == value { // 이미 있는 값과 동일한 값이라면
                return // 그냥 끝내줘도 됨.
            }
            repeat {
                index += 1
                index %= array.count
            } while !array[index].isEmpty // 빈공간 찾기 open addressing & linear probing
            array[index].append(toInsert) // 찾은 빈공간에 넣기
        } else { // Collision이 발생하지 않았다면
            array[index].append(toInsert) // 그냥 넣어주면 됨
        }
        count += 1 // 개수 증가
    }
}

우선 코드 전문을 먼저 올려놓고 하나씩 살펴보겠습니다.

chaining기법인 Linked List로 구현하지 않음에도 2차원 배열로 array로 구성한 이유는 init시에 1차원 배열을 선언해서 array에 넣어줄려고 할 때 [Bucket] 을 생성할 때 기본 값이 무조건 있어야했기 때문에 Bucket(key: "", value:"") 이런 의미없는 값을 넣어줘야만 했습니다. 그러고 싶지 않았기에 2차원 배열로 생성해서 빈 배열 [] 을 넣어주는 것으로 구현했습니다.

hash(_ value: String) -> Int

hash function에 해당하는 함수입니다. 해당 함수는 파라미터로 들어온 Key값을 Hash table에 쓰일 인덱스인 Hash값으로 바꿔주는 작업을 수행합니다. 해당 함수가 좋은 hashing function이 될려면 충돌이 적게 나오는 해싱 함수를 구성해야합니다.

예시에서는 이 후 충돌상황을 손쉽게 재현하기 위해서 간단하게 작성하였습니다.

insert(_ value: Value?, forKey key: Key)

func insert(_ value: String, forKey key: String) {
    if array.count == count { // Array가 가득차면 doubling
        array += Array(repeating: [], count: count)
    }

    var index = hash(key)

    let toInsert = Bucket(key: key, value: value)
    if !array[index].isEmpty { // Collision 발생.
        if array[index][0].value == value { // 이미 있는 값과 동일한 값이라면
            return // 그냥 끝내줘도 됨.
        }
        repeat {
            index += 1
            index %= array.count
        } while !array[index].isEmpty // 빈공간 찾기 open addressing & linear probing
        array[index].append(toInsert) // 찾은 빈공간에 넣기
    } else { // Collision이 발생하지 않았다면
        array[index].append(toInsert) // 그냥 넣어주면 됨
    }
    count += 1 // 개수 증가
}

 

insert할 때 신경써줘야할점은 Collision이 발생했을 때 linear probing과 open addressing을 통해서 빈공간을 찾아서 값을 넣어주는 것 입니다.

 

if array.count == count { // Array가 가득차면 doubling
    array += Array(repeating: [], count: count)
}

 

Array자료구조를 사용하고 있기 때문에 처음 init할 때 할당받은 공간이 가득차게 되면 자동으로 doubling을 통해 저장공간을 2배 늘려줍니다.

 

var index = hash(key)

let toInsert = Bucket(key: key, value: value)
if !array[index].isEmpty { // Collision 발생.
    if array[index][0].key == key && array[index][0].value == value { // 이미 있는 값과 동일한 값이라면
        return // 그냥 끝내줘도 됨.
    }
    repeat {
        index += 1
        index %= array.count
    } while !array[index].isEmpty // 빈공간 찾기 open addressing & linear probing
    array[index].append(toInsert) // 찾은 빈공간에 넣기
} else { // Collision이 발생하지 않았다면
    array[index].append(toInsert) // 그냥 넣어주면 됨
}
count += 1 // 개수 증가

 

hashing function을 통해 insert하고자 하는 키값을 우선 해싱합니다. 이를 통해 얻게 된 index를 가지고 Hash table(array)를 살펴봅니다.

 

찾아간 공간, array[index]에 이미 값이 들어있다면 해시 충돌이 발생한 것입니다. 이 때 만약, 충돌이 일어난 공간에 넣고자 하는 key와 value가 동일한 값이 들어온다면 그냥 return시켜줍니다.

 

중요한 곳은 이제부터입니다.

 

위에서 return이 되지 않았다는 것은 다른 Key값이 들어왔는데 해시 충돌이 일어났다는 뜻입니다. Linear Probing의 시작입니다.

구한 index를 +1 씩 증가시키면서 hash table[index]가 Empty일 때까지 이를 반복합니다. (이 때 모듈러 연산을 통해 배열의 크기에 맞게 index를 조정해줘야합니다)

 

while문을 벗어나왔다라는 것은 빈공간을 찾은 것이므로 그 빈공간에 넣고자 하는 Bucket을 넣습니다.

 

이 때 index를 1씩 증가시키면서 선형탐색을 하기 때문에 충돌이 발생했을 때 최악의 경우 O(n)의 시간복잡도가 나옵니다.

---

value(forKey key: String) -> String

func value(forKey key: String) -> String {
    // 찾을 때 그 자리에 바로 원하는 key값이 있다면 가져옴.
    // 하지만 collision이 발생해서 다른 집에 들어가있다면 탐색해야함.
    var index = hash(key)

    if array[index][0].key == key {
        return array[index][0].value
    }

    repeat {
        index += 1
        index %= array.count
    } while array[index][0].key != key

    return array[index][0].value
}

 

값을 꺼내오는 로직입니다. 동일하게 hashing function을 통해 얻은 index를 통해 hash table[index] 위치로 원하는 값을 꺼내기 위해 찾아갑니다.

 

그 곳에 있는 키값이 자신이 찾고자 하는 키값과 동일한지 확인합니다. 동일한 키값이라면 제대로 찾아온 것이므로 저장되어있는 value값을 return하면 됩니다. 이렇게만 찾을 수 있다면 O(1)의 시간복잡도만에 찾을 수 있겠네요.

 

문제는 충돌이 발생해서 그 공간에 다른 키값을 가진 요소가 자리를 차지하고 있을 때 입니다. Open addressing이기에 사실 내집 너집이 없고, 남의 집에 들어가있는 것이죠.

이 때 부터는 목표인 키값을 찾을 때까지 선형 탐색을 하는 수 밖에 없습니다. 이는 O(n)의 시간복잡도를 가집니다.

 

while문을 빠져나왔다는 뜻은 원하는 키값을 찾았다는 것이므로 해당 위치의 value를 return시켜줍니다.

---

답변 타임

정말정말 먼길을 돌아서 왔습니다. 이제는 이 질문들에 그래도 답변을 할 수 있을 것만 같습니다.

Dictionary의 키는 왜 Hashable 타입인가요?

왜 Dictionary/Set의 탐색은 O(1)인가?

hashing function을 통해 index를 얻는 과정은 O(1)로 구해지고, 구한 index를 통해 배열에 접근하는 것 또한 O(1)이기 때문에 통상적으로 O(1)의 시간복잡도를 가집니다.

 

왜 Dictionary 탐색의 최악의 경우는 O(n)인가?

 

insert를 할 때 Collision이 발생했을 때의 경우를 생각해보면 linear probing을 통해서 처음 구한 index 다음으로 올 빈공간을 선형 탐색하는데 O(n)이 걸립니다. 이 후 값을 탐색할 때에도 찾고자 하는 키값을 찾을 때까지 동일한 과정을 거치게 되기 때문에 O(n)이 걸리게 됩니다.

 

Hashable의 hashValue는 왜 Int 인가?

 

hashing function을 통해 얻게 되는 hashValue가 어디에 쓰이는지를 보면 왜 Int인지 알 수 있었습니다. hashValue는 Hash table, 즉 배열의 index로 쓰이기 때문에 hashValue는 Int여야만 합니다.

Hashing을 왜 하는가?

 

빠른 데이터 탐색과 삽입을 위해서 hashing을 사용합니다.

좋은 해싱 알고리즘이 필요한 이유는?

 

좋은 hashing function이란 충돌 확률이 적은 hashValue를 만들어주는 hash function을 말합니다. 충돌 확률이 만약 높아서 충돌이 많이 발생하게 된다면 값을 삽입할 때나 탐색할 때 최악의 경우 O(n)의 시간복잡도가 걸릴 수 있기 때문에, 좋은 해싱 알고리즘을 적용한 hashing function을 통해서 충돌 확률을 낮춘다면 O(1)의 시간복잡도로 hashing을 유의미하게 사용할 수 있게 됩니다.

---

마무리

오늘은 hashing에 대해서 공부하고 Swift에서의 자료구조 dictionary가 어떻게 구현되어있는지를 엿보고 그 방법을 적용한 딕셔너리를 직접 구현해보았습니다. 애매하게 알고 있던 부분과 기억이 가물가물 했던 부분을 다시 재정리하면서 다시 기반을 다질 수 있어서 보람찼던 것 같습니다ㅎㅎ