[Swift] 프로토토콜 뽀개볼까 (4) | Hashable, HashTable

set, dictionary가 해시테이블로 만들어져서 배열의 검색보다 빠르다는 이야기를 들어본 적이 있나요?

set, dictionary가 해시테이블로 저장되기 위해서는 hashable해야하는데, 

 

이 해시테이블이란 무엇이고 값들이 어떻게 저장되며, hashable은 도대체 무엇인지 알아보자!!

 

# HashTable

Hah Table은 간단하게 말하면 (key,valye)형태로 데이터를 저장하는 자료구조입니다만,,,

전혀 간단하지 않단말임..

 

1) key를 해시 함수에 넣어
2) 고유한 인덱스를 만들어서
3) 배열의 해당 인덱스에 value값을 집어넣는 원리

라고 일단 머릿속에 넣어놓고 천천히 생각해 보자!

 

 

 

 

(key,valye)형태라고 하면 swift에서 가장 먼저 생각나는 건 아마 딕셔너리 Dictionary 일 것이다. 

맞다. 가장 처음에 말했던 것처럼 set, dictionary가 해시 테이블이란 것으로 구현되어 있다.

 

뒤에 다시 설명하겠지만 set, dictionary가 해시 테이블이란 것으로 구현되어 있다는 것은
=> set의 원소, dictionary key가 hashable 해야한다는 것!

 

 

 

 

 

일단 대충 해시테이블은 이렇구나를 머릿속에 담아놓고 해시테이블에 값을 저장할 때와 해시테이블에서 값을 가져올 때 어떻게 작동되는지 알아보자!

 

 

 

 

 

해시테이블에 값을 저장할 때

해시’테이블’이라는 이름에서 알 수 있듯이 내부적으로는 배열을 이용해서 저장하고 있다.

 

 

그럼 이 배열에 어떻게 값을 저장하느냐!

1) key 값에 해시함수를 적용해서 정수로 변환하고,
2) 이때 변환된 정수는 해시 테이블 배열의 인덱스 역할을 한다.
3) 이렇게 저장할 index를 결정하고, value를 그 index에 저장시켜 놓는 것!

좀 더 풀어서 설명했지만 위에서 설명한 1), 2), 3)  설명과 동일하다!

 

 

 

(key, value) 형태로 가장 익숙한 딕셔너리를 예로 들어 설명하면,

[Key:value] 이런 식으로 시퀀스가 나열되어 있으면

1) key를 해시 함수를 통해 해시
2) 결과값인 해시 주소값(정수값)이 인덱스 역할을 하고
3) 그 인덱스 해당하는 해시테이블 슬롯에 value를 저장한다

지금도 예시를 들어 설명했지만 위에서 설명한 1), 2), 3)  설명과 동일하다!

 

 

 

 

 

 

 

해시테이블에서 값을 가져올 때

우리 눈에 보이는 대로 key:value 이렇게 대응시켜서 저장하는 게 아니라 해시테이블로 저장하기 때문에

우리는 value를 찾기 위해 key를 그대로 사용하는 것이 아닌!

 

key를 해싱해서 해시테이블의 index를 알 수 있어야 그 index를 활용해서

해시테이블[index] 이렇게 접근해서 value값을 가져올 수 있게 되는 것!!

 

⇒ key에 대응하는 index 정수값이 항상 동일해야 value를 찾을 수 있는 것

 

 

 

 

 

 

 

# "Hashable 하다"?

 

해시 테이블을 알아봤는데 그래서 도대체 Hashable은 뭔데?

"Hash" + "able" 아니겠나.. 그니까.. "해시" + "할 수 있는"

=> "해싱할 수 있는 것 "

 

그럼 "해시한다는 것" 즉, "해싱hashing"은 뭔데??

"Hasher(해시 함수)에 의해 해싱되어 해시값을 만드는 것!"을 말한다.

 

즉,

Hashable

=> "Hasher(해시 함수)에 의해 해싱되어 해시값을 만들 수 있는 것!"을 의미한다.

 

 

 

 

 

 

 

# Hashable 공식문서

A type that can be hashed into a Hasher to produce an integer hash value.
(정수 해시값을 생성하기 위해 Hasher로 해시될 수 있는 유형.)

 

앞서 알아본 것처럼 정수 해시값을 만들기 위한 것이라고 하죠!

 

- Hashable 프로토콜을 준수하는 모든 유형을 set 또는 dictionary의 key값으로 사용할 수 있다.
- 표준 라이브러리의 많은 유형은 Hashable을 준수합니다. (String, Int, Bool, Float, 심지어 set도 기본적으로 hashable하다)

 

set, dictionary가 해시테이블로 구현될 수 있는 이유도 set의 원소와 dictionary key가 hashable하기 때문이죠! 

즉,  set의 원소와 dictionary key에는 hashable한 것만 들어가야 한다고 공식문서에서도 말하고 있습니다!

 

 

그리고 여느 프로토콜처럼 Swift의 기본 유형은 hashable하게 구현이 이미 되어 있다고 하네요!

그럼 역시나 이 프로토콜 준수하는 걸 고려해줘야 할 건 custom type이겠네요?!

맞슴당..

custom type(구조체, 클래스, 열거형)도 해시 가능하도록 만들 수 있는데요!

->  이제 어떻게 활용하는지 한번 살펴볼까요

 

 

 

 

 

 

 

# 커스텀 타입에서의 Hashable

 

딕셔너리가 Hash Table로 구현되기 위해서는 딕셔너리의 key가 hashable 해야 한다고 말했었죠?

⇒ 즉, 어떤 타입이 hashable 한 지 보려면 딕셔너리의 키 자리에 넣어보면된답니당

 

 

 

 

구조체 

Hashable한 타입만 넣을 수 있는 딕셔너리의 key 자리에 구조체 타입을 그냥 넣어주면 에러

 

 

 

모든 프로퍼티가 hashable한 구조체의 경우에는 Hashable 프로토콜만 채택해 주면 hash(into:)함수는 자동으로 구현해 준다

struct HashablePersonStruct : Hashable {
    let name : String
    let age : Int
}

let dictionary3 : [HashablePersonStruct : String]

 

 

 

구조체의 프로퍼티가 구조체 타입이더라도 그 구조체가 hashable하다면!

이 경우에도 당연히 Hashable 준수하겠죠??

struct HashablePersonStruct : Hashable {
    let name : String
    let age : Int
    let dog : HashableDogStruct
}

let dictionary3 : [HashablePersonStruct : String]


struct HashableDogStruct : Hashable {
    let dogName : String
    let dogAge : Int
    
}

 

 

 

 

열거형

연관값 없는 열거형은 정의하면 자동으로 Hashable 을 준수하게 된다.

enum HashableEnum {
    case case1
    case case2
    case case3
}



let dictionary1 : [HashableEnum : String]
dictionary1 = [.case1 : "case1"]

 

 

 

연관값 있는 열거형은 Hashable 프로토콜만 채택해 주면 hash(into:)함수는 자동으로 구현해 준다

enum HashableEnum2 : Hashable {
    case case1(num : Int)
    case case2(num : Int)
    case case3(num : Int)
}

let dictionary2 : [HashableEnum2 : String]

 

 

 

 

 

 

 

 

하지만 위의 열거형, 구조체의 경우와 다르게

자동으로 Hashable을 준수하지 못하는 커스텀타입의 경우에는 어떻게 하느냐!

Hashable을 채택하고 hash(into:)함수를 사용해서 Hashable을 준수하도록 만들어주어야 하는 것입니다!

바로 밑에 나오는 class가 바로 그렇게 해주어야 하는 아이..

 

 

 

 

 

 

 

 

 

클래스

역시나 클래스는 호락호락하지 않을 것이라는 거 예상은 했습니다

 

프로퍼티가 모두 Hashable 하더라도.. Hashable을 채택해주어야 하고요!!

Hashable을 채택하더라도 ‘Equatable’과 ‘Hashable’을 준수하지 않았다고 나오죠?

 

 

 

 

왜냐

 

일단 ‘Hashable’을 준수하지 않았으니 Hashable 프로토콜에서 채택하고 있는 ‘Equatable’을 준수하지 않은 것은 당연하구

 

‘Hashable’을 준수하지 않았다는 건! 위에서 말해던 hash(into:)를 구현해주어야 했던 것!

 

 

 

 

 

근데 hash(into:)함수 어떻게 구현해 주는데

 

hasher이란 파라미터의 combine이란 메서드를 이용하면 되는데

hasher.combine이란 메서드에 해시할 파라미터로 넣어주는 것!

 

다만, 특별한 경우가 아니면 combine에는 해당 타입의 모든 저장 프로퍼티를 전달하고

또한, combine 파라미터로 전달하는 프로퍼티는 반드시 Hashable을 준수하고 있어야

한다고 하네요?! ( dogName은 String 이고 dogAge는 Int이기 때문에 당연히 Hashable 준수하고 있죠??)

class HashableDogClass : Hashable{
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(dogName)
        hasher.combine(dogAge)
    }
    
    let dogName : String
    let dogAge : Int
    
    init(dogName : String, dogAge : Int) {
        self.dogName = dogName
        self.dogAge = dogAge
    }
}


let dictionary4 : [HashableDogClass : String]

 

 

 

 

 

 

그래도 .. 에러가 여전히 하나 더!

 

 

왜 Hashable을 채택했는데 Equatable은 준수하지 않고 있냐! 라는 건데요..

Comparable 프로토콜이 Equatable을 이미 채택하고 있었던 프로토콜이었던 것처럼, Hashable도 공식문서에서 봤다시피 Equatable을 이미 채택하고 있었죠?!

 

 

 

그르니까.. Hashable을 채택했으면 Equatable도 준수해주어야 하는데..

클래스는 Equatable를 준수해 주려면 == 라는 static method를 구현 해줘야하져

 

 

이렇게 해주면 오류 해결!

class HashableDogClass : Hashable{
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(dogName)
        hasher.combine(dogAge)
    }
    
    static func == (lhs: HashableDogClass, rhs: HashableDogClass) -> Bool {
        return lhs.dogName==rhs.dogName && lhs.dogAge==rhs.dogAge
    }
    
    let dogName : String
    let dogAge : Int
    
    init(dogName : String, dogAge : Int) {
        self.dogName = dogName
        self.dogAge = dogAge
    }
}


let dictionary4 : [HashableDogClass : String]

 

 

 

 

 

 

# +) array의 검색 속도보다 set, dictionary의 검색 속도가 더 빠른 이유?!

배열에서 어떤 요소가 있는지 여부를 검색하려면 해당 배열을 싹~ 다 훑어야 하죠??

그래서 .contains(_:)메서드를 사용하면 O(n)라는 시간복잡도가 나오죠

 

반면 set는 어떨까요?

.contains(_:)메서드를 사용하면 파라미터로 전달되는 요소가 해싱되어 바로 그 요소가 있는지, 몇 번째 인덱스에 있는지 알 수 있겠죠!

그래서 시간복잡도가 O(1)인것!

 

그럼 dictionary는?

dictionary는 검색할 때 key를 통해서 값이 있는지 여부, 어떤 값을 가지고 있는지 알 수 있는데 

이 때도 key가 해싱되어 그 인덱스에 값이 있는지를 알 수 있겠죠?

그래서 시간복잡도가 O(1)! 

 

 

 

 

 

---

 

 

 

Hashable이라는 프로토콜을 자세히 공부하며 자료구조 중 Hash Table에 대해 알아보는 계기가 되었고, Hash Table로 구현되어 있는 set와 dictionary도 좀 더 깊이 이해할 수 있었습니다!

그리고  set와 dictionary의 검색, 조회가 왜 배열보다 빠른 지도 이해할 수 있었네욤 ㅎㅎ