Hashable / Hasher

작성자 : Mattt 번역자 : 김필권 2018년 8월 13일

이 기사는 다음과 같이 번역되었습니다 :: English; español; français; 中文

애플 스토어의 지니어스 바를 이용할 때는 정해진 날의 정해진 시간에 컨시어지에 가야합니다. 컨시어지는 우리를 큐에 쌓고 스툴에 앉혀놓은 후에 각자를 알아볼 수 있는 메모를 작성합니다.

익명의 전 리테일 직원의 보고에 따르면 이 메모에는 엄격한 가이드라인이 있다고 합니다. 고객의 외모에 대한 언어는 사용할 수 없습니다. 나이, 성별, 민족성, 키, 심지어 머리 색깔까지요. 대신에 모든 고객들은 그들의 옷으로 설명됩니다. “검정 터틀넥, 청바지 그리고 안경을 낀 사람” 처럼요.

애플이 고객을 설명하는 방식은 프로그래밍의 해싱 함수와 많은 공통점을 가지고 있습니다. 훌륭한 해싱 함수의 일관성과 계산하기 쉬운 점 그리고 우리가 찾는 것을 빠르게 찾을 수 있다는 점이 동일합니다. 여러분도 동의할거라 믿습니다!

오늘의 주제는 Hashable과 새로운 타입인 Hasher입니다. 이 둘은 스위프트의 가장 사랑받는 두 컬렉션 클래스인 Dictionary와 Set의 기본 기능으로 구성되어 있습니다.

우리에게 객체의 list가 있고 또 다른 것과 같은지 비교할 수 있다고 해봅시다. 목록에서 특정 객체를 찾으려면 그 객체를 찾을때까지 모든 요 를 반복해야 합니다. 배열에 요소가 추가될수록 검색에 드는 평균 시간이 (O(n))와 같은 선형으로 상승한다는 것을 의미합니다.

배열 대신에 set에 그 객체들을 저장한다면 이론적으로 상수 시간(O(1))에 검색이 가능합니다. 즉, 10개의 요소를 가진 세트에서 검색하는 데 걸리는 시간이 10,000개의 요소를 가진 세트에서 검색하는 것과 동일하다는 말입니다.^* 어떻게 그럴 수 있을까요? 객체를 순차적으로 저장하는 대신에 세트는 해시를 객체의 컨텐츠에 기반한 인덱스로 계산합니다. 세트에서 객체 검색을 할 때 우리는 새로운 해시를 계산하고 그 곳에 있는 객체를 보는 것과 똑같은 작업을 하는 것입니다.

^* 두 객체가 같은 값을 가지고 있지만 같지는 않을 때는 해시 충돌을 일으킵니다. 삽입할 때 충동일 발생하면 그것들은 그 주소에 리스트의 형태로 저장됩니다. 객체간의 충돌 비율이 점점 높아지면 높아질수록 해시 컬렉션의 퍼포먼스도 선형으로 상승합니다.

Hashable

Swift에서 Array는 리스트에 대한 표준 라이브러리를 제공하고 Set는 세트를 담당하고 있습니다. 객체를 Set에 저장하기 위해서는 먼저 타입이 Hashable이 될 수 있어야 합니다. (익스텐션인 Equatable도 있습니다) Swift 표준 map 인터페이스인 Dictionary는 연관된 Key 타입에 비슷한 제약을 가지고 있습니다.

Swift의 이전 버전에서는 커스텀 타입을 Set이나 Dictionary에 저장하기 위한 조건을 충족시키기 위한 상용구 코드가 필요했었습니다.

다음과 같이 Color 타입이 있다고 해보겠습니다. 이 타입은 빨강, 초록, 그리고 파랑을 8비트 값으로 표현합니다.

struct Color {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
}

Equatable을 만족하기 위해서는 == 연산자에 대한 구현을 제공해야 합니다. Hashable을 만족하기 위해서는 hashValue 속셩을 계산하는 구현을 제공해야 합니다.

// Swift < 4.1
extension Color: Equatable {
    static func ==(lhs: Color, rhs: Color) -> Bool {
        return lhs.red == rhs.red &&
               lhs.green == rhs.green &&
               lhs.blue == rhs.blue
    }
}

extension Color: Hashable {
    var hashValue: Int {
        return self.red.hashValue ^
               self.green.hashValue ^
               self.blue.hashValue
    }
}

대부분의 개발자들에게 Hashable을 구현하는 것은 과속 방지턱같아서 실제로는 간단하게 XOR를 적용하고 말았었습니다.

이 방법이 좋지 않았던 이유 중 하나는 해시 충돌 비율이 높았다는 것입니다. XOR은 제시된 수의 순서에 상관없이 결과가 동일하기 때문에 시안과 노랑처럼 다른 색끼리도 해시 충돌이 일어났습니다.

// Swift < 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)

cyan.hashValue == yellow.hashValue // true, collision

오랜 시간동안 이것은 문제가 되지 않았었습니다. 현대 컴퓨터들은 매우 강력해서 많은 구현적인 상세사항이 잘못돼서 퍼포먼스 저하가 있더라도 알기 어려웠습니다.

그러나 이것은 세부 사항이 중요하지 않다는 말이 아닙니다. 세부 사항은 종종 대단히 중요합니다.

Hashable 적합성의 자동 합성 (Automatic Synthesis of Hashable Conformance)

Swift 4.1에서는 컴파일러가 자동으로 Equatable과 Hashable 프로토콜에 대한 적합성을 자동으로 합성합니다.

개발자 생산성을 크게 향상시키는 것 외에도 코드베이스의 사이즈를 엄청나게 줄일 수 있습니다. 예를 들면 우리의 Color 예제가 이전의 3분의 1 수준으로 줄어듭니다.

// Swift >= 4.1
struct Color: Hashable {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
}

이러한 애매하지 않은 발전에도 불구하고 구현 방식에 대한 언어적인 질문이 여전히 존재합니다.

Tony Allevato의 Swift 발전 제안인 SE-0185: Synthesizing Equatable and Hashable conformance에서 해싱 함수에 대한 메모를 제공합니다.

해시 함수의 선택은 디자인적으로 고정된 부분이 아닌 구현의 세부 사항으로 남아있습니다. 따라서 사용자는 행동의 특정 특성에 의존해서는 안됩니다. 가장 비슷한 구현은 표준 라이브러리의 _mixInt 함수일 것입니다. 각 멤버들이 해시 값을 가지고 exclusive-or(^)로 그것들은 합칩니다. 이는 Collection 타입이 오늘날 해시되는 방식과 동일합니다.

운좋게도 Swift가 해시 함수에 정착하는 것이 길지 않을 것이라고 생각합니다. 그리고 바로 다음 버전에서 대답을 얻게되었습니다.

Hasher

Swift 4.2는 Hashable을 개량해서 Hasher 타입과 해싱 함수의 새로운 세계에 적응하는 방법을 소개합니다.

또 다른 Swift 발전 제안인 SE-0206: Hashable Enhancements를 보겠습니다.

훌륭한 해시 함수가 있다면 간편한 조회, 삽입 또는 삭제는 평균적인 상수 시간이 걸립니다. 하지만 해시 함수가 적절한 데이터를 사용하지 않으면 연산에 걸리는 예상 시간은 테이블에 저장된 요소의 수에 비례합니다.

Karoy Lorentey와 Vincent Esche가 말했듯이, Set과 Dictionary같은 해시 기반 컬렉션의 큰 그림은 값을 상수 시간에 찾을 수 있게 하는 것입니다. 만약 해시 함수가 값의 균등한 분포를 생성하지 않으면 이러한 컬렉션은 효율적으로 링크드 리스트가 됩니다.

Swift 4.2는 의사 난수(pseudorandom) 함수의 가족인 SipHash에 기반을 두고 해싱을 구현했습니다. 그 중에서도 SipHash-1-3 and SipHash-2-4에 중점을 뒀고, 이 글의 1,2 라운드는 메시지 블럭마다의 해싱 단계를 말하고 3,4 라운드는 각각의 마무리를 설명합니다.

이제 Hashable을 구현하는 방식을 커스텀하고 싶으시면 hash(into:) 메소드를 hashValue 대신에 덮어씌우면 됩니다. hash(into:) 메소드는 Hasher 오브젝트를 참조로 전달합니다. 여러분은 combine(_:)을 호출하여 타입의 필수 상태 정보를 추가합니다.

// Swift >= 4.2
struct Color: Hashable {
    let red: UInt8
    let green: UInt8
    let blue: UInt8

    // 컴파일러에 의해 합성됨
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.red)
        hasher.combine(self.green)
        hasher.combine(self.blue)
    }

    // 프로토콜 익스텐션의 기본 구현
    var hashValue: Int {
        var hasher = Hasher()
        self.hash(into: &hasher)
        return hasher.finalize()
    }
}

로우 레벨의 비트 조작 세부 정보를 추상화는 것으로 개발자들은 자동으로 Swift의 내장 해싱 함수에서 원래의 XOR 기반 구현에서 우리가 얻던 충돌을 재현하지 않는 추가적인 이점을 얻게되었습니다.

// Swift >= 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)

cyan.hashValue == yellow.hashValue // 거짓, 충돌 없음

해시 함수 커스터마이징하기

기본적으로 Swift는 유니버셜 해시 함수를 사용해서 바이트 시퀀스를 단일 정수로 줄입니다.

하지만 우리는 해시 함수를 재단해서 우리의 도메인에 맞게 발전시킬 수 있습니다. 예를 들어 체스나 고같은 보드 게임을 플레이하기 위해 프로그램을 작성중이라면 게임의 상태를 빠르게 저장하기 위해 Zobrist hashing를 구현할 수 있습니다.

해시의 홍수에서 자신을 보호하기

SipHash와 같은 암호 알고리즘을 선택하는 것은 해시 홍수 DoS 공격에서 우리를 보호해줍니다. 이 공격은 해시 충돌을 고의적으로 생성하여 데이터 구조를 해싱하는 최악의 경우를 시행하고 프로그램의 속도를 늦추려고 합니다. 이는 2010년 초기의 웹에서 많은 문제를 일으켰습니다.

더 안전하게 만들려면 Hasher가 앱이 실행될 때마다 무작위 시드 값을 만들게 해서 해시 값을 예측할 수 없게 만들 수 있습니다.

우리는 특정 해시 값에 의존하거나 실행하는 동안에 저장하지 않아야합니다. 드물지만 저장해야하는 경우가 생긴다면, SWIFT_DETERMINISTIC_HASHING 플래그를 통해 랜덤 해시 시드를 비활성화할 수 있습니다. 상수 값에 의존하면 안되지만 테스트 목적으로는 필요하실 수도 있습니다.

유추를 프로그래밍하는 문제는 그것들이 반사회적 행동을 경계 사례를 통해 정상화하는 것입니다.

이제 우리는 해시의 홍수 Dos 공격의 경우에 공격하는 사람이 어떤 불길한 행동을 할 지 생각할 수 있는 탁월한 소프트웨어 엔지니어가 되었습니다.

다시 말하자면 오늘의 글은 애플 리테일 샵의 지니어스 바에 갔을 때 혼란을 야기시키기 위해서 의상을 통일하라는 말이 아닙니다.

제발 그러지마세요.

대신에 다음과 같이 행동해주세요.

지니어스 바에서 대기 중일때는 비슷하게 옷을 입은 사람과는 멀리 앉으세요. 모두의 일이 더 빨리 해결될 것입니다.