Hashable

오늘의 목표는 Hash 개념과 관련된 개념을 공부하면서 iOS 개발자 면접 질문 리스트 중 하나인, Hashable이 무엇이고 왜 Equatable을 상속해야 하는지 설명하시오. 에 대해 알아보도록 하겠습니다.

 

그리고 Hash라는 개념 자체는 이를 바탕으로 자료구조를 생각해서 코딩 테스트를 잘 풀 수 있습니다. (아마도?

 

Hash 

Hash? Hash Table?

📌 Hash

해쉬, 해쉬값이란 데이터를 간단한 숫자로 변환한 것을 말합니다. 

원본 데이터에 대해서 특정 규칙에 따라 처리하여 간단한 숫자로 변환된 값을 해쉬 값이라고 합니다. 여기서 말하는 특정 규칙은, 원본 데이터(객체)를 해쉬 함수를 사용해서 64bit의 Int값으로 변환한 것을 말합니다. 

 

✅ 데이터가 동일하면 각 데이터의 해쉬값도 동일합니다.

2개의 데이터가 있을 때, 데이터가 동일하면 각 데이터의 해쉬값도 동일합니다. 그러나, 데이터가 다르면 둘은 완전히 다른 해쉬값을 가집니다. (역은 성립하지 않습니다. 그렇기 때문에 해쉬값을 통해서 원본 데이터를 유추할 수는 없습니다.)

 

let hi: String = "안녕하세요"
let hello: String = "안녕하세요"
let apple: String = "소깡이와 함께 하는 Swift 공부"

print(hi.hashValue)    // 2897817589225975386 - 해쉬값
print(hello.hashValue) // 2897817589225975386
print(apple.hashValue) // 1147360803777020165

-> 위의 코드를 보게 되면, "안녕하세요"라는 데이터를 담고 있는 상수 hi와 hello의 해쉬 값은 동일합니다. 즉, 동일한 데이터를 갖고 있다면 동일한 해쉬값을 가집니다. 그러나, "소깡이와 함께 하는 Swift 공부"라는 데이터를 갖고 있는 상수 apple의 해쉬값은 다릅니다. 다른 데이터를 갖고 있기 때문이죠. 

 

해쉬값의 경우 코드를 컴파일/실행 할 때마다 변경되므로 주의해야 합니다.

 

✅ 서로 다른 데이터가 동일한 해쉬값을 가질 수도 있습니다.

앞서 말한 것과 같이 '해쉬값이 동일하면 2개의 데이터가 동일하다'가 참이 아닐 수도 있습니다. 

 

그 이유는 아래와 같습니다. ⬇️

해쉬값은 일정 크기의 Int값이므로 표현할 수 있는 값의 범위는 유한합니다. 그러나 생성할 수 있는 데이터는 무한하기 때문에 데이터를 표현할 해쉬값이 충분하지 않습니다. 

(-> 그리고 이와 같은 이유로 해쉬 충돌이 발생합니다. 해쉬 충돌은 다른 데이터 구조를 사용해서 해결할 수 있습니다.)

 

📌 Hash Table

해쉬 테이블은 해쉬 함수를 사용해서 키를 해쉬 값으로 매핑하고 이 해쉬값을 인덱스/주소로 하여 key와 함께 저장하는 자료구조입니다.

 

🧐 해쉬 함수

해쉬와 해쉬 테이블을 제대로 알기 전에 먼저 해쉬 함수를 제대로 알고 있어야 합니다. 해쉬 함수의 정의는 Key를 고정된 길이의 해쉬 값으로 변경해주는 역할을 하는 함수입니다. 그리고 이 과정을 hashing이라고 합니다. 

 

✔️ 해쉬 함수는 Key로 해쉬를 만드는 함수입니다. 

✔️ Key를 해쉬 함수라는 함수에 Input으로 넣어서 Output으로 나오는 것이 해쉬이고 이 해쉬가 저장 위치라고 생각하면 됩니다.

 

자료 구조를 배우는 이유는 원하는 값을 최대한 효율적으로 찾을 수 있게 하기 위해서 여러 가지 저장 구조를 배우는 것입니다. 데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치를 잘 생각해서 저장해야 합니다. 

해쉬 테이블도 자료 구조 중 하나이고 단순하게 Key-Value로 이루어진 자료 구조라고 생각하면 됩니다. 

 

 

📌 Hash Table의 구성

• Key
  • 고유한 값으로 해쉬 함수의 Input 값이 됩니다.
  • Key 값을 그대로 저장소의 인덱스로 사용할 경우, Key의 길이만큼의 정보를 저장해야 하므로 고정된 길이의 해쉬로 변경합니다/
• Hash Function
  • Key를 고정된 길이의 해쉬로 변경해주는 역할을 합니다.
  • 서로 다른 Key가 hashing 이후 같은 해쉬 값이 나오는 경우가 있습니다. 이를 해쉬 충돌이라고 부르는데, 해쉬 충돌 발생 확률이 낮을수록 좋습니다.
  • 해쉬 충돌이 적게 나는 것도 중요하지만, 균등하게 발생하도록 하는 것도 중요합니다. 모든 Key가 같은 해쉬 값이 나오게 되면 데이터 저장 시 비효율성이 커지고 보안이 취약해지기 때문에 좋지 않습니다. 
• Value
  • 저장소에 최종적으로 저장되는 값으로 해쉬와 매칭되어서 저장됩니다.
• Hash Table
  • 해쉬 함수를 사용해서 Key를 해쉬값으로 매핑하고 이 해쉬값을 주소 또는 색인으로 하여 데이터를 Key와 함께 저장하는 자료구조입니다.
  • 데이터가 저장되는 공간을 버킷, 슬롯이라고 합니다.

- 해쉬 : 색인 또는 인덱스
- 해쉬 함수 : Key -> Hash로 만들어 주는 함수
- 해쉬 테이블 : Hash를 주소로 하여 데이터를 저장하는 자료 구조 

장점

해쉬 테이블은 key-value가 서로 1:1로 매핑되어 있기 때문에 삽입/삭제/검색의 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 갖고 있습니다.

 

단점

- 해쉬 충돌이 발생합니다. 

- 순서/관계가 있는 배열에는 적합하지 않습니다.

- 데이터가 저장되기 전에 미리 그 공간을 만들어야 하므로 공간을 만들었는데, 채워지지 않는 경우 공간 효율성이 떨어집니다.

- 해쉬 함수의 의존도가 높습니다. 그래서 해쉬 함수가 복잡하다면, 해쉬를 만들어 내는데 오래 걸릴 수 있습니다. 

 

해쉬 충돌을 어떻게 해결하는가?
(인덱스를 한정된 인덱스로 바꾸게 된다면, 다른 해쉬 코드라도 같은 인덱스가 나올 수 있고 이 경우 해쉬 충돌이 발생했다고 합니다.)

같은 인덱스를 가지는 데이터가 여러 개인 경우, 그 인덱스의 링크드 리스트 (Linked List)를 선언하고 각 데이터들을 이 리스트에 저장합니다. 이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다. 그러므로 한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 합니다. 

 

Hashable

애플 공식 문서를 찾아보면, Hashable에 대해서 아래와 같이 설명하고 있습니다. ⬇️

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

 

즉, Hasher을 통해 정수 해쉬 값을 생성할 수 있는 유형을 말합니다.

 

Overview

Set 또는 Dictionary의 Key로, Hashable을 준수하는 모든 타입을 사용할 수 있습니다.

Swift에서 딕셔너리는 Dictionary <KeyType, ValueType>의 형태로 쓰입니다. 이때, KeyType은 해쉬 가능한 타입이어야 합니다. (= Hashable 한 타입이어야 한다는 것입니다.) 즉, 그 자체로 유일하게 표현이 가능한 방법을 제공해야 합니다.

 

Swift의 기본 타입(String, Int, Double)은 기본적으로 해쉬 가능한 것들이므로 Dictionary의 KeyType으로 사용이 가능합니다.

 

표준 라이브러리의 많은 타입이 Hashable 합니다. (Hashable을 준수합니다.)

Strings, integers, floating-point, Boolean values, sets이 기본적으로 Hash Value를 제공합니다. 자신만의 사용자 정의 타입도 hash가 가능할 수 있습니다. 

 

associated values 없이 열거형(enum)을 정의하면, Hashable 준수가 자동으로 적용되고, hashValue프로퍼티를 추가하여 사용자 정의 타입에 Hashable 준수를 추가할 수 있습니다.

 

타입의 hashValue프로퍼티에 의해 제공되는 hash 값은, 동일하게 비교되는 임의의 두 인스턴스에 대해 동일한 정수입니다.

즉, 같은 타입의 인스턴스인 a와 b의 경우, a==b이면 a.hashValue == b.hashValue입니다. 

반대의 경우는 true가 아닐 수 있습니다. 동일한 hash 값을 가진 두 개의 인스턴스가 서로 동일한 필요는 없습니다.

 

Conforming to the Hashable Protocol

앞서 Set에는 Hashable 한 것들만 들어갈 수 있고 Dictionary의 Key 역시 Hashable 하다고 했습니다.

사용자 정의 타입도 Set에 넣고 싶거나 Dictionary Key로 만들고 싶다면, 타입이 Hashable 하면 됩니다.

 

사용자 정의 타입의 Hashable과 Equatable 요구 사항은 아래의 조건을 충족시킬 때 컴파일러에서 자동으로 만들어줍니다. ⬇️

- 구조체의 경우, 저장 프로퍼티는 모두 Hashable을 준수해야 합니다.

- 열거형의 경우, 모든 associated values는 모두 Hashable을 준수해야 합니다. 

 

예를 들어서, 버튼 그리드의 위치를 설명하는 GridPoint 타입을 고려해봅시다. 

/// A point in an x-y coordinate system.

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

 

이때, 사용자가 탭한 그리드 포인트의 Set을 만들어 봅시다.

GridPoint타입은 아직 Hashable하지 않기 때문에 Set의 element 타입으로 사용할 수 없습니다. Hashable을 준수하려면, ==연산자와 hashValue 프로퍼티를 제공해야 합니다. 

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

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

공식 문서에는 위처럼 나와 있는데, Swift 4.1 이후부터는 위와 같이 할 필요가 없습니다. 

아래와 같이 Hashable을 채택하면 됩니다. (그러면, 자동으로 hashValue를 만들어 줍니다.)

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

 

위와 같이 Hashable을 채택하면??

var soKyteSet = Set<GridPoint>()

>> Hashable만 element로 넣을 수 있던 Set에도 넣을 수 있고

 

var soKyteDic: [GridPoint:Int] = [:]

>> Dictionary의 Key로도 추가가 가능해집니다.

 

🤔 그렇다면, 왜 Set 또는 Dictionary Key가 되려면 Hashable이어야 할까요?

위에서 해쉬에 대해서 알아보았는데요, 해쉬 테이블을 사용하면 매우 빠른 데이터 검색이 가능하다는 것을 알 수 있습니다. 

해쉬 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해쉬 함수에 의해 얻어지는 값을 해쉬 값, 해쉬 코드.. 간단하게 해쉬라고 한다. 그 용도 중 하나는 해쉬 테이블이라는 자료 구조에 사용되고, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다. 

해쉬 함수는 큰 파일에서 중복되는 값을 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다.

 

Hashable = 정수 Hash 값을 제공하는 타입입니다.

정수 Hash (=hashValue)가 있기 때문에 사용자가 찾으려는 데이터를 빨리 찾을 수 있습니다. 

 

Ex) 예를 들어서, 

0~100까지 데이터를 저장할 수 있는 리스트를 생성하고 'soKyte'에 해쉬 함수를 적용해보겠습니다. 해쉬 함수의 인풋으로 soKyte를 넣고 Output이 25가 나왔다고 하면, 인덱스 25에 soKyte를 저장합니다.

 

해쉬 함수의 경우 동일한 Input에 대해서 동일한 Output이 나오기 때문에 이후 또 soKyte가 들어오게 되면, 같은 25가 나오게 됩니다. 

 

그러고 나서, soKyte를 찾으려고 한다면? 해쉬 함수는 25를 반환할 것입니다. 그래서 0번째부터 찾을 필요 없이 바로 인덱스 25로 가면 soKyte를 찾을 수 있습니다. 

(이때, 인덱스 충돌이 발생할 수 있고 충돌 해결 알고리즘을 통해서 해결할 수 있습니다.)

 

Hashable이 무엇이고 왜 Equatable을 상속해야 하나요?

✅ Hashable을 준수하면, Hasher로 하여금 고정된 길이의 Hash값을 알 수 있습니다. Hashable을 채택하는 Set/Dictionary에서 Set에서는 element가 Dictionary에서는 key가 유일한지 구분하고 이를 통해 빠른 데이터 서치가 가능하므로 성능이 향상됩니다.

 

✅ Hashable이 Equtable을 상속받고 있는데, 이는 Hashable을 통해서 변환된 정수의 값을 통해서 인스턴스를 비교하면서 찾아야 하기 때문입니다.