Swift) 해시 테이블(Hash Table) 이해하기

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

Hash Table

Dictionary는 Key-Value로 값을 저장하기 때문에 특정 Key를 던저주면, 그 키에 해당하는 Value가 나오는 형태잖아??

Dictionary가 바로 해시 테이블이란 것으로 구현되어 있기 때문에 HashTable도 당연히 Key-Value로 값을 저장한다

해시 테이블은 내부적으론 배열로 구현이 되어 있다.

해당 Key를 해시함수란 것을 통해 해시를 하고,

결과 값인 해시 주소 값에 해당하는 해시 테이블 슬롯에 Value를 저장하는 것이다.!

Key 값을 해싱 함수에 넣어 해시하여 배열의 주소값(해시 주소값)을 얻고, 그 주소값에 맞는 index에 Value값을 저장하는 것이다.

Example

Dictionary를 사용할 때 다음과 같이 Key 값으로 기본 자료형(Int, String 등)을 쓸 경우

let myDictionary: [String: Int] = ["Derrick": 31]

아무런 문제 없이 사용할 수 있다.

왜?! Equatable과 마찬가지로 기본 자료형은 컴파일러에 의해 Hashable 프로토콜이 알아서 채택된다.