대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.
이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.
키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있다면 O(n) 이고 정렬이 되어 있다면 O($log_2n$) 이다. 정렬이 되어 있는 경우의 시간 복잡도가 O($log_2n$) 인 건 이진 탐색 알고리즘 혹은 이진 탐색 트리의 탐색 알고리즘의 시간복잡도를 생각하면 된다.
해싱이 나오게 된 배경은 위에서 설명한 시간복잡도 보다 더욱 빠은 탐색을 필요로 할 때다. 해싱은 이론적으로 O(1)의 시간 안에 탐색을 끝마칠 수도 있다. 해싱은 보통 사전(Dictionary)과 같은 자료 구조를 구현할 때에 최상의 선택이 된다.
*사전 구조(Dictionary)는 맵(Map) 이나 테이블(Table)로 불리기도 한다. 사전 구조는 다음과 같이 탐색 키, 그리고 탐색 키와 관련 있는 값 이렇게 2가지 종류의 필드를 가진다.*
영어 사전을 예를 들자면, 영어 단어가 탐색 키(search key)이고 영어 단어의 뜻풀이가 값(value)이 된다. 사전 구조는 항목들을 탐색 키에 의하여 식별하고 관리한다. 항목들의 위치는 상관 없다. 따라서 항목들을 접근하고 삭제할 때는 단지 키만 있으면 된다.
(키를 삭제하면 키와 관련 있는 뜻풀이까지 함께 날아가기 때문에 단지 키만 삭제하면 되는 것이다.)
*사전 구조에 있는 항목들은 모두 탐색 키를 가지고 있다는 점에서 리스트와 같은 다른 자료구조들과는 구분이 된다. 리스트에도 물론 탐색 키를 같이 넣어서 저장할 수 있지만, 리스트는 근본적으로 위치에 의하여 관리되는 자료구조이다. 반면 사전 구조는 오직 탐색 키에 의해서만 관리된다.*
(리스트에서는 특정 노드를 방문할 때, 해당 노드가 나올 때까지 계속 다음노드를 살펴봐야 한다. 이것 도한 O(n)의 시간복잡도가 요구되는 작업이다.)
*사전 구조에서는 유일한 탐색 키를 사용하기도 하고 동일한 탐색 키를 허용하기도 한다. 예를 들면, 주민등록번호에 의하여 학생들을 관리하는 사전 구조는 유일한 탐색키를 사용하는 경우이다. 그러나 영어 사전의 경우 철자가 동일한 단어가 많은 의미를 가질 수 있기 때문에 중복되는 탐색키를 사용한다.*