[Swift] Dictionary에서의 HashTable Collision

안녕하세요🙇‍♂️

 

이번 게시글은 자료구조를 공부하다가 다양한 Collision 해결 방법 중에 Swift는 어떤 방법을 채택하고 있는지 갑자기 궁금해져서

 

작성하게 되었습니다.

 

간단하게 HashTable과 Collision에 대해 알아보고 Swift에서는 Collision을 어떤 방법으로 해결하는지 작성하려고 합니다. 혹시나 Swift에서 Collision 해결 방법만 궁금하시다면 바로 아래로 스킵하셔도 됩니다. :)

 

자 시작해봅시다!

 

HashTable은 <Key, Value> 쌍으로 1:1 매핑 되어 있는 데이터 구조를 말하죠?

 

Key에 해당 하는 값에 정해진 해쉬함수를 적용해서 인덱스를 뽑아내고 Bucket 또는 Slot이라고 불리는 Storage에 해당 인덱스에 Value 값을 저장하는 방식입니다.

 

Key 값은 항상 유일해야 하기 때문에 해당 키값에 맞는 인덱스값 또한 유일하겠죠?

 

예를 들어 "John" 이라는 Key 값에 해쉬함수를 적용해서 인덱스를 찾을 때, 해쉬함수가 동일하다면 항상 같은 인덱스 값이 나올 것 입니다.

 

그렇다면 충돌은 언제 일어나는 걸까요?

 

코드로 예시를 들어보겠습니다 :)

 

struct Person: Hashable {
  
  let lastName: String
  let familyName: String
  
  func hash(into hasher: inout Hasher) {
    hasher.combine(familyName)
  }
}

let john = Person(lastName: "John", familyName: "João")
let felix = Person(lastName: "Felix", familyName: "João")

print("좐의 해쉬값: \(john.hashValue)")
print("펠릭스의 해쉬값: \(felix.hashValue)")

// 결과값
// 좐의 해쉬값: -1046845654427067341
// 펠릭스의 해쉬값: -1046845654427067341

 

familyName을 통해 해쉬값을 구하도록 했는데 좐과 펠릭스의 familyName이 동일합니다.

당연히 결과값을 확인해보면 동일한 해쉬값이 나오게 됩니다.

 

이 상태에서 Dictionary에 좐과 펠릭스를 저장한다면 해쉬값이 동일하기 때문에 같은 인덱스에 저장하기 위해 충돌이 일어날 것입니다.

 

이러한 문제를 해결하는 방법은 크게 2가지 방법이 있고 각 방법 또한 세부적으로 나눠져 있습니다.

이 글은 HashTable에 깊게 알아보는 글이 아니니 종류에 대해 나열만 하도록 하겠습니다. 😅

 

Open Addressing

LinearProbing, Quadratic Probing, Double Hashing

Separate Chaining

LinkedList를 이용

 

 

요런 방법들이 있지요? 

각각의 방법들에는 장단점이 있는데,

 

자! 그렇다면 Swift의 Dictionary에서는 어떤 Collision 해결방법을 사용할까요?

 

 

 

바로 Linear Probing입니다.

뭔가 SeparteChaining 방법을 사용할 줄 알았는데 Linear Probing을 사용하네요.

 

글들을 찾아보니 이유는 그냥 간단해서??.. 라고 하는데 이게 맞나.. 이래도 되나요 ㅋㅋㅋㅋ

이유가 있으셨겠죠?

 

마지막으로 Equatable에 대해 간단하게 얘기하면서 마무리하려고 합니다.

 

Hashable을 채택했는데 Equatable까지 채택해서 == 스태틱 메서드를 구현하라고 Xcode가 압박을 넣는 것을 경험한 적이 있으실 겁니다.

 

저는 개인적으로 이게 뭔 이유로 이러나 하고 그냥 별 생각 없이 구현하고 넘어갔었습니다. 🤪

좀만 더 깊게 생각해보면 Collision이 일어났을 때(인덱스 값이 같을 때) 실제 값을 비교해서 일치하는지를 확인하기 위함이었단걸 알 수 있습니다. 값이 같은지 비교한 후에 Linear Probing 방법으로 Storage에 저장하겠죠?

 

좀 최근에 깨달은 거여서 뿌듯한 마음에 적어봤습니다 :)

 

 

이번 게시글에서는 간단하게 HashTable과 Collision에 대해 알아보고

 

실제 Swift에서는 어떤 Collision 해결방법을 사용하는지 알아봤습니다.

 

혹시 오타나 틀린 부분에 대해서는 댓글로 지적 부탁드립니다. :)

 

 

(추가적으로 swift Dictionary github에 18번째 라인에 LinearProbing을 사용한다고 나와 있습니다. 이상!)

 

 

Reference

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

apple/swift

https://ciechanow.ski/exposing-nsdictionary/

Exposing NSDictionary – Bartosz Ciechanowski

https://stackoverflow.com/questions/28379809/how-are-hash-collisions-handled

How are hash collisions handled?