<div id="readability-page-1" class="page"><div aria-label="Content">
<article itemscope="" itemtype="http://schema.org/BlogPosting">
<header>


<time datetime="2023-10-24T00:00:00+00:00" itemprop="datePublished">
Oct 24, 2023
</time> &nbsp;
</header>
<div itemprop="articleBody">
<h2 id="dictionary의-키는-왜-hashable-타입인가요">Dictionary의 키는 왜 Hashable 타입인가요?</h2>
<ul>
<li>왜 Dictionary/Set의 탐색은 O(1)인가?</li>
<li>왜 Dictionary 탐색의 최악의 경우는 O(n)인가?</li>
<li>Hashable의 hashValue는 왜 Int 인가?</li>
<li>Hashing을 왜 하는가?</li>
<li>좋은 해싱 알고리즘이 필요한 이유는?</li>
</ul>
위 질문에 대한 답을 명확히 하기 힘들다면 Array만을 가지고 Dictionary를 직접 구현해보는 것을 추천한다. 그 과정에서 알게 되는 것들로 위 질문들에 대한 답을 찾을 수 있다.
요구사항은 아래와 같다.
<ul>
<li>자료 구조는 Array만 사용한다.</li>
<li>Hashable 타입은 사용하지 않는다.</li>
<li>구현해야 하는 메서드
<div><pre><code>func value(forKey key: Key) -&gt; Value?
func insert(_ value: Value?, forKey key: Key)
var count: Int { get }
</code></pre></div>
</li>
</ul>

</div>

Tags: swift, mutation, variable, constants &nbsp; 


</article>
</div></div>

Soojin Ro

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 }

[기본기] Hashing 제대로 알기

댓글