class SomeObject: Hashable
어떤 객체가 Hashable 프로토콜을 채택해서 따른다.
즉, 어떤 객체가 Hashable 하다는 것은 무슨 말일까요?
이 질문에 대답할 수 있으려면, Hashable한 객체가 어디에 사용되는지를 알아야 합니다.
결론부터 말씀드리면!! Hashable한 객체는 Hash Table에 저장될 수 있어요!
1. Hash Table이 뭘까?
Hash Table은 Collection 타입의 저장 방식의 한 개념인데,
(index 방식 : Array, Hash Table 방식 : Set, Dictionary)
index를 기반으로 저장되는 Array의 개념과 달리 Hash Table은 객체의 Hash값을 기반으로 저장됩니다.
쉽게 이야기하면, 객체의 Hash값이 객체의 주소가 되는거죠!!
출처: https://khalilstemmler.com/blogs/data-structures-algorithms/hash-tables/
우리가 직접 Hash Table을 구현하여 사용할 수도 있지만,
이미 Swift에는 Hash Table방식으로 저장하는 Set과 Dictionary가 내장되어 있어 더 익숙하실 거에요!
Set은 “Hash Table 그 자체”라고 보시면 되고 Dictionary는 Hash Table을 이용한 저장 방식이라고 보시면 됩니다.
Dictionary는 Hash Table에 Key 값의 Hash 주소에 Value가 저장되는 형태이죠.
Hash Table 방식의 장점은 시간복잡도에 있습니다.
예를 들어 Hash Table에서 “Apple”이라는 단어를 조회한다고 하면, 단순히 Apple의 Hash 값으로 해당 위치를 보면 되기 떄문이죠!
만약 index 방식으로 단어를 찾는다면 index 0부터 쭉 순회해야 하는 번거로움이 있죠
데이터를 추가할 때도 index 방식은 마지막 index까지 간 이후, 그 뒤에 데이터를 붙여주는 방식인데,
Hash Table의 경우 Hash 값으로 그곳에 저장하면 되니까 보다 효율적입니다. (시간 복잡도 보통 O(1))
다만 어디에 저장될지 모르기 때문에 저장 공간을 넓게 잡아서 메모리가 조금 더 사용된다는 문제가 있는데요..
또 저장한 순간부터 각각 Hash 값 위치에 저장되어 순서가 의미 없어지기 때문에 순서가 유지되어야 하는 경우에도 문제가 생길 수 있습니다.
정리하면, Hash Table은 Index 방식과 비교하여 다음과 같아요.
장점: 시간복잡도(Read / Write)가 빠르다.
단점: 공간복잡도(저장공간이 더 차지)가 크다. 순서가 유지되지 않는다.
2. HashTable에서 충돌 해결 (Equatable 해야 하는 이유)
Swift의 Hashable을 열어보면, 다음과 같이 Equatable 프로토콜을 기본으로 채택하고 있습니다.
다시 말해 Hashable 하려면 Equatable 해야 한다는거죠!!
public protocol Hashable : Equatable
왜 Equatable 해야할까요?
이는 Hash Table에서 Write시 Hash값 충돌을 해결하는 방식과 연관이 있습니다.
갑자기 충돌? 그냥 Hash 값 계산한 다음에 그 위치에 저장하면 되는거 아녔어??
정말 드문 경우이긴 하지만 두 다른 값의 Hash 값이 같을 수도 있습니다..
예를 한번 들어볼게요!
두 String “Apple”과 “Samsung”을 Hash Table에 저장하려고 한다고 합시다.
- “Apple”의 Hash 값을 계산 했더니 11aaa 이라는 값이 나와서, 이 위치에 저장을 했습니다.
- “Samsung”의 Hash 값을 계산 했더니 또 11aaa이 나왔습니다.
이제 어떻게 해야할까요?? 저 위치는 이미 “Apple”이 저장되어 있는데??
이를 해결하기 위해 두가지 방식이 주로 사용됩니다.
첫번째로 Chaining 기법입니다.
Linked List 기법을 활용하여, 11aaa 위치의 “Apple” 값 뒤에 “Samsung”을 붙이는거죠.
그리고 식별을 위해 Hash 되기 전의 값도 함께 저장합니다.
자 이제 거꾸로 저장된 Hash Table에서 “Samsung”을 조회 하려면 어떻게 할까요?
- 먼저 “Samsung”의 hash값인 11aaa로 찾아갑니다. 똑 똑 똑
- 갔더니 “Apple”이 있네요.
- “Samsung”과 비교합니다. 다르네??
- 그럼 linked list를 타고 다음 노드로 들어갑니다.
- 이번엔 “Samsung”이 있고, 조회하려고 했던 “Samsung”과 같네??
- Hash Table에는 “Samsung”이 contain되어 있다는 것을 알리자!! (끝)
이렇게 되는거죠!
여기 3번에서 “Apple”과 “Samsung”을 비교하기 위해서는 둘 모두 Equatable 해야겠죠?
Hashable이 Equatable을 채택하고 있어야 하는 이유입니다!!
아까 두가지 방법이 있다고 했죠?
나머지 하나는 Linear Probing 기법입니다.
저는 이 방법이 썩 좋아보이진 않는데요..ㅎㅎ
그래도 한번 알아보자면,
hash 값이 충돌하게 되면, Hash Table을 순회하다가, 가장 처음 나오는 빈공간에 그냥 무지성으로 저장하는 것이죠ㅎㅎ
마찬가지로 비교를 위해 Hash 전 값도 저장하고, 이번에는 Hash 값도 함께 저장해주어야 합니다.
마찬가지로 “Samsung”을 조회한다고 가정할게요!!
- 먼저 “Samsung”의 hash값인 11aaa로 찾아갑니다. 똑 똑 똑
- 갔더니 “Apple”이 있네요.
- “Samsung”과 비교합니다. 다르네?? (여기까진 같죠?)
- 이제 “Apple” 이후의 주소값부터 11aaa hash값을 가진 객체가 나올 때까지 쭉 순회합니다.
- 11aaa 주소값을 가진 공간을 드디어 찾았다. 그 안에는 “Samsung”이 있고, 조회하려고 했던 “Samsung”과 같네??
- Hash Table에는 “Samsung”이 contain되어 있다는 것을 알리자!! (끝)
Chaining기법의 경우에는 linked list로 타고 타고 들어가다 끝 Node까지 가도 없을 때는 없다고 판단할 수 있는데,
Linear Probing 기법에서는 찾을 떄까지 “Apple” 다음 공간을 순회해야 해서 비효율적이라는 생각이 드는데요?
제가 생각하지 못한 기가막히고 코가막힌 방법으로 이 순회를 안하게 했으려나?? 누가 알면 알려주세요!
다만 collection에 할당되어 있는 주소값 덩어리 내에서 어떻게든 빈 공간을 찾아서 저장하기 때문에,
최대한 할당된 저장공간을 사용한다는 점에서는 효율적일 수 있습니다.
(근데 애초에 Hash Table을 쓰는 것 자체가 저 정도는 감수하는거 아닌가..)
제 생각에는 Chaining과 Linear Probing을 적절하게 섞은 방식이 합리적이라고 생각이 되는데요.
타고 타고 빈공간을 찾은 다음에, 그 빈공간의 주소값을 Apple의 Linked List의 다음 노드의 주소값으로 저장하면 조회도 더 빠를거고 저장공간도 할당된 공간을 최대한 쓰니까 좋지 않을까요?
사실 hash 값이 충돌나는 경우는 거의 없으니까!! 알아서 잘 되어있을거라고 믿고 넘어가죠
3. Struct와 Class에서 Hashable 채택
Class에서 Hashable을 채택하려고 하면, Equtable을 위한 메소드와 Hashable을 위한 hash(into: Hasher)메소드를 따로 구현해야 한다고 하는데요.
(밑에 코드로 실험 해보시길..)
왜 그럴까요?
struct CellModel: Hashable {
let person: Person
var isSelected: Bool
}
class CellModel: Hashable {
let person: Person
var isSelected: Bool
// static func == (lhs: CellModel, rhs: CellModel) -> Bool
// func hash(into hasher: inout Hasher)
}
struct Person: Hashable {
let name: String
}
이 원인을 이해하기 위해서는 Struct와 Class의 차이를 정확하게 알고 있어야 합니다.
먼저 사실 별로 상관 없는 Equatable에 대해서 간단하게 보시죠.
Struct 인스턴스는 그 자체가 값이기 때문에 (값타입) person 값이 같고, isSelected 값이 같으면 그냥 같은 값으로 다르면 다른 값으로 취급이 됩니다.
따로 ==을 구현해주지 않아도요!
반면에 Class의 인스턴스는 어떻죠?? 내부의 person과 isSelected 값이 모두 같아도, 다른 인스턴스이면 그냥 다른 인스턴스인겁니다.
왜??
Class의 인스턴스가 가르키는 것은 인스턴스의 값 자체가 아닌 인스턴스의 주소값이니까!!! (참조타입)
그렇기 때문에 두 Class 인스턴스를 비교하기 위해서는 비교를 위한 == 메소드를 구현해줘야 하는거죠
Hashable도 마찬가지입니다. Struct 인스턴스는 그 자체로 값이기 때문에 그 값을 hash 연산하면 되는데,
Class 인스턴스의 경우, 그 자체가 주소값을 가리키고 있기 때문에 따로 Hash 연산을 어떻게 할건지를 명시해줘야 하는거죠.
자 여기까지 이해하셨으면 Hashable에 대해서 이제 기본을 알고 계시는 거라고 생각합니다ㅎㅎ
'iOS 개발 > Swift' 카테고리의 다른 글
[Swift] iOS는 화면을 어떻게 렌더링할까? (1) | 2023.10.04 |
---|---|
[Swift] Struct와 Class를 메모리 원리부터 자세하게 비교해보자 (2) | 2023.02.12 |
[ARC] 성능을 위해 unowned를 꼭 써야할까? (0) | 2023.02.03 |
[ARC] Lazy 변수 클로저에서 Unowned 캡처가 항상 안전할까? (0) | 2023.02.02 |
[Concurrency] Semaphore로 비동기적 이벤트를 동기적으로 발생시키기 (0) | 2023.01.20 |
[ARC] 약한참조(Weak, Unowned)에 대해서 (0) | 2022.11.06 |
[Swift] 지정한 For-Loop 탈출하기 (0) | 2022.10.03 |
[Swift] Stride 함수를 사용하자 (0) | 2022.10.02 |