[iOS] - Hashable

in APP on iOS, Hashable, Hash


개발하다보면 Hashable 프로토콜을 정말 많이 사용하게 된다. Hashable과 옵셔널 값을 같이 사용하면서 생긴 궁금증도 있고, Hashable을 굉장히 많이 사용하지만 깊이 알고 있지 않은 상태로 사용하고 있는 것 같아 Hashable 이 어떤 프로토콜인지 좀 더 자세히 공부해보려고 한다.

Hashing

Hasing(해싱)은 주어진 key나 문자열을 다른 값으로 변환시키는 작업이다. 해싱을 통해 고정 길이의 더 짧은 key, value로 표현되고, 이 key-value를 사용해서 원래의 값을 더 쉽고 빠르게 찾을 수 있다.

해싱은 데이터를 특정 정수 값으로 매핑하는 함수, 알고리즘을 사용한다. 즉 hash function을 사용해서 데이터에서 새로운 값을 만드는 것이다. 이 새로운 값을 hash value, 아니면 단순히 hash라고 한다.

image

해싱을 사용한 방법 중 하나로 흔히 hash table을 본 적이 있을 것이다. Hash table은 키-값 쌍을 저장해서 이를 인덱스를 통해 접근할 수 있게 한다.

image

위 그림을 보면 개발자가 저장하고 싶은 데이터의 (키, 값) 쌍이 있고, 키를 hash function의 입력값으로 해서 나온 출력값 hash를 hash table의 인덱스로 사용하고 있다.

정리하자면 hashing은 데이터를 새로운 값으로 변환시키는 작업이고, 이 새로운 값을 hash라고 한다.

Hashable

image

Hashable은 프로토콜로, Hasher를 통해 정수 hash 값으로 해싱될 수 있는 타입을 의미한다.

image

위에서 그린 그림을 Hashable을 대입해서 다시 그려봤다. Hashable한 타입은 Hasher를 통해 정수 hash 값으로 변환될 수 있다.

image

Hashable은 Equatable 프로토콜을 준수한다. Equatable도 프로토콜로, 값이 같은지 여부를 비교할 수 있는 타입이다.

특징

  • 집합, 딕셔너리 키로 Hashable 프로토콜을 따르는 타입을 사용할 수 있다.
  • 표준 라이브러리의 많은 타입이 Hashable을 준수한다. (문자열, 정수, 실수, Bool, 집합 등)
  • 개발자가 생성한 커스텀 타입도 hashable할 수 있다.
  • 값을 hasing한다 : Hasher 타입의 hash function에 필요한 요소들을 제공해서 해시 값을 생성한다는 의미다.

Hash 값 제공하기, hash(into:)

image

hash(into:) 는 프로토콜을 채택하는 타입에서 꼭 구현해야 하는 required 인스턴스 메서드다. hash(into:)는 필수적인 요소들의 값을 주어진 hasher에 전달해서 해싱하는 함수다.

image

파라미터의 hasher는 인스턴스의 요소들을 결합시킬 때 사용하는 hasher다. 이때 해싱에 사용되는 요소들은 == 메서드에서 값을 비교하기 위해 사용했던 요소들과 같은 요소가 되어야 한다.

Hasher

hash(into:) 메서드에서 사용하는 hasher의 타입은 Hasher다.

image

Hasher는 집합과 딕셔너리에 사용되는 hash 함수로, 구조체다.

Hasher는 임의의 byte sequence를 정수 hash 값으로 mapping할 때 사용된다. Mutating combine 메서드를 사용해서 hasher에 데이터를 추가로 줄 수도 있다.

var hasher = Hasher()
hasher.combine(23)
hasher.combine("Hello")
// 여기에서는 finalize 메서드를 사용했는데, `hash(into:)` 메서드를 사용할 때는 절대로 hasher에 finalize를 사용하면 안된다고 공식문서에 나와있다.
let hashValue = hasher.finalize()

image

그림으로 다시 정리하면 위와 같다.

  • Hashable 프로토콜을 채택해서 우리가 사용하고자 하는 타입이 Hashable하게 한다.
  • 타입 내부에 hash(into:) 메서드를 구현해서 Hasher 타입 hash function에 추가적인 값을 제공하고, hashing 한다.
  • 결과적으로 우리는 정수 hash 값을 갖게 된다.

Automatically provided Hashable protocol conformance

Swift는 여러 경우에 자동으로 Hashable protocol conformance를 제공한다. 이게 무슨 말이냐면 이 문법적 구현(synthesized implementation)을 사용해서 프로토콜 요구사항을 구현하기 위해 반복적인 boilerplate 코드를 작성할 필요가 없게 된다는 뜻이다.

image

1. Associated valuer가 없는 Enum

enum HashableEnum1 {
    case one
    case two
}

let hashableEnum1 = HashableEnum1.one

if let _ = hashableEnum1 as? AnyHashable {
    print("hashableEnum1 is hashable")
    // hashableEnum1 is hashable 를 출력한다.
}

이 경우 enum에 : Hashable라고 따로 명시하지 않아도 자동으로 hashable한 enum이 된다.

2. 모든 저장 프로퍼티가 Hashable한 Struct

struct HashableStruct {
    var name: String
}

let hashableStruct = HashableStruct(name: "Hi")

if let _ = hashableStruct as? AnyHashable {
    print("hashableStruct is hashable")
} else {
    print("not hashable")
}

// not hashable이 출력된다.

헷갈리지 말아야 할게, 조건을 만족할 경우 자동으로 Hashable하게 되는 것이 아니다. 프로토콜 요구사항을 만족시키기 위해 작성해야 하는 코드를 작성하지 않을 수 있다는 것이다.

image

위 코드에서는 Hashable을 채택하는 구조체, 클래스를 정의했다. 클래스의 경우에만 “Type ‘HashableClass’ does not conform to protocol ‘Equatable’” 라는 에러가 뜨는 걸 확인할 수 있는데, 이는 Hashable 프로토콜이 요구하는 메서드를 내부에 구현하지 않았기 때문이다.

image

컴파일 에러가 나지 않게 하려면 위와 같이 hasher(into:), == 함수를 다 구현해야 한다. 여기에서 말하는 “모든 저장 프로퍼티가 Hashable한 struct인 경우 Hashable의 문법적인 구현을 사용할 수 있다” 라는 말은 모든 저장 프로퍼티가 Hashable한 구조체가 명시적으로 Hashable 프로토콜을 채택한다고 했을 때, hasher(into:), == 함수를 구현하지 않아도 된다는 말이다.

다시 정리하면 Hashable 프로토콜을 채택한 구조체에서 모든 저장 프로퍼티가 Hashable하면 Swift가 자동으로 hash(into:) 메서드를 생성하기 때문에 아래와 같이 코드를 작성할 수 있다.

struct HashableStruct: Hashable {
    var name: String
}

let hashableStruct = HashableStruct(name: "Hi")

if let _ = hashableStruct as? AnyHashable {
    print("hashableStruct is hashable")
} else {
    print("not hashable")
}

// hashableStruct is hashable 출력

3. 모든 Associated type이 Hashable한 enum

2번 케이스와 비슷하다.

enum HashableEnum2: Hashable {
    case one(name: String)
    case two
}

if let _ = HashableEnum2.one(name: "Hi") as? AnyHashable {
    print("hashable")
}

// hashable 출력

추가로, 위 조건을 만족하지 않는 enum이나 struct은 당연하게도 Hashable의 문법적 구현(synthesized implementation)을 제공받을 수 없기 때문에 아래와 같이 명시적으로 hash(into:)와 == 메서드를 구현해줘야지만 컴파일 에러가 나지 않는다.

class Cat {}

enum AnotherEnum: Hashable {
    case one(cat: Cat) // Cat은 Hashable하지 않다.
    case two
    
    func hash(into hasher: inout Hasher) {
        switch self {
        case .one(_):
            hasher.combine("cat")
        case .two:
            hasher.combine(2)
        }
    }
    
    static func == (lhs: AnotherEnum, rhs: AnotherEnum) -> Bool {
        lhs.hashValue == rhs.hashValue
    }
}

Optional and Hashable

Hashable을 더 공부하게 된 계기다. 옵셔널 값을 해싱할 수 있을까?

image

Hashable Apple 공식 문서를 보면 하단에 Hashable 프로토콜을 채택하는 수많은 타입들이 나와있는데, Optional도 여기 포함되어 있다. 옵셔널의 Wrapped가 Hashable할 때 Hashable하다.

Swift github을 보면, Optional은 아래와 같이 enum으로 구현되어 있다.

image

그리고 Swift 4.2에서는 Optional: Hashable을 아래와 같이 구현하고 있다.

extension Optional: Hashable where Wrapped: Hashable {
  //  ...
  public func hash(into hasher: inout Hasher) {
    switch self {
    case .none:
      hasher.combine(0 as UInt8)
    case .some(let wrapped):
      hasher.combine(1 as UInt8)
      hasher.combine(wrapped)
    }
  }
}
  • .none : hash 값은 0가 된다.
  • .some(wrapped) : wrapped를 hasher에 섞어서 정수 hash 값을 갖는다.

그래서 optional은 Wrapped가 Hashable할 때 Hashable하다. 따라서 optional 값을 해싱할 때 사용할 수 있다.

struct HashableStruct: Hashable {
    var hashableOptional1: String? = "Hi"
    var hashableOptional2: String? = nil
    var hashableOptional3: Optional<String> = nil
}

위 코드의 경우 구조체의 저장 프로퍼티가 모두 hashable하기 때문에 hash(into:) 메서드를 따로 작성하지 않아도 된다.

image

hasher.combine(어떤 값)에서 어떤 값은 hashable해야 한다. 그런데 hashable하지 않은 옵셔널을 집어넣었기 때문에 컴파일러 에러가 뜨는 것이다. 따라서 에러를 안 뜨게 하려면 Cat 클래스를 Hashable하게 만들 수도 있고, hasher(into:) 메서드 내에서 임의로 hashing하는 로직을 추가로 구현해도 될 것이다.

class Cat: Hashable {
    func hash(into hasher: inout Hasher) {
    }
    
    static func == (lhs: Cat, rhs: Cat) -> Bool {
        return true
    }
}

struct HashableStruct: Hashable {
    var hashableOptional1: String? = "Hi"
    var hashableOptional2: String? = nil
    var hashableOptional3: Optional<String> = nil
    var notHashableOptional: Cat? = Cat()
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(hashableOptional1)
        hasher.combine(hashableOptional2)
        hasher.combine(hashableOptional3)
        
//        방법 1: 임의로 hashing 로직 추가. 좋은 예시는 아닌 것 같다.
//        if let notHashableOptional = notHashableOptional {
//            hasher.combine(1)
//            hasher.combine("cat")
//        } else {
//            hasher.combine(0)
//        }
        
//        방법 2: Cat이 Hashable 프로토콜을 준수하게 한다.
        hasher.combine(notHashableOptional)
    }
    
    static func == (lhs: HashableStruct, rhs: HashableStruct) -> Bool {
        lhs.hashValue == rhs.hashValue
    }
}
  • 참고
  • https://www.techtarget.com/searchdatamanagement/definition/hashing
  • https://developer.apple.com/documentation/swift/hashable
  • https://docs.swift.org/swift-book/LanguageGuide/Protocols.html
  • https://github.com/apple/swift/blob/7123d2614b5f222d03b3762cb110d27a9dd98e24/test/IRGen/swift3-metadata-coff.swift
  • https://stackoverflow.com/questions/53218315/how-can-i-make-optionals-hashable-in-xcode-9-4