[자료구조] 해시 테이블(+Swift)

 

안녕하세요 오늘은 자려구조중 해쉬테이블에 대해 다뤄보겠습니다.

 

어떤 개발자에게 "해시테이블을 모르면 개발자가 아니다." 라는 말을 들은적이 있는데요.

 

해시테이블 개념에 대해 정리해보고, Swift에서는 어떻게 활용할 수 있을지 알아보겠습니다.

 

 

 

해시 테이블

해시 테이블은 key, value쌍으로 이루어진 자료구조입니다. 

 

내부적으로 배열을 사용하여 구현됩니다. key값을 배열의 인덱스로 변경하기 위해 해시함수를 사용합니다.

 

해시함수마다 성능의 차이는 존재하지만, 서로다른 키 값에 대해서 같은 해쉬값이 생기게되어 충돌(collision)이 발생할 수 있습니다.

 

해당 경우를 해결하기 위한 방법들은 다음과 같습니다.

 

 

 

체이닝

특정 해시값이 가리키는 공간을 링크드 리스트의 시작점으로 하고 충돌이 발생하는 경우

 

링크드 리스트의 노드를 추가하고 키와 값을 저장합니다.

 

탐색시 링크드 리스트를 순회하며 일치하는 Key값을 찾는 방식으로 탐색이 진행됩니다.

 

해당 방식은 충돌이 많이 발생하는 경우 탐색시 O(1)의 복잡도를 가지는 해시 테이블의 장점이 다소 경감됩니다.

 

 

 

오픈 어드레싱

오픈 어드레싱 방법은 체이닝 방식을 사용하지 않고 충돌 문제를 해결할 수 있습니다

 

위에 링크드리스트 처럼 충돌이 발생할 시 (키, 값)쌍을 이어붙이는 것이 아닌, 또 다른 공간을 탐색합니다.

 

그러다 빈 공간이 발생하는 경우 해당 공간을 사용하게됩니다.

 

충돌이 발생한 인덱스 뒤로 한칸씩움직이며 빈공간을 찾는 방식을 Linear probing이라고 합니다.

 

해싱 값에 한번더 해싱을 하여 새로운 인덱스 값을 도출하는 이중 해싱 방법역시 존재합니다.

 

 

 

 

동시성 문제

해시테이블이 Thread Safe하지 않을 경우 여러 쓰레드에서 특정 같은 해시테이블에 접근시 동시성문제가 발생할 수 있습니다.

 

Thread Safe하다는 말은 여러 쓰레드에서 수정가능한 자원에 동시에 접근하여도 동기화를 통해 안전하게 해당 자원을 사용할 수 있도록 설계된 것을 말합니다.

 

여기서 안전함이란, 얘기치 않은 동작이 발생하지 않음을 의미하는 것입니다.

 

"특정 시점에 해당 값을 읽었을 때 예상한 값이 있어야 한다" 와 같은 예를 들 수 있습니다.

 

 

 

 

Swift

 

Swift는 Dictinary와 Set이 내부적으로 해시테이블을 사용합니다.

 

딕녀너리의 키값과 Set의 요소는 Hashable프로토콜을 채택해야한다는 점을 확인할 수 있습니다.

 

 

 

동시성 문제 해결하기

Swift의 딕셔너리는 Thread Safe하지 않습니다.

 

아래코드는 멀티쓰레드 환경에서 동일한 자원에 접근하는 경우 입니다.

 

※ 값타입의 경우 클로져 캡쳐리스트에 포함시 복사로 값을 가져옴으로 클래스의 프로퍼티를 통해 접근하도록 구현했습니다.

class UnSafeDict {
    var dict: [String: Int] = ["test":1]
}

let unSafeDict = UnSafeDict()

let queue = OperationQueue()

queue.addOperation { [unSafeDict] in
    unSafeDict.dict["test"] = 2
}
queue.addOperation { [unSafeDict] in
    unSafeDict.dict["test"] = 3
}
queue.addOperation { [unSafeDict] in
    print(unSafeDict.dict["test"]!)
}

 

실행결과

 

해당코드를 실행하면, BAD_ACCESS런타임 에러가 발생합니다.

 

해당 에러는 잘못된 메모리 주소 공간에 접근하는 경우 발생합니다.

 

에러가 발생하는 이유는, 딕셔너리가 값타입이기 때문입니다. 딕셔너리는 Swift의 Copy-on-write방식에 의해

 

값이 수정되는 경우 값타입 자체가 복사되어 새로운 공간에 할당되고, 포인터는 새로운 공간을 가리키게 됩니다.

 

동시성 환경에서 미처 변경되지 못한 포인터가 메모리 해제된 공간을 가리켜 런타임 에러가 발생한 것입니다.

 

따라서 NSLock혹은 GCD, Actor를 사용하여 동시성 문제를 해결할 수 있습니다.

 

 

 

NSLock

NSLock은 lock매서드 호출시 락을 획득하기 전까지 해당 동작을 요청한 쓰레드를 대기시킵니다.

 

lock을 획든한 경우에만 Dictionarty에 접근할 수 있도록 함으로써 Thread Safe를 보장할 수 있습니다.

 

Thread Safe한 딕셔너리는 다음과 같습니다.

 

class DictWithLock {
    
    private var dict: [String: Int] = [:]
    
    let lock = NSLock()
    
    func write(key: String, value: Int) {
        lock.lock()
        dict[key] = value
        lock.unlock()
    }
    
    func get(key: String) -> Int? {
        lock.lock()
        defer {
            lock.unlock()
        }
        return dict[key]
    }
}

 

런타임 에러가 발생한 코드의 딕셔너리를 해당타입으로 바꿔 실행시켜 보겠습니다.

 

let dictWithLock = DictWithLock()

class UnSafeDict {
    var dict: [String: Int] = ["test":1]
}

let queue = OperationQueue()

queue.addOperation { [dictWithLock] in
    dictWithLock.write(key: "test", value: 2)
}
queue.addOperation { [dictWithLock] in
    dictWithLock.write(key: "test", value: 3)
}
queue.addOperation { [dictWithLock] in
    print(dictWithLock.get(key: "test")!)
}

 

실행결과

 

런타임 에러가 발생하지 않고 결과가 잘 출력됨을 확인할 수 있습니다.

 

 

GCD

 

GCD 동시성 큐를 사용하여 읽기작업및 쓰기를 실행시켜보겠습니다.

 

class UnSafeDict {
    var dict: [String: Int] = ["test":1]
}

let unsafeDict = UnSafeDict()
let corcurrentQueue = DispatchQueue.global(qos: .default)

corcurrentQueue.async { [unsafeDict] in
    unsafeDict.dict["test"] = 2
}
corcurrentQueue.async { [unsafeDict] in
    print(unsafeDict.dict["test"]!)
}
corcurrentQueue.async { [unsafeDict] in
    unsafeDict.dict["test"] = 3
}
corcurrentQueue.async { [unsafeDict] in
    print(unsafeDict.dict["test"]!)
}

 

실행결과

 

읽기/쓰기 작업을 모두 비동기로 처리할 경우 앞선 상황의 문제를 해결하지 못합니다.

 

쓰기작업의 경우만 동기로 작업을 등록시켜 보겠습니다.

 

※ 동기 작업이 등록되면 큐의 나머지 작업들은 해당 작업이 끝날때 까지 대기상태가 된다. 동기작업의 경우 큐에 등록되마자 즉시 실행되며 즉시, 등록된 나머지 작업들을 대기상태로 만든다. (+실행중인던 비동기 작업의 쓰레드 역시 대기)

 

let unsafeDict = UnSafeDict()
let corcurrentQueue = DispatchQueue.global(qos: .default)

🤚🤚🤚
corcurrentQueue.sync { [unsafeDict] in
    print("순서1")
    unsafeDict.dict["test"] = 2
    print("순서1종료")
}

corcurrentQueue.async { [unsafeDict] in
    print("순서2")
    print(unsafeDict.dict["test"]!)
}

🤚🤚🤚
corcurrentQueue.sync { [unsafeDict] in
    print("순서3")
    unsafeDict.dict["test"] = 3
    print("순서3종료")
}

corcurrentQueue.async { [unsafeDict] in
    print("순서4")
    print(unsafeDict.dict["test"]!)
}

 

 

실행결과

 

등록되자마자 실행되는 동기작업들에 의해 비동기 작업들은 대기상태가 되고,

 

동기작업들이 모두 끝난 이후에 실행되는 것을 확인할 수 있습니다.

 

하지만 해당 방식은 완변한 Thread-Safe를 보장할 수 없습니다.

 

동기작업들이 비동기 작업들을 대기시키지만 그 시점에 따라 앞선 예제처럼 런타임 오류를 여전히 야기할 수 있습니다.

 

 

모든작업을 동기로 등록함으로 작업의 순서와 결과를 동기화 시킬 수 있습니다.

 

※ 혹은 직렬큐를 사용

 

모든 작업을 동기로 등록하는 경우 처리결과

 

하지만 해당 구현방식은 하나의 쓰레드가 하나의 딕셔너리를 통째로 점유한다는 문제점이 있습니다.

 

서로 상관없는 키값들에 대해 접근이 이뤄질 경우 해당 구현 방식은 매우 느린 처리가 발생할 것을 알 수 있습니다.

 

 

예를들어 아래코드의 "test"키와 "practice"는 서로다른 키값이지만, 동시에 처리되지 못합니다.

 

corcurrentQueue.sync { [unsafeDict] in
    print("순서1")
    unsafeDict.dict["test"] = 2
    print("순서1종료")
}
corcurrentQueue.sync { [unsafeDict] in
    print("순서2")
    print("test: \(unsafeDict.dict["test"]!)")
}
corcurrentQueue.sync { [unsafeDict] in
    print("순서3")
    unsafeDict.dict["practice"] = 3
    print("순서3종료")
}
corcurrentQueue.sync { [unsafeDict] in
    print("순서4")
    print("practice: \(unsafeDict.dict["practice"]!)")
}

 

실행결과

 

자바의 해쉬 테이블도 Thread Safe한 접근을 보장하지만, 위와 같은 문제를 가지고 있습니다.

 

그래서 등장한 개념이 CocunrrentHashable입니다.

 

동시성 해시테이블은 (키, 값)으로 이루어진 하나의 엔티티를 단위로 읽기/수정 을 동기화 시킵니다.

 

해당 방식을 actor를 사용하여 구현해보겠습니다.

 

Actor를 사용한 CocunrrentHashable

 

Actor는 참조타입임으로 프로퍼티값에 수정이 발생해도 메모리 주소가 이전되지 않습니다.

 

접근이 동시에 일어남을 확인하기 위해 수정/읽기 접근을 하는 Key값을 출력해보겠습니다.

 

actor MyActor<T> {
    
    var value: T
    
    init(value: T) {
        self.value = value
    }
    
    func getValue(key: String) -> T {
        print("\(key) 읽기")
        defer {
            print("\(key) 읽기 종료")
        }
        return value
    }
    
    func setValue(key: String, _ newValue: T) {
        print("\(key) 쓰기")
        defer {
            print("\(key) 쓰기 종료")
        }
        value = newValue
    }
}

class UnSafeDict<T> {
    var dict: [String: MyActor<T>] = [:]
}

let unsafeDict = UnSafeDict<Int>()

Task {
    unsafeDict.dict["test"] = MyActor(value: 1)
    unsafeDict.dict["practice"] = MyActor(value: 2)
    
    Task.detached { [unsafeDict] in
        await unsafeDict.dict["test"]!.setValue(key: "test", 3000)
    }
    Task.detached { [unsafeDict] in
        print(await unsafeDict.dict["test"]!.getValue(key: "test"))
    }
    Task.detached { [unsafeDict] in
        await unsafeDict.dict["practice"]!.setValue(key: "practice",1000)
    }
    Task.detached { [unsafeDict] in
        print(await unsafeDict.dict["practice"]!.getValue(key: "practice"))
    }
}

 

실행결과

 

서로다른 키값에 대한 접근이 병렬적으로 이루어짐을 알 수 있습니다.

 

 

해시테이블의 장점인 빠른 접근이 가능하면서도 동시성문제를 해결할 수 있는 방식으로 생각됩니다.

 

 

구현사항에 대한 문제 글의 문제에 대해 댓글록 알려주시면 감사하겠습니다! 🙇‍♂️

 

 

 

참고한 글들

 

HashMap vs HashTable vs ConcurrentHashMap

 

 

Actor | Notion