해시 충돌

서로 다른 두 개의 입력값에 대해 해시 함수가 같은 출력값을 반환할 때 해시 충돌이 발생한다. 이런 현상을 발생시키지 않는 해시 함수를 ‘충돌 저항이 있다’고 표현한다. 만약 충돌 저항이 없거나 값이 다른 두 입력값이 같은 결과를 산출하는 드문 경우가 발생하면 충돌 해결 전략을 세워야 한다.

기본적으로 충돌 해결 전략이란 서로 다른 두 입력값이 같은 결과를 산출하는 상황을 처리하는 방법을 말한다. 만약 해시 테이블에 값 하나에 대한 산출 공간만 있다면 결국 출력값 중 하나는 소실될 것이다.

이런 상황을 처리하는 간단한 방법은 해시 테이블의 각 셀 안에 리스트를 만들어 놓는 것이다. 대부분의 셀에는 값 하나만 있겠지만, 그림 4-9에 나와 있듯이 충돌이 발생하면 해시 테이블 셀에서 키와 값의 리스트를 관리하는 것이다. 이 방법이 충돌 문제에 대한 일반적이고 논리적인 해결책이다.

▲ 그림 4-9 값에 대한 연결 리스트를 유지하는 것처럼 충돌 해결 전략을 사용해 해시 함수의 충돌을 관리한다