Hashable/Equatable

Hashable이 무엇이고,
Hashable은 Equatable을 왜 상속해야할까?

Hashable이 무엇일까

Swift 에서 다음과 같은 상황에 Hashable 프로토콜을 채택한다.

• dictionary의 key의 타입으로 사용할 때
• set의 타입으로 사용할 때

그 이유는 set과 dictionary는 array와 다르게 순서가 없어서 검색을 하기 위한 수단으로 사용한다.
set과 dictionary의 시간 복잡도는 O(1)으로 특정 요소를 검색할 때 처음부터 끝까지 찾아볼 필요 없이 바로 그 자리로 가서 찾을 수 있다.
set과 dictionary가 중복을 허용하지 않는 이유도 여기에서 나온 것 같다.
Hashable을 채택하면 hash Value를 구할 수 있게 되는데, hash Value는 요소들의 위치를 찾는 수단이 된다.

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

• Hash Value는 무엇일까
  • 어떤 데이터가 와도 64비트짜리 정수로 치환하는거 (암호화)
  • 원본 데이터를 특정 규칙에 따라 처리하여 간단한 숫자로 만든 것
  • 2개의 데이터 비교시 데이터가 동일할 때 둘의 해시값은 같다.
    • 하지만 조금이라도 데이터가 다르면 둘의 해시값은 완전히 다르다.

Hashable은 Equatable을 왜 상속해야할까

Hashable은 Equatable 프로토콜을 상속받고 있는데 그 이유는 hashValue가 항상 unique하지 않기 때문이다.
hashValue가 같아서 해시 충돌이 일어날 가능성이 있기 때문에,
hashValue로만은 정확도가 떨어져서 추가로 동일한지 확인하는 Equatable이 필요한 것이다.

• hashValue로는 사용자가 찾는 객체에 근접할 수 있고,
• Equatable의 구현사항인 == 함수로는 hashValue가 고유값인지 식별한다.

자동으로 Hashable한 타입은 뭐가 있지

1. 스위프트 스탠다드 라이브러리 중 거의 다 이미 Hashable을 채택하고 있음

   따라서,, 따로 우리가 채택해주지 않아도 값을 비교할 때 ==를 사용할 수 있다.

• String, Integer, Float, Bool, Double

1. 커스텀 타입 중에서는

• 연관값이 없는 enum

커스텀 타입을 만약 Hashable을 채택하도록 하려면

이렇게 공식 문서에도 나와있듯이

두가지 경우가 있음

그냥 Hashable 프로토콜만 채택해주면 알아서 hash(into:) 구현해주는 케이스

• 모든 저장 프로퍼티가 Hashable한 struct
• 모든 연관값이 Hashable한 enum 인 경우는
  

이렇게 모든 저장 프로퍼티가 Hashable한 Int타입인 경우 Hashable만 채택하면 hash(into:) 구현하지 않아도 자동으로 생김

그 외의 경우에는 두가지를 구현해줘야 하는데

1. == 함수 ← Equatable 프로토콜을 따라야해서
2. hash(into:) 함수 ← Hashable 프로토콜을 따라야해서

예를 들어 위의 struct를 class로 바꿨더니 그냥 Hashable만 채택해서는 안됐다
== 랑 hash(into:)를 구현해줘야 했음

왜 커스텀 타입은 Hashable을 기본적으로 채택하고 있지 않을까?

같은 이름과 생일을 가졌다고 해서 두 사람이 같은 사람이라는 보장이 없는 것처럼

타입을 구현한 사람이 특정 타입이 같다고 여겨질 수 있는 속성을 직접 구현해야한다.

여기서는 id를 기준으로 판단한다.

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.id == rhs.id
}

Stack Overflow에서 질문자가 hashValue를 사용해놓고 "나 Equatable 구현했는데 왜 중복된 값이 나와?" 라고 질문했는데,

Equatable을 구현할 땐 hashValue가 아니라 모델 타입의 value중 하나가 동일한지로 판단해야한다고 한다.

Reference

https://developer.apple.com/documentation/swift/hashable
https://ko.wikipedia.org/wiki/해시_함수
https://zeddios.tistory.com/498
https://stackoverflow.com/questions/31664159/how-to-handle-hash-collisions-for-dictionaries-in-swift
https://heartbeat.comet.ml/diving-into-data-structures-in-swift-sets-e972c5a26b72