Hashable

[Brandnew-one]

Hashable

Hash에 대해 먼저 간략하게 살펴보면 아래 그림과 같다 (바킹독 알고리즘 강의 내용)

결국 우리가 사용할 어떤 key 값을 Hash function을 통해서 고정된 길의 데이터로 mapping 해서 Hash value를 얻어내는 것을 의미한다.

왜 굳이 Hash Value를 얻는 과정이 필요할까? 라는 의문이 든다면 위의 예시를 생각해보면 된다.

만약 16자리의 카드번호을 이용해서 해당 카드를 사용하는 사람을 찾는 문제를 생각해보자!

다양한 방법이 있겠지만 시간복잡도가 O(1)이 되는 방법들을 생각해보면 단순하게 Counting Sort와 유사하게 0~9999 9999 9999 9999 크기의 String 타입 배열을 가지고 있으면 인덱스에 카드번호를 넣어줌으로서 O(1) 의 복잡도로 해당 카드번호를 사용하는 사람을 찾을 수 있다.

하지만 위의 방법은 메모리를 굉장히 많이 사용한다는 단점이 있다. 이때 Hash의 개념을 이용하면 메모리는 절약하면서 O(1)의 시간복잡도를 가지도록 할 수 있다.

다양한 Hash function이 있겠지만 단순하게 예를 들면 카드의 앞의 4자리만을 위와 같은 방법으로 저장해서 구분한다고 생각해보자. 이렇게 임의의 길이의 데이터를 고정된 길이의 데이터로 mapping 하는 함수가 Hash function이다.

그렇게 되면 중복되는 문제가 생길 수 있지 않을까? 하는 의문이 생길 수 있다. Hash function을 이용하게 되면 예상했던 것 처럼 중복이 발생해서 충동 이 생기게 되고 이런 충돌이 필연적이다.

이런 충돌을 피하기 위해서 다양한 기법들이 존재한다. (Open Addressing, Chaning)

---

그럼 Hashable 프로토콜을 채택한다는 것은 어떤 key 값을 해쉬함수를 통해서 hash value로 만들어 낼 수 있다. 어떤 key 값을 고유한 hash value (Int)로 만들어 낼 수 있음을 의미한다.

protocol Hashable: Equatable {
  var hashValue: Int { get } // Deprecated
  func hash(into hasher: inout Hasher)
}

프로토콜을 살펴보면 앞서 공부한 Equatable 프로토콜을 채택하고 있고 hash 함수를 구현해야 하는 것을 확인 할 수 있다.

Swift의 기본 자료형들은 이미 Hashable 프로토콜을 채택하고 있다. (그래서 우리가 딕셔너리 타입을 사용할 때 key 값으로 사용할 수 있었고, Set의 자료형으로 사용할 수 있었다)

구조체, 열거형, 클래스와 같이 우리가 커스텀하게 만드는 경우 Hashable을 채택하는 방법을 살펴보자

struct

// 구조체 내의 프로퍼티가 모두 기본 자료형인 경우, Hashable 채택만으로 가능
struct Human: Hashable {
  let name: String
  let height: Double
}

let a = Human(name: "bran", height: 27)
let b = Human(name: "bran", height: 27)
if a == b {
  print("오잉 구조체는 값타입이라 Equable을 만족하고 있는건가?")
}

var dic: [Human : Int]

구조체의 저장프로퍼티는 모두 Hashable을 준수해야 한다.

구조체는 Swift 4.1 이후로 Hashable을 채택만해주면 된다.

enum

// 연관값이 없는 열거형은 Hashable을 채택하지 않아도 자동으로 구현
enum Gender {
  case male
  case female
}

var myDic: [Gender : Int]

enum GenderwithAge: Hashable {
  case male(age: Int)
  case female(man: Human)
}

연관값이 없는 열거형의 경우 Hashable을 이미 채택하고 있고, 연관값이 있는 경우 연관값은 모두 Hashable을 준수해야 한다.

class

// 클래스가 Hashable하기 위해서는 프로토콜을 채택하고
class Man {
  let name: String = "Bran"
  let age: Int = 27
}

// Equatable 프로토콜을 채택하고
extension Man: Equatable {
  static func == (lhs: Man, rhs: Man) -> Bool {
    return lhs.name == rhs.name && lhs.age == rhs.age
  }
}

// hash 함수를 구현해야 한다
extension Man: Hashable {
  func hash(into hasher: inout Hasher) {
    hasher.combine(name)
    hasher.combine(age)
  }
}

클래스는 Equatable 프로토콜을 준수하고 hash 함수를 가지고 있어야 한다. hash 함수는 Hasher의 combine을 사용해서 쉽게 구현할 수 있다.

(combine에는 해당 타입의 모든 저장 프로퍼티를 전달, 해당 프로퍼티는 Hashable을 준수하고 있어야 함)