해시테이블(hash table)

해시테이블은 효율적인 탐색을 위한 자료구조로서 KEY값을 VALUE에 대응시킨다. 간단한 해시테이블을 구현하기 위해 연결리스트와 해시 함수 코드를 사용한다.

키와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다.

1. 처음엔 키의 해시 코드를 계산한다. 키의 개수가 무한한데 반해 키의 자료형은 보통 INT 혹은 LONG로 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다.

2. 그다음엔 해시 코드를 이용해 배열의 인덱스를 구한다. 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있다.

3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 등의 충돌을 대비하기 위해 반드시 연결리스트를 이용한다.

충돌은 입력값의 범위보다 출력값의 범위가 좁은 경우에 발생한다. 대표적인 예시로 비둘기집 원리와 생일 문제가 있다.

비둘기집 원리

n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다.

생일 문제

사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 365개(2월 29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.

키에 상응하는 값을 찾기 위해서는 키로부터 해시 코드를 계산하고, 이 해시 코드를 이용해 인덱스를 계산한다. 그 다음엔 해당 키에 상응하는 값을 연결리스트에서 탐색한다.