Hashable이란?
먼저 최초의 질문은 Hashable이라는 프로토콜이 무엇인지에 대한 궁금증에서 출발한다.
Hashable이란, hasher로 인하여 int값인 hash value를 가져서 hashing 될수있는 타입을 의미한다.
그렇다면 Hasher는?
Hasher는 구조체 이며, hash 함수이며, 주로 셋과 딕셔너리 타입에서 사용한다.
해당 메소드를 보면 다음과 같은데
•
.combine<H>(H) : 주어진 값을 해셔에 추가해서 해셔에 혼합한다.
•
.finalize() → Int : 해시를 완료하고 해시 값을 반환한다.
직접 쳐본 코드
해시(Hash)
쉽게 말해서 딕셔너리 같은 타입이 해시를 사용하게 되는데, 이는 Key와 Value값의 1대1 매핑을 해주게 되는 자료형이다. 그런데 이때 이 value값을 해시테이블이라는 배열에 저장하게 된다.
즉, 이렇게 배열에 key값을 해싱함수에 넣게 되면, 해당 주소값(해시값)을 통해서 hashtable의 배열 위치를 알게 되고, 이 위치에 value를 저장하게 되는것이다.
다시 정리하자면,
Key라는 것을 해시 함수를 이용해 해시 주소값(해시 테이블의 index)으로 바꾸고,
해시 주소값(해시 테이블의 index)를 통해 해시 테이블에 접근하여 값을 가져오거나 저장하는 형태이다.
그래서 위에서 .finalize를 하면 int값이 반환되는것이다. (주소값)
해시의 장점
해시테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로O(1)의 시간복잡도를 가지고 있다.
해시의 단점
•
해시 충돌이 발생(개방 주소법, 체이닝 과 같은 기법으로 해결해 줘야 한다.)
•
순서/관계가 있는 배열에는 어울리지 않는다.
•
공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다. 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다.
•
hash function의 의존도가 높다. 해시함수가 복잡하다면 hash를 만들어 내는데 오래 걸릴 것이다
해시충돌을 해결해주기 위한 방법
해시 충돌이란, 동일한 키값으로 해싱을 하게 되면, 동일한 해시값을 가지게 되고 이는 동일한 주소를 가지게 되는것이기 때문에 메모리충돌이 일어난다.
1. 체이닝
체이닝이란, linked list를 사용해서 데이터를 추가로 뒤에 연결해주는 방법을 의미한다.
알고리즘은 다음과 같다.
•
hash값이 주어졌을때 해당 해시값에 데이터가 있는지 해시테이블을 검색한다.
•
데이터가 존재하면, 다음 공간을 생성해서 연결해주면 된다.
2. liner probing
liner probing이란, 해시충돌이 일어났을 때 빈 공간을 선형탐색하면서 값을 삽입하는 방법을 말한다.
알고리즘은 다음과 같다.
1.
hash값을 구한다.
2.
해당 hash값의 위치에 값이 존재할 경우, 다음 인덱스를 선형탐색하면서 빈공간을 찾는다.
3.
빈공간을 찾으면 해당 공간에 값을 저장한다.
4.
모든 공간을 탐색하였음에도 빈공간을 찾지 못했을 경우, 해시테이블의 크기를 늘려주면 된다.
다시 돌아와서! Hashable에 대해서
Hashable프로토콜은 또 Equatable이라는 프로토콜을 채택하고 있다.
Equatable프로토콜이란???
기본적으로 우리는 int형이나, double, string과 같은 타입은 비교 연산이 가능하다.
그렇지만 struct나 class의 인스턴스는 비교 연산자가 불가능한데 그 이유는 기본적으로 사용하는 Int, string, double이라는 형 내부에서는 진작에 Equatable이라는 프로토콜이 채택되어 있고 이로 인하여 구현까지 되어있기 때문이다.
프로토콜 요구사향
이런식으로 구현되어 있음, 타입에 대한 비교기 때문에 static(타입함수)로 선언되어있다.
인스턴스끼리 비교하고 싶어요~
인스턴스끼리 비교를 하고 싶을때는, 앞서 말했듯이 Equatable이라는 프로토콜을 채택하면 된다.
이렇게 비교연산자를 사용하면 당연하게도, 작동하지 않는다! 하지만 Equatable을 채택하면 다음과 같이 된다.
채택한후, 프로토콜 구현에서 class 내부의 프로퍼티를 비교해서 동일하면 Boo로 리턴하는것으로 구현하게 된다.
이렇게 Equatable을 채택하면 인스턴스끼리의 비교연산이 가능하게 된다.
equatable을 hashable이 채택해야 하는 이유(내 생각)
서로다른 인스턴스가 동일한 해시값을 갖도록 해야하기 때문이다.
예를 들어서,
class Jinyong {
var name: Stirng = "jin"
}
var someJin = Jinyong()
var someOne = Jinyong()
Swift
복사
이렇게 만들었을때, Jinyong이 키값으로 들어가게 되면 someJin과 someOne은 동일한 키값이 되어야하며 동일한 hashvalue를 리턴해야한다.
하지만 만약 Equatable을 채택하지 않는다면 두개의 인스턴스를 비교를 할수가 없고, 즉 동일한 hashvalue를 리턴할수도 없게 된다. 따라서 hashable은 Equatable을 채택해야하는것이다.
다시 다시 Hashable로 돌아와서
Hashable을 채택하는 이유는 class, enum, struct를 딕셔너리 형태의 key로 사용하기 위해서이다.
구조체에서 Hashable
클래스에서의 Hashable
클래스에서 hashable을 채택할때는 Hash함수를 직접 구현을 해야한다.
하지만!! swift에서는 직접 구현해뒀다 뭐로? 아까 공부했던 Hasher~~~~~~~~
주의사항은
•
특별한 경우가 아니면 combine에는 해당 타입의 모든 저장 프로퍼티를 전달하는 것
•
또한, combine 파라미터로 전달하는 프로퍼티는 반드시 Hashable을 준수하고 있어야 한다.
정리
•
Hash란, 한개의 키 값을 통해서 해싱함수를 거쳐 해시값(주소)를 리턴하고 해당 주소에 Value를 저장하는 방식의 자료구조를 의미한다.
•
이러한 방법을 사용해서 보통 Set, Dictionray를 구현하게 된다.
•
따라서 Swift에서는 Hashable이라는 프로토콜은 dictionary타입의 키 값으로 class, struct, enum의 타입을 사용할때 채택한다.
•
하지만 이렇게 인스턴스를 비교연산은 기본적으로 불가능 하기 때문에 Hashable은 Equatable이라는 프로토콜을 채택하고 있다.
참고자료
