[Swift] Hashable이 Equatable을 채택하는 진짜 이유

Swift에서Hashable이 Equatable을 채택하는 진짜 이유는 Hash Collision 때문이다.

글을 쓰게 된 계기..

며칠 전 회사에서 일을 하며 DiffableDatasource을 사용하고 있었다. 이때 SnapShot에 해쉬값이 동일한 아이템을 넣었는데 크래쉬가 나지 않았다!!!

이유를 알기 위해 문서를 찾다 보니 아래와 같은 내용이 있었다. Updating Collection Views Using Diffable Data Sources

Two identifiers that are equal must always have the same hash value. However, the converse isn’t true; two values with the same hash value aren’t required to be equal. This situation is called a hash collision. To increase efficiency, try to ensure that unequal identifiers have different hash values. The occasional hash collision is okay when it’s unavoidable, but keep the number of collisions to a minimum. Otherwise, the performance of lookups in the data collection may suffer.

핵심은 첫번째 줄이다 "Identifier가 같은 객체는 같은 해쉬값을 가지지만 같은 해쉬값을 지녔다고 같은 객체는 아니다". Hashable, Equatable에 대해서 놓친 부분이 있다는 것을 깨달았다. 그래서 이번 기회에 Hashable에 대해서 자세히 알아보면서 왜 Equatable을 채택해야 하는지 이유도 알아보려고 한다.

 

Hashable은 무엇인가?

간단하게 Hashable은 Siwft에서 객체를 해시 테이블에 저장할 수 있게 해주는 프로토콜이다.

쉽게 말하자면 이 프로토콜은 객체를 해시값으로 변환할 수 있게 해주고 이 해시 값은 Dictionary의 키, Set의 요소로 사용된다. 해시 값은 Hasher를 통해 생성되는데 매번 실행 시 랜덤 시드값이 Hasher에 들어가기 때문에 프로그램 실행마다 해시값이 다를 수 있다.

public protocol Hashable : Equatable {
    var hashValue: Int { get }
    func hash(into hasher: inout Hasher)
}

프로토콜을 살펴면 `Equatable`을 채택해야만 한다. Equatable을 채택하면 객체 간의 Equability를 비교할 수 있게 된다. 즉 두 객체가 같은지 다른지 판단할 수 있는 기능을 제공한다.

public protocol Equatable {
    static func == (lhs: Self, rhs: Self) -> Bool
}

 

그런데, 왜 Hashable은 Equatable이 필요한가?

"Hashable의 해시값들끼리 비교해야하니까..?" 라는 답변을 들은 적 있다. 이전에 나도 이런 식으로 생각했던 적이 있었다. 하지만 위에 Hashable protocol의 hashValue는 Int값이다. 즉 기본 타입으로 Equatable은 이미 구현되어 있다.

이 질문의 핵심은 바로 "Hash Collision"에 있다. 해쉬 충돌이란 서로 다른 두 객체가 같은 해쉬값을 가질 때 발생하는 현상이다. 그렇다면 이 해쉬 충돌과 Equatable을 연결지어 생각해 보자

 

Hash Collsion과 Equatable

Dictionary는 키값을 사용해서 O(1)의 시간 복잡도를 같는다. 하지만 무수히 많은 아이템이 추가되거나 hash function의 한계로 인해 중복된 키값이 생길 수 있다. 이때 가장 쉬운 방법은 기존의 값을 덮어 씌우는 방법이 있지만 이는 데이터 손실이 발생한다. 그러기에 여러 가지 방법을 쓰게 되는데 Chaining, Open Addressing 방법 등을 사용한다.

해쉬 충돌 출처: https://en.wikipedia.org/wiki/Hash_collision

그렇다면 본론으로 다시 돌아와서, 두 개의 다른 객체가 동일한 해시값을 가질 수 있다. 해시값을 단순히 Index로 보면, 해시값이 같은 경우 두개의 객체가 실제로 같은지를 체크해야 한다.

1. 해쉬값은 같고 실제로도 같은 경우: 그대로 값을 덮어 씌운다.
2. 해쉬값은 같지만 실제 값이 다른 경우: 다른 빈 슬롯을 찾아 넣는다. (Linear Probing)

그렇기에 Equatable을 채택해야만 하는 것이다. 정리하자면

Hashable은 해쉬 충돌이 발생했을 때, Equatable을 사용해 두 객체가 정말 같은지 확인하기 위해서 Equatable이 필요하다.

 

코드 예제

간단한 코드 예제를 통해 이 개념을 이해해 보자. 해시값이 같은 세 개의 인스턴스를 만들고 이를 딕셔너리에 저장해 보자.

반응형

import Foundation

struct ObjectA: Hashable {
    var a: String
    var b: Int
    func hash(into hasher: inout Hasher) {
        hasher.combine(a)
    }
}

let original = ObjectA(a: "12", b: 1)
let test1 = ObjectA(a: "12", b: 1) // same hash value & equal object
let test2 = ObjectA(a: "12", b: 3) // same hash value & but different object

print(original.hashValue) // 7443114000065216636
print(test1.hashValue) // 7443114000065216636
print(test2.hashValue) // 7443114000065216636 all same

print(original == test1) // true
print(original == test2) // false

print(original.hashValue == test1.hashValue) // true
print(original.hashValue == test1.hashValue) // true

var dic: [ObjectA: Int] = [:]

dic[original] = 1
dic[test1] = 2
dic[test2] = 3

print(dic)

• Object A는 Hashable을 채택하고 있는데 해쉬 값을 만들 때 a 변수만 고려해서 만들게 된다. 그리고 equatablity 비교 시에는 a, b 변수를 모두 사용한다.
• test1는 original과 모든 값이 같으므로 해쉬값이 같고 같은 객체이다
• test2는 original과 a만 값이 같으므로 해쉬값이 같지만 다른 객체이다.
• print로 해쉬값을 찍어보면 같은 해쉬값들을 가지고 있는 것이 보인다.
• print로 객체 간의 관계를 살펴보았다.
• 이후 딕셔너리에 3개의 인스턴스를 차례대로 넣었다.

/*
 Result:
 [ObjectA(a: "12", b: 1): 2,
 ObjectA(a: "12", b: 3): 3]
 */

결과를 살펴보면 같은 해쉬값을 지닌 3개의 인스턴스를 딕셔너리에 넣었을 때:

• test1과 original은 해쉬값을 비교 후 equtable을 통해 같은 인스턴스로 판명되어 덮어써진 것을 확인할 수 있다.
• test2는 origin, test1과 같은 해쉬값을 지니고 있지만 equtable을 통해 다른 인스턴스로 판명되어 딕셔너리에 새로운 값이 추가되었다.

 

결론

결론적으로, Swift에서 Hashable이 Equatable을 요구하는 것은 Hash Collision 때문이다. 딕셔너리와 같은 컬렉션에서는 같은 해시값을 가진 키가 존재할 수 있으며, 이 경우 Equatable을 사용하여 실제 값이 같은지를 비교한다. 이를 통해 Swift는 효율적으로 데이터를 관리할 수 있게 된다.

 

여담

Swift에서는 해쉬 충돌 시 Open Addressing 기법 중 하나인 Linear Probing을 사용한다. 이 방식은 해쉬 충돌이 발생하면 다음 빈 슬롯을 찾아 그곳에 아이템을 저장하는 방식이다.

Native storage is a hash table with open addressing and linear probing. The bucket array forms a logical ring (e.g., a chain can wrap around the end of buckets array to the beginning of it).

아래 블로그에서 각각의 언어가 어떠한 방식으로 Hash Collision에 대응하는지 알 수 있었는데 아주 흥미로웠다.

언어	방식
C++	개별 체이닝
Java	개별 체이닝
Go	개별 체이닝
Ruby	오픈 어드레싱
Python	오픈 어드레싱

출처: https://ryu-e.tistory.com/87

Reference

• Updating Collection Views Using Diffable Data Sources
• https://ryu-e.tistory.com/87
• https://github.com/apple/swift/blob/main/stdlib/public/core/Dictionary.swift