<Dictionary> 왜 검색이 빠른가?

Dictionary는 일반적으로 Hashing이라는 기술을 사용하여 데이터를 저장하고 검색합니다. 이러한 Hashing은 데이터의 특정 특성을 활용하여 고유한 'Hash key'를 생성하며, 이 Key를 사용하여 데이터를 찾습니다.

Hash table(해시 테이블)이라는 이러한 데이터 구조는 일반적으로 배열과 같은 다른 데이터 구조에 비해 빠른 검색 속도를 제공합니다. 

 

배열에서 데이터를 찾으려면, 보통 모든 원소를 차례대로 검색해야 하므로, 이를 선형 검색이라 하며, O(N)의 시간 복잡도를 가집니다. 여기서 N은 배열의 크기를 나타냅니다.

해시 테이블은 특정 Key를 사용하여 데이터를 즉시 찾을 수 있습니다. 이는 상수 시간, 즉 O(1)의 시간 복잡도로 검색할 수 있게 해줍니다. 즉, 데이터의 크기와 관계없이 항상 일정한 시간에 데이터를 찾을 수 있습니다.

따라서, Dictionary 같은 해시 기반의 자료구조는 많은 양의 데이터를 효율적으로 관리하고 검색하는데 매우 유용합니다. 그러나 이런 장점이 있음에도 불구하고, 해시 충돌(hash collision)이라는 문제가 발생할 수 있어 이를 관리하는 방법 또한 중요하게 생각해야 합니다.

 

***해시 충돌이란 서로 다른 데이터에 대해 동일한 해시 키가 생성되는 현상이다.