3.2.1 해싱

해싱에 대해 자세히 설명하기에 앞서 한 가지 예를 살펴보겠습니다. 정수를 저장하고 있는 컨테이너가 있고, 이 컨테이너에 특정 정수가 들어 있는지를 빠르게 판단하고 싶다고 가정하겠습니다. 가장 간단한 방법은 부울 타입 배열을 하나 만들고, 입력 정수를 이 배열 원소의 인덱스로 취급하는 것입니다. 만약 새 원소를 삽입한다면 해당 인덱스의 배열 값을 1로 설정합니다. 즉, 새 원소 x를 삽입할 경우 data[x] = true로 설정합니다. 특정 정수 x가 있는지를 알고 싶다면 단순히 data[x] 값이 true인지를 확인하면 됩니다. 이런 방식을 사용할 경우, 원소 삽입, 삭제, 검색의 시간 복잡도는 O(1)입니다. 0부터 9 사이의 정수를 저장하는 용도의 간단한 해시 테이블을 그림 3-1에 나타냈습니다.

▲ 그림 3-1 간단한 해시 테이블