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 }



https://soojin.ro/blog/hashable

[기본기] Hashing 제대로 알기 · Soojin Ro

soojin.ro


    
      [기본기] Hashing 제대로 알기 · Soojin Ro

더 많은 콘텐츠를 보고 싶다면?

또는

이미 회원이신가요?

2023년 10월 24일 오후 5:13

댓글 0