Dictionary의 키는 왜 Hashable 타입인가요?

  • 왜 Dictionary/Set의 탐색은 O(1)인가?
  • 왜 Dictionary 탐색의 최악의 경우는 O(n)인가?
  • Hashable의 hashValue는 왜 Int 인가?
  • Hashing을 왜 하는가?
  • 좋은 해싱 알고리즘이 필요한 이유는?

위 질문에 대한 답을 명확히 하기 힘들다면 Array만을 가지고 Dictionary를 직접 구현해보는 것을 추천한다. 그 과정에서 알게 되는 것들로 위 질문들에 대한 답을 찾을 수 있다.

요구사항은 아래와 같다.

  • 자료 구조는 Array만 사용한다.
  • Hashable 타입은 사용하지 않는다.
  • 구현해야 하는 메서드 
    func value(forKey key: Key) -> Value?
func insert(_ value: Value?, forKey key: Key)
var count: Int { get }