[Data Structure] 딕셔너리 구현해보기 Swift Dictionary

스위프트에서 딕셔너리는

자바나 일반 자료구조에서의 HashTable과 같은 개념에요

key-value로 이루어져있고

데이터 간에는 순서가 없죠

 

우선 HashTable이 뭔지 부터 알아볼까요??

 

 

HashTable 이란

key와 value의 쌍으로 이루어진 데이터 타입이에요

매핑하기전 원래값을 key, 매핑후 데이터 값을 hash value(hash code)라고 하며

그 hash value를 배열의 index로 사용하고 그 index에 value를 저장해서 사용하는 방식이에요

 

 

Hash함수란

해시 함수는 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수

 

왜 사용할까요??

특정 key값에 해당하는 데이터를 바로 찾을 수 있어요

평균 시간 복잡도 O(1)

최악의 경우는 O(n) - 모든 key값에 대해서 해시 충돌이 일어날 경우

 

 

해시충돌

다른 key값이 같은 hash value로 변경되는 문제

 

비둘기집 원리

n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한상자에는 두개 이상의 물건이 들어있다는 원리

 

충돌이 최대한 적게 일어나게 만드는 해시함수를 사용하는게 좋아요

(하지만 성능이 좋은 함수일수록 내부적인 연산이 오래걸리겠죠..?)

 

 

충돌해결

 

Resizing

테이블에 할당된 공간을 다사용해서 더이상 사용할 수 없을 때사용

테이블 크기를 늘려준뒤 기존데이터를 다시 해시함수로 보내서 재정렬

 

 

Open Addressing

링크드리스트와 같이 추가적인 메모리공간을 사용하지않고

빈공간을 사용하는 방법이에요

충돌이 발생하면 인덱스 뒤에있는 버킷중 빈곳을 찾아서 데이터를 넣어요

 

대표적인 3가지 방식이 있어요

선형 탐색(Linear Probing) - 충돌시 다음 버켓, 혹은 몇개를 건너뛰어 데이터삽입

제곱 탐색(Quadratic Probing) - 충돌시 제곱만큼 건너뛴 버켓에 데이터 삽입

이중 해시(Double Probing) - 충돌시 다른 해시함수를 한번더 적용한 결과를 사용

 

장점

포인터가 필요없고 추가적인 저장공간이 필요없음

삽입,삭제시 오버헤드가 적다

저장할 데이터가 적을 때 더 유리함

 

 

Close Addressing(Separate Chaining)

충돌이 발생하면 링크드 리스트로 연결하여 문제를 해결

버켓이 꽉차더라도 연결리스트로 늘려가기때문에 데이터의 주소값은 바뀌지 않는다

수행시간이 일어진다 -> 리스트 안에 있는 데이터를 다 확인해야 함

 

장점

복잡한 계산식이 필요없고 연결 리스트만 사용하면 됌

성능 저하가 Linear하게 발생

 

 

이렇게 좋은 자료구조를 인데

왜 모든곳에 안쓸까요..?

 

공간 효율성이 떨어지고

해시함수 의존도가 높고

충돌없이 만든 좋은 해시함수는 그 자체 연산시간도 소모되서 시간이 걸릴 수도 있죠

이러한 이유로 이 자료구조에 적합한곳에 사용하는게 좋다고해요

 

 

 

이제 딕셔너리를 한번 만들어볼까요?

물론 정말 스위프트 내장타입으로 있는 딕셔너리처럼은 만들지 못하지만

개념을 활용해서

비슷하게만 만들어볼거에요 ㅎㅎ

정의를 보면

Key는 Hashable을 따르고 있네요

Hash가능한 타입이여야해요!

 

스위프트에서는 Hashable라는 프로토콜이 있어요

그 값은 유일하게 구분되어야 하죠

Swift의 기본 타입(Int, String...)은 대부분 Hashable을 따르고 있어서 Key로 사용할 수 있지만

직접만든 Struct을 Key로 쓰려면 Hashable을 채택하고 구현해줘야해요

위의 사진같이

==를 구현해주고

hash함수를 구현해줘야했지만 

지금은 : Hashable만 써주면 내부적으로 처리해주는것 같아요!!

자동으로 처리해주기때문에 struct의 모든 저장프로퍼티는 Hashable를 따라야하구요

 

 

스위프트에서 같은 입력값이면 같은 해쉬값이 나오는걸 볼 수 있어요

빌드할 때마다 값은 다르게나오구요

같은 인스턴스면 같은 해쉬값일 수 있지만

반대로 같은 해쉬값이면 같은 인스턴스가 아닐 수도 있어요!!

역은 성립하지않아요

 

이제 구현을 위해 설계를 해보자면

key로 abc를 사용한다면

hash함수에 의해서 일정한 index로 변환되서

그위치에 저장되는 방식이에요

Hashable을 준수하고있으니 key의 해쉬값을 이용해서

해당하는 bucket 위치에넣어주면 되겟죠?

 

넣어줄 bucket을 일정한 크기로 만들어주고

dic[abc] = 123 이렇게 입력받으니까

subscript를 구현해줄거에요

입력할때, 읽을때 해시를 이용해서 값을 가져올거구요

 

struct MakeDictionary<Key, Value>: CustomDebugStringConvertible where Key: Hashable {
    var debugDescription: String {
        let temp = buckets.filter { $0.key != nil }
        temp.forEach { print($0) }
        return ""
    }
    
    struct Hash {
        var key: Key?
        var value: Value?
    }
    
    private let capacity: Int
    private var buckets: [Hash]
    
    init(capacity: Int = 100000) {
        self.capacity = capacity
        self.buckets = Array<Hash>(repeating: Hash(key: nil, value: nil), count: capacity)
    }
    
    subscript (_ key: Key) -> Value? {
        set {
            guard let value = newValue else {
                return
            }
            let position = hash(key: key)
            buckets[position] = Hash(key: key, value: value)
        }
        
        get {
            let position = hash(key: key)
            return buckets[position].value
        }
    }
    
    private func hash(key: Key) -> Int {
        abs(key.hashValue) % capacity
    }
}    

bucket을 임의로 100000사이즈로 정의해준다음

 

index는 해시값을 용량과 나누고 남은 나머지가 되고

그 index에 값을 저장했어요

 

여기서 구조체를 출력하면 100000개가 출력되서 좀 문제가생길거에요 ㅎㅎ

그래서

 

CustomDebugStringConvertible

을 이용해서 출력시 나오는 String을 커스텀해줄거에요

 

그리고 딕셔너리의 사이즈를

bucket사이즈로하면 항상 100000이 나올거기때문에

키값이 nil이 아닌갯수를 반환하고

 

key만 배열로 받을 수 있도록 만들어 줘야겠죠

    var size: Int {
        return buckets.filter { $0.key != nil }.count
    }
    
    var keys: [Key] {
        return buckets.filter { $0.key != nil }.compactMap {$0.key}
    }

 

 

아주 잘 나오는걸 볼 수 잇어요 ㅎㅎ

 

 

그런데!! 

저희가 쓰는 딕셔너리는 for문에도 돌아가지만

지금 만든건 돌아가지않죠

 

 

Sequence를 준수하지 않았기때문이에요!!

시퀀스는 요소전체를 하나씩 접근할 수 있도록 해주는 거구요

 

 

Sequence, IteratorProtocol를 같이 구현 해줘야해요

extension MakeDictionary: Sequence, IteratorProtocol {
    
    typealias Element = Hash
    
    
    private mutating func makeIterator() -> MakeDictionary<Key, Value> {
        self.current = 0
        return self
    }
    
    mutating func next() -> Hash? {
        if current < allIndex.count {
            defer { current += 1}
            return buckets[allIndex[current]]
        }
        return nil
    }
}

makeIterator은 Sequence에 있는 메서드로

디폴트로 만들어주지만 원하는 작업이 있다면 따로 구현해주고저같은경우는 처음 접근할때 접근하는 index를 초기화시켜줬어요

 

 

그리고 IteratorProtocol를 준수하면

next를 구현해 줘야해요

다음 값을 접근하는 메서드죠

 

next가 끝나고 다음 값을 접근해야하니까 defer를 이용해서 함수 종료후 

current가 증가되도록 했어요

 

값에 접근할 때 이미 채워진 해시값을 알면 좀더 효율적으로 접근 할 수 있을 것 같았어요

그래서 구조를 좀 다시 바꿔밨어요

buckets에 값을 넣을때 index를 저장하기위한 allIndex변수를 추가했어요

 

next()에서

현재 존재하는 키값이 위치한 배열의 index를 저장한 배열인 allIndex가 있고

current로 하나씩 증가하면서 접근하면

값이 있는 배열만 접근하면서 나타낼 수 있을 거에요

 

allIndex가 추가되면서

size와 keys를 allIndex를 이용하도록 더 간단하게 수정했어요

 

for문이 잘동작하네요 ㅎㅎ

 

충돌시 해결하는 로직은 만들지 않았구요

비슷하게 만들긴한것 같은데 부족한 점이 많을거같네요...

잘 만든건지 모르겠어요...

 

 

아래는 전체 코드구요!!

struct MakeDictionary<Key, Value>: CustomDebugStringConvertible where Key: Hashable {
    var debugDescription: String {
        let temp = buckets.filter { $0.key != nil }
        temp.forEach { print($0) }
        return ""
    }

    struct Hash {
        var key: Key?
        var value: Value?
    }
    
    subscript (_ key: Key) -> Value? {
        set {
            guard let value = newValue else {
                return
            }
            let position = hash(key: key)
            buckets[position] = Hash(key: key, value: value)
            allIndex.append(position)
        }
        
        get {
            let position = hash(key: key)
            return buckets[position].value
        }
    }
    
    subscript () -> [Hash] {
        get {
            return buckets.filter { $0.key != nil }
        }
    }
    
    private let capacity: Int
    private var buckets: [Hash]
    private var allIndex: [Int] = []
    private var current = 0
    
    var size: Int {
        return allIndex.count
        // buckets.filter { $0.key != nil }.count
    }
    
    var keys: [Key] {
        return allIndex.map { buckets[$0].key! }
        // buckets.filter { $0.key != nil }.compactMap {$0.key}
    }
    
    init(capacity: Int = 100000) {
        self.capacity = capacity
        self.buckets = Array<Hash>(repeating: Hash(key: nil, value: nil), count: capacity)
    }
    
    private func hash(key: Key) -> Int {
        abs(key.hashValue) % capacity
    }
}

extension MakeDictionary: Sequence, IteratorProtocol {
    
    typealias Element = Hash
    
    
    private mutating func makeIterator() -> MakeDictionary<Key, Value> {
        self.current = 0
        return self
    }
    
    mutating func next() -> Hash? {
        if current < allIndex.count {
            defer { current += 1}
            return buckets[allIndex[current]]
        }
        return nil
    }
}