• 왜 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 }

https://soojin.ro/blog/hashable