룩업(lookup, 조회)은 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키(key)에 해당하는 값(value)을 찾는 작업을 의미합니다. 이전 장에서 예로 들었던 학생 데이터베이스 시스템이나 병원 관리 시스템에 저장된 방대한 자료 중에서 원하는 자료를 찾아 가져오는 작업은 매우 흔하게 일어납니다. 사전에서 단어의 뜻을 찾는다거나 또는 특정 시설에서 출입이 허가된 사람인지를 체크하는 작업도 흔히 접할 수 있는 룩업 관련 문제입니다.

모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 일반적으로 매우 많은 시간이 소요됩니다. 특히 저장된 데이터가 많아질수록 검색 시간은 크게 증가합니다. 사전에서 단어를 찾는 것을 예로 들어보겠습니다. 대략 170,000개의 단어가 수록된 영어 사전이 있고 특정 단어의 뜻을 찾으려고 합니다. 가장 단순한 방법은 찾으려는 단어와 사전에 나타난 모든 단어를 차례대로 비교하는 것이며, 찾는 단어가 나타나거나 사전의 맨 마지막에 다다르면 종료합니다. 그러나 이 방법은 매우 느리고, O(N)의 시간 복잡도를 가집니다. 여기서 N은 사전에 저장된 영어 단어 수이며, 영어 단어 수는 나날이 증가하고 있습니다.

그러므로 이 작업을 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요합니다. 이 장에서는 해시 테이블과 블룸 필터라는 두 가지 효과적인 구조에 대해 알아볼 것입니다. 이 두 방법을 직접 구현해보고, 장단점을 비교해보겠습니다.