Swift Hashable Protocol

in Swift on Basic

Hashable은 프로토콜이다.

Hash?

자료구조 시간에 해쉬(hash)의 개념에 대해서 배운다. 일반적으로 Hash function 이라는 알고리즘 접근을 통해 데이터 마다 고유의 숫자를 설정하여 탐색등에 효율적으로 데이터를 접근하기 위함이다.( O(1) 만에 원하는 데이터를 탐색 가능) 자세한 내용은 Gaki-CS-Study 에 정리를 해놓았다.

이 hash 기능을 swift 내부에서 프로토콜로 제공을 하고 있는데 사용법과 특징에 대해서 알아보자

Swift Hashable Protocol

Swift에서 딕셔너리는 Dictionary<KeyType, ValueType> 형태로 쓰인다. 여기서 제약사항은 반드시 KeyType은 해쉬가능한 타입이어야 한다.(Hashable) 즉, 그 자체로 유일하게 표현이 가능한 방법을 제공해야한다는 말이다.

스위프트의 기본 타입으로 제공되는 String, Integer, Floating-point, Boolean 등과 같은 Standard library에 속한 많은 타입들은 Hashable 프로토콜을 준수한다. 또한 enum역시 해쉬가능하므로 이에 해당한다. 게다가 Set 은 오직 Hashable 한 것만 들어가야하기 때문에 기본적으로 해시값을 제공한다.

또한 자신만의 사용자 정의 타입도 hash가 가능할 수 있다. Hashable 프로토콜을 준수한다면 딕셔너리의 키나 세트로 활용할 수 있다는 말이다.

Hashable 프로토콜을 준수하는 모든 타입의 인스턴스는 hashValue 라는 정수형 프로퍼티 를 갖고 있으며 이 값은 각각의 인스턴스를 식별하는 값이 된다. 그렇기 때문에 반드시 하나만 존재해야하는 딕셔너리의 key 값이나 중복된 값은 허용하지 않는 자료구조인 set에 들어가는 값들은 Hashable해야 한다는 것이다.

Hashable : 값이 중복이 되지 않고 특정 인스턴스를 식별할 수 있는 고유의 키 값을 가지는 모든 값들은 이 속성을 지켜야한다.

// 1.
var basicDic = [String: String]()

basicDic["Gaki"] = "iOS Developer"    // String, bool 모두 Hashable 을 준수하는 기본 타입

struct CustomType: Hashable {
    var property: Int
}
// 2.
var customDic = [CustomType: String]()  // 위에 CustomType 구조체 선언시 Hashable 프로토콜을 준수하게 선언했기때문에 딕셔너리 키값으로 사용할 수 있다.
  1. 기본 타입인 String은 Hashable 프로토콜을 준수하기 때문에 딕셔너리의 키값으로 사용할 수 있다.
  2. 사용자 지정인 CustomType 구조체는 Hashable 프로토콜을 준수하도록 선언하였기때문에 마찬가지로 딕셔너리 키값으로 사용할 수 있는 것이다.

만일 같은 타입의 두 인스턴스가 동일하다면 두 인스턴스의 해시 값 역시 같다. 하지만 그 역은 성립하지 않는다. 즉, 두 인스턴스의 해시 값이 같다고 두 인스턴스는 같은것이 아니다

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

let grid1 = GridPoint(x: 3, y: 3)
let grid2 = GridPoint(x: 3, y: 3)

print(grid1.hashValue == grid2.hashValue)       // true

중요

hash 값은 프로그램 실행에 따라 동일하지 않을 수도 있다. 그러므로 추후에 사용을 위해 해시 값을 저장하는 행위는 하면 안된다.

Conforming to the Hashable Protocol

사용자 정의 타입을 딕셔너리의 Key나 Set에서 사용하기 위해서는 Hashable 프로토콜을 준수해야한다. Hashable 프로토콜은 Equatable 프로토콜을 상속받는다. 그렇기 떄문에 이 두 프로토콜의 요구 사항을 모두 충족시켜야 한다.

  • 사용자 정의 타입은 선언부에 Hashable 을 작성해주어 해당 프로토콜을 준수한다 명시해야한다.
  • 구조체 : 내부의 저장 프로퍼티가 모두 Hashable 프로토콜을 준수해야한다,
  • 열거형: 연관 값의 타입이 Hashable 프로토콜을 준수해야한다.

참고

Swift 4.1 버전 이전에는 Hashable 프로토콜을 준수하기 위해서는 hashValue 값과 == 연산자를 다음과 같이 직접 구현해야한다.

// Swift 4.1 ver 이하 Hashable 작업
struct GridPoint {
    var x: Int
    var y: Int
}

extension GridPoint: Hashable {
    var hashValue: Int {
        return x.hashValue ^ y.hashValue &* 16777619
    }

    static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
}

hashValue 값을 4.1 버전 이상부터는 컴파일러가 자동으로 구현하여 제공하고 있기 때문에 이를 설정 해줄 필요도 없다. 하지만 사용자가 여전히 이를 정의할 수 는 있다.

Class는 컴파일러가 제공하지 않는다!

클래스의 경우 컴파일러가 자동으로 구현해주지 않기 때문에 사용자가 위의 코드 처럼 직접 구현해주어야한다

class Country {
    let name: String
    let capital: String
    var visited: Bool
    
    init(name: String, capital: String, visited: Bool) {
        self.name = name
        self.capital = capital
        self.visited = visited
    }
}

extension Country: Equatable {
    static func == (lhs: Country, rhs: Country) -> Bool {
        return lhs.name == rhs.name &&
            lhs.capital == rhs.capital &&
            lhs.visited == rhs.visited
    }
}

// deprecated 되었기 때문에 hash(into:) 함수를 사용
//extension Country: Hashable {
//  var hashValue: Int {
//    return name.djb2hash ^ capital.hashValue ^ visited.hashValue
//  }
//}

extension Country: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(name.djb2hash )
        hasher.combine(capital.hashValue)
        hasher.combine(visited.hashValue)
    }
}

extension String {
    var djb2hash: Int {
        let unicodeScalars = self.unicodeScalars.map { $0.value }
        return unicodeScalars.reduce(5381) {
            ($0 << 5) &+ $0 &+ Int($1)
        }
    }
    
    var sdbmhash: Int {
        let unicodeScalars = self.unicodeScalars.map { $0.value }
        return unicodeScalars.reduce(0) {
            Int($1) &+ ($0 << 6) &+ ($0 << 16) - $0
        }
    }
}

위의 코드는 Country class에 각 프로퍼티에 hash 값을 적용 시킨 것이다. 여기서 유심히 봐야할 것은 String과 Int를 extension 해서 또 내부에서 Hash 값을 계산해서 반환하는 프로퍼티를 선언했고 또 이 Hash 값을 Country 클래스에서 사용하고 있다.

이전에는 hashValue 를 직접 프로퍼티로 선언해서 값을 설정해주어서 반환해주었지만 지금은 deprecated 되어서 hash(into:) 메서드를 제공하고 있어 이를 통해 hash를 계산하는 함수를 작성 해주면 된다.

Hash Algorithm 을 잘 설계하자

hashValue의 로직을 작성할 때는 사용자 정의 타입을 이루고 있는 데이터들에 따라 적절한 해시 알고리즘을 사용해야한다

해시 알고리즘이란? : 앞에서 데이터들을 특정 숫자로 표현하기 위해 HashFunction 을 설정하여 작업하는 것을 말하며 데이터 간의 해싱을 하였을때 중복(충돌)을 최소화 하는 것이 목적이고 이에 대한 다양한 알고리즘 기법이 존재한다

만약 해시 알고리즘을 잘못 설계하여 데이터 끼리의 충돌(collision) 이나 overflow 가 발생하게 되면 해시의 가장 큰 장점인 O(1) 만에 빠른 탐색이 불가능 하게 되고 결국 배열 탐색과 동일한 작업이 되므로 성능이 떨어지게 된다.

Reference




© 2020. by Gaki

Powered by gaki