배열들은 객체가 직접 배열 인덱스에 매핑되는 경우에 객체를 저장하고 검색하는 데 아주 유용하지만, 항상 그럴 수는 없는 것이다.

예를 들어 여러분은 200명의 고용인들로 운영되는 공장을 소유하고, 고용인들의 봉급을 지급하는 과정을 프로그램으로 기록하기를 원한다고 가정하자. 한 명의 고용인을 표현한 각 객체들을 참조하는 배열로 프로그램을 고안할 것이다. 왜냐하면 각각의 고용인은 고유한 주민등록번호를 가지므로 객체의 주민등록번호 필드로써 고용인 객체를 신속하게 할당하기 위하여 배열 인덱스처럼 주민등록번호를 사용하려고 할 것이기 때문이다.

그러나 문제가 있다. 배열 지수처럼 주민등록번호를 사용하기 위해서는, 각각의 주민등록번호에 해당하는 상당히 많은 수의 메모리를 확보하여야 하는 것이다. 혹시 충분한 크기의 배열을 확보할 수 있는 넉넉한 메모리를 갖고 있을지라도, 혹시 200개의 객체들만을 참조할 뿐이라면 상당한 양의 메모리가 낭비될 것이다.

여전히 주민등록번호를 사용할 수는 있지만 직접적으로는 아니다. 이번에는 더 좁은 범위의 수를 주민등록번호에 할당한다. 200명의 직원 때문에 200개의 엔트리에 10억 개를 매핑하여야만 한다. 이렇게 하면 메모리 낭비 없이 기록을 효율적으로 검색할 수 있다. 이러한 매핑은 '해싱(hashing)'을 통하여 이루어질 수 있다.

해싱은 모든 키들이 같은 배열 색인에 할당되니 않는다는 방식을 이용하여 비트 기호의 스크램블에 의해 배열 인덱스에 기호를 할당하기 위한 컴퓨터 과학 기술이다. 다른 말로, 해싱은 키 값들이 배열 인덱스 전체에 균일하게 분포되도록 이들 비트들을 스크램블 한다. 균일 분포된 200개의 배열 엔트리에 10억 개의 주민등록번호를 매핑하는 것은 각 엔트리에 5백만 개의 주민등록번호를 매핑시키는 것이다.

불행하게도, 배열 인덱스에 대한 키들의 비율이 매우 클 수 있기 때문에(예를 들면, 200에 십억 개), 충돌(같은 배열 인덱스에 두 개 또는 더 많은 키가 할당됨)이 일어날 수 있다.

두 개(5백만은 고사하고) 키가 같은 배열 인덱스에 해시 되었을 때 어떻게 할 것인가? 이 요소에 어떤 값이 기억될까? 이 문제에 대한 다양한 해결책이 있지만, 가장 유명한 해결책 중에 하나는 배열 요소에 값을 기억하지 않는 것이다. 대신에 각각의 배열 요소는 동적으로 성장/수축 가능한 연결 목록을 참조하게 된다. 단순한 값 대신에 키/값 쌍이 노드들에 기억된다.

이 계획안을 다시 생각해 보자. employee 객체는 특별한 주민등록번호가 필요하다. 주민등록번호는 인덱스 20에 해시한다. 그 연결 목록은 노드가 진짜 기호에 맞는 것을 찾거나 찾지 못했을 때까지 통과한 배열 요소 20에 의해 조회된다. 만약 노드가 찾아지면 그 값이 반환된다.

배열 요소와 적당한 연결 목록의 결합으로 형성되는 데이터 구조를 해시 테이블(hash table)이라고 한다. 해싱을 목적으로 연결 목록을 참조하는 각 배열 요소들은 버킷(bucket)이라고 한다.

f(key)=index 표시법은 해시 함수가 배열 인덱스를 생성하기 위하여 키에 적용되었음을 의미하는 것이다. 이 인덱스는 사용중인 인덱스와 충돌하지 않을 것인데, 만약 충돌한다면 새 엔트리가 인덱스된 배열 요소에 의해 참조된 연결 목록에 추가된다. 로드 인자(load factor)는 실행에 영향을 줄 수 있다. 이 비율이 1.0에 가까워질수록, 충돌 수는 더 커진다.