요약

• 정수 해시값을 만들어 낼 수 있는 타입
  • hash(into:) 에서 Hasher 가 해싱한다.
• Hashable 타입은 Set, Dictionary 의 키로 사용된다.
• 🔥 Hashable 에 Equatable 이 필요한 이유
  • 해시테이블 구조에서는 Hash Collision 이 일어날 수 있다.
  • Swift 의 Dictionary 에서는 해시충돌 시 개방주소방식 중 하나인 Linear Probing 방식을 사용한다.
  • 같은 해시 값으로 저장된 경우에는 실제 객체를 비교해서 원하는 값을 찾는다.

개요

• Set, Dictionary 의 키에 사용
• String, Integer, floating-point and Boolean values 등은 Hashable 을 준수함
  • Optional 은 타입 파라미터에 전달된 타입이 준수하면 따라서 준수함
• 커스텀 타입에 hash(into:) 를 구현해주면 준수가능함

Linear Probing

• Swift 레포 주석에서 발견하였다.

https://github.com/apple/swift/blob/main/stdlib/public/core/Dictionary.swift

Native storage is a hash table with open addressing and linear probing.

자료