해시 테이블은 사전을 구현하는 효율적인 자료 구조이다.
이론적으로 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것 만큰 오래 걸릴 수 있지만, 평균 수행시간은 O(1)이다.
해시 테이블은 실제 저장된 키의 개수에 비례하는 크기를 가지는 배열을 사용한다.
이에 따라 실제 저장된 키의 키의 개수가 가능한 키의 전체 개수보다 상대적으로 작은 경우 일반 배열에 직접 주소화 방법을 사용하는 것보다 효율적이다.
배열의 인덱스는 키로부터 계산된다.
직접 주소화 방법은 집합 U ={0 ~ m-1} 에서 추출된 키를 가지는 원소로 구성된 동적 집합을 취급한다고 가정하자. (m은 너무 크지 않은 값이다.)
이럴 때 동적 집합을 나타내기 위해 T[m] 으로 표현되는 배열, 즉 직접 주소 테이블을 사용하게 된다.
이 테이블에서의 각 위치는 전제 집합 U에 속한 키와 일치한다.
간단히 말해서 배열의 인덱스 값을 키로 가지도록 하고, 키 값을 통해 배열에 접근하여 값을 얻는 형식이다.
직접 주소화 방법의 단점: U가 매우 크다면 테이블 T를 저장하는 것이 불가하다. 추가로 키들의 집합 K는 U에 비해 상대적으로 작어서 T를 위해 할당된 공간을 낭비한다.
해시 테이블을 사용한다면 검색 시간 O(1)을 유지하면서 저장 공간을 O(K) 만큼으로 줄일 수 있다. 다만 직접 주소화 방법에선느 이 수행시간이 최악의 경우 수행시간이지만, 해시테이블에서는 평균 수행시간에 해당한다.
해싱을 이용한 방법에서는 키 k를 갖는 원소의 위치는 위치 h(k) 에 저장된다. 즉, 키로부터 저장될 위치를 계산하기 위한 해시 함수 h를 사용한다. h 는 전체 집합 U를 해시테이블 T[m] 의 각 위치에 대응시킨다.