Hashable

오늘은 Hashable에 대해서 알아보자.
처음에 듣자마자 Hash...able?ㅋㅋㅋㅋ이런 느낌였고...ㅋㅋㅋ알고 보니 맞았고...ㅋㅋㅋ
오늘도 공식 문서따라서 쭉쭉 봐보자.

Hashable

우선 Hashable은 프로토콜이다.

A type that can be hashed into a Hasher to produce an integer hash value.

정수 해시 값을 생성하기 위해 Hasher로 해시할 수 있는 타입이라고 나온다.
흐음... 해시 값은 뭐고 Hasher는 뭘까?

Hash

해시 값이라고 구글링하면 위키백과에 다음과 같이 나온다.

• 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
• 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.

위의 그림처럼 어떠한 데이터를 Hash 함수에 넣게 되면 어떠한 값을 반환해주는데 이걸 해시 값이라고 한다.

Hasher

그렇다면 Hasher는 뭘까?

Defines the Hasher struct, representing Swift's standard hash function.
Swift의 표준 해시 함수를 나타내는 Hasher struct

Swift Hasher 코드에는 위와 같이 나와 있다.
Hasher는 해시 값을 만드는 해시 함수가 있는 struct이다.

공식 문서에는 다음과 같은 주의점이 나와 있다.

Do not save or otherwise reuse hash values across executions of your program. Hasher is usually randomly seeded, which means it will return different values on every new execution of your program. The hash algorithm implemented by Hasher may itself change between any two versions of the standard library.

프로그램 실행하면서 해시 값을 저장하거나 재사용하지 말아라!
Hasher는 일반적으로 무작위로 생성되고, 프로그램을 새로 실행할 때마다 다른 값을 반환한다.
Hasher에서 구현한 해시 알고리즘은 표준 라이브러리의 버전마다 변경될 수 있다.

흐음... 그렇군용ㅋㅋㅋㅋㅋ

---

Hashable에 대해 좀 더 알아보자.

Hashable 프로토콜을 준수하는 모든 유형은 set 또는 dictionary 키로 사용할 수 있다.
그리고 표준 라이브러리의 많은 타입들이 Hashable을 준수하고 있다.

• Hashable을 준수하고 있는 타입: String, Integer, floating-point, Boolean
• Optional과 Array, Range들은 argument들이 동일하게 구현될 때 자동으로 Hashable이 된다.

custom 타입에도 Hashable을 준수하도록 할 수 있다.
associated value 없이 enum을 정의하면 자동으로 Hashable을 준수한다.
hash(into:) 메서드를 구현한다면 다른 custom 타입도 Hashable을 준수할 수 있다.
저장 property들이 모두 Hashable한 구조체, 모두 Hashable한 enum 타입을 가진 enum이라면 컴파일러가 hash(into:) 메서드를 자동으로 제공한다.

---

Hashable 준수하기

set이나 dictionary의 key에 custom 타입을 사용하려면 Hashable을 준수해야 한다.
Hashable 프로토콜은 Equatable 프로토콜에서 상속되므로 Equatable의 요구 사항도 충족해야 한다.
(갑자기 Equatable..?? Equatable에 대해서는 아래에서 알아보자.)

• 모든 저장 property가 Hashable을 준수하는 struct
• 모든 associated value가 Hashable을 준수하는 enum

위의 경우에는 Hashable을 채택한다고 명시해두면 컴파일러가 자동으로 필요 사항들을 더해준다.
(associated value가 없는 enum은 Hashable을 채택한다고 명시하지 않아도 Hashable을 준수 중이다.)

Hashable을 채택한 custom 타입이거나 위의 경우에 해당하지 않지만 Hashable을 채택한 경우에 Hashable을 준수하려면 타입에서 hash(into:)를 구현해야 한다.

hash(into:)를 구현할때 해싱해야 하는 값을 Hasher 인스턴스에서 combine(_:)을 호출해야 한다.
(위에서 Hasher는 해시 값을 만드는 해시 함수가 존재하는 struct라고 했다.)

Hashable은 Equatable 프로토콜을 상속하고 있으므로 Hashable을 준수하고 있다는 것은 Equatable도 준수하고 있다는 말이다.
즉, hash(into:)를 구현할때에는 Equatable의 요구사항도 구현해주는 것이 좋다.

struct GridPoint {
    var x: Int
    var y: Int
}

좌표를 의미하는 GridPoint custom 타입이 있다.
내가 이 좌표를 이전에 사용했는지 확인하고 싶다.
보통 이럴때 중복이 불가한 Set을 사용하는데 Set은 Hashable을 준수하는 타입만 insert할 수 있다.
그렇다면 GridPoint이 Hashable을 준수하도록 해보자.

struct GridPoint {
    var x: Int
    var y: Int
}

extension GridPoint: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }
    
    static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
}

hash(into:)는 GridPoint의 x, y를 해시값에 추가해준다.

hash(into:)를 구현해서 Set에 사용할 수 있도록 GridPoint를 만들었는데 뭔가 찝찝하다.

위에서 어떤 조건일때에는 Hashable을 채택한다고 명시하기만 해도 컴파일러가 알아서 해시 값을 만들어 준다고 했다.

모든 저장 property가 Hashable을 준수하는 struct
모든 associated value가 Hashable을 준수하는 enum

GridPoint는 우선 struct이다.
x, y property를 확인해 보면 저장 property이고, Int이므로 Hashable을 준수하고 있다.

그렇다면 hash(into:)를 구현하는 것이 필요할까?

struct GridPoint: Hashable {
    var x: Int
    var y: Int
}

❗️ 이렇게 Hashable을 채택한다고 명시만 해줘도 컴파일러가 알아서 해준다!
(위의 예시는 공식 문서에 나와 있는 예시인데 업뎃이 안된건지 머르겠음...ㅋㅋ)

---

참고

Hashable에 대해서 알아가면서 combine(_:)이나 Equatable 같은 부분들을 추가로 다뤄보자.

combine(_:)

공식 문서를 확인해 보자.
(combine 구글링하는데 자꾸 프레임워크만 나왔다...ㅋㅋ)

설명은 굉장히 간단하다.
combine(_:)은 입력한 값을 해시 값과 혼합해 주는 메서드이다.

그렇다면 위의 코드로 생각해보자.

func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }

좌표를 중복되지 않게 사용하기 위해 GridPoint에 Hashable을 준수하도록 했다.
그렇다면 좌표를 중복되지 않게 하기 위해서는 x, y 두 값 모두 유일성이 보장되어야 하기 때문에 x, y 둘다 combine()한다.
즉, x와 y가 포함된 해시 값을 갖게 된다.

아래는 그냥 참고로 combine(_:)을 분석해봤다.ㅋㅋㅋㅋ
(그냥 알고 앞에서 공부했었던 것들을 적용해본 것뿐이지만...)

combine(_:)은 위와 같은 형태이다.
하나씩 봐보자.
Hasher는 struct이므로 Hasher 안의 property를 변경하는 combine(_:)에 mutating이 붙어 있다.
combine(_:)은 제네릭으로 구성되어 있고... 흠... 뒤에 보니 Hashable을 준수하고 있는 타입만 받겠다는 제약이 있다.

---

Equatable

공식 문서를 봐보자.

Equatable은 값이 같은지 비교할 수 있는 타입이다.

Equatable 프로토콜을 준수하는 타입은 ==연산자를 사용해 같음을 비교하거나 !=연산자를 사용해 같지 않음을 비교할 수 있다.
일부 sequence나 collection 작업들은 Equatable을 준수하면 더 간단해질 수 있다.
예를 들어 배열에 특정 값이 표함되어 있는지 확인하려면 같음을 확인하는 클로저를 사용하는 대신에 배열의 요소가 Equatable을 준수할 때 값 자체를 contains(_:) 메서드에 전달할 수 있다.

흠... 결국 말이 길었지만 Equatable은 ==/!=와 같은 연산자들을 사용해 값들을 비교할 수 있도록 해주는 프로토콜이고, 이를 준수한다면 값들을 비교하는 값을 쉽게 얻을 수 있다는 말인거 같다.

호오.... 재밌는 것은 Equatable도 Hashable과 같이

• 모든 저장 property가 Equatable을 준수하는 struct
• 모든 associated value가 Equatable을 준수하는 enum

이라면 Equatable을 채택한다고 명시하기만 해도 컴파일러가 알아서 해준다고 한다.

---

Hasher

Swift Hasher 코드에는 다음과 같은 설명이 있다.

Hasher can be used to map an arbitrary sequence of bytes to an integer hash value.
You can feed data to the hasher using a series of calls to mutating combine methods.
When you've finished feeding the hasher, the hash value can be retrieved by calling finalize()

Hasher는 임의의 byte sequence를 정수 해시 값으로 매핑하는데 사용한다.
combine메서드로 입력 받은 값을 해시 값에 더할 수 있다.
해시 값 생성이 끝나면 finalize()를 호출해 해시 값을 검색 할 수 있다.

Within the execution of a Swift program, Hasher guarantees that finalizing it will always produce the same hash value as long as it is fed the exact same sequence of bytes.
However, the underlying hash algorithm is designed to exhibit avalanche effects: slight changes to the seed or the input byte sequence will typically produce drastic changes in the generated hash value.

Hasher는 똑같은 byte sequence가 공급되는 한 항상 동일한 해시 값이 생성되도록 보장된다.
하지만 기본 해시 알고리즘은 눈사태 효과를 나타내도록 설계되어 있다.
시드 또는 input byte sequence를 약간이라도 변경되면 일반적으로 생성된 해시 값이 크게 변경된다.

눈사태 효과가 뭐지..?

위키백과에 따라면 어떤 암호 알고리즘이 입력값에 미세한 변화를 줄 경우 출력값에 상당한 변화가 일어나는 성질을 의미한다고 한다.

LOVE, LIVE, LIFE는 4글자이고 모두 L로 시작하고 E로 끝난다.
언뜻 봐서는 3단어 모두 비슷하게 생겼으니 해시 값도 비슷하지 않을까라고 생각할 수 있다.
하지만 오른쪽 문자열은 3단어가 굉장히 다르게 생겼다.
이런거를 눈사태 효과라고 한다.
입력은 살짝 다르지만 출력은 많이 다른!ㅋㅋㅋ

오호.... 그렇다면 정리를 해보자.

• Hasher는 임의의 byte sequence를 정수 해시 값으로 매핑하는데 사용한다고 했다.
  -> LOVE, LIVE, LIFE(byte sequence)가 Hasher를 통해 0, 1, 2(정수 해시 값)으로 매핑되었다.

• 정수 해시 값으로 매핑될때 Hasher의 combine(_:)이 사용된다.
  -> combine(_:)에는 해시 값으로 사용하고 싶은 값(즉, 유일성을 갖도록 하고 싶은 값)을 주입한다.

• Hasher는 똑같은 byte sequence가 공급되는 한 항상 동일한 해시 값이 생성되도록 보장한다.
  -> 즉, LOVE에 관한 해시 값은 항상 동일하다.
  -> finalize()를 호출해 해시 값을 검색할 수 있으므로 LOVE의 finalize()는 항상 같은 값을 반환한다.

흠... 그렇다면 해시 값을 만듬으로써 Set과 Dictionary Key가 유일성을 갖도록 했다.
(근데 사실 해시를 이용한다고 충돌이 아예 없는건 아님, 그래서 그런거를 우회하도록 하는 방법들이 있음... 빈방 찾기? 이런 이름였던거 같은데....이중 해시도 있었던거 같고... 방법이 3개쯤 있었던거 같은데...ㅋㅋ)

같은 byte sequence에 같은 해시 값을 반환함으로써 O(1)의 복잡도로 Set, Dictionary에 접근할 수 있게 되었다.

---

그렇다면 왜 Hashable은 Equatable을 상속 받을까?

Set, Dictionary의 key로 사용하기 위해서는 Hashable을 준수하고 있어야 한다.
Set, Dictionary의 Key는 중복을 허용하지 않는다.
즉, Set, Dictionary는 Key가 중복인지 아닌지를 구별할 수 있어야 하는데 이때 Equatable을 사용한다.

Hashable이 Equatable을 상속하고 있는 이유는 해시 값은 각각 타입의 인스턴스를 식별하는 값으로 유일성을 가지고 있어야 한다.
따라서 해시 값이 유일한 값인지를 비교해야하기 때문에 Equatable 프로토콜을 상속 받아 값을 비교할 수 있도록 하고 있다.

---

마무리

오늘은 Hashable에서 시작해서 Equatable, Hasher에 대해서 알아봤다.
역시... 금방 끝날줄 알았는데 오늘도 오래 걸렸다ㅋㅋㅋ
그럼 이만👋