사전 검색의 기본적인 문제에 대해 알아보겠습니다. 옥스퍼드 영어 사전에는 약 170,000개의 단어가 수록되어 있습니다. 앞에서 언급했듯이 선형 검색은 O(N)의 시간을 필요로 합니다. 더 나은 방법은 BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것입니다. 이렇게 사용할 경우 시간 복잡도가 O(log N)이 되기 때문에 선형 검색보다 훨씬 빨라집니다. 그러나 검색 횟수가 크게 증가할 경우 이 정도 연산 속도도 만족스럽지 않을 수 있습니다. 특히 신경 과학 또는 유전자 데이터처럼 수백 수천만 이상의 데이터가 저장되어 있는 경우라면 문제가 더 심각해져서 자료 검색에 며칠이 소요될 수도 있습니다. 이러한 상황에서는 더욱 효율적인 방법이 필요하고, 그중 해시 테이블(hash table)이 괜찮은 방법 중 하나입니다.

해시 테이블의 핵심은 해싱(hashing)입니다. 해싱은 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 또는 해당 숫자에 대응하는 원본 데이터를 추출하는 작업입니다. 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수를 해시 함수(hash function)라고 합니다. 몇 가지 예제를 통해 해시 함수가 왜 필요한지, 그리고 이를 이용하여 어떻게 값을 저장하고 검색하는지에 대해 알아보겠습니다.