▲ 그림 3-8 해시 테이블이 가득 차서 새 원소를 삽입할 수 없음

그림 3-7에 나타났듯이 주어진 데이터의 해시 값에 해당하는 위치가 이미 다른 값으로 채워져 있다면 다음으로 비어 있는 위치에 새 데이터를 삽입합니다. 그림 3-7에서 처음에 세 개의 원소를 삽입했더니 해시 테이블의 특정 위치에 서로 인접한 군집 형태로 값이 채워졌습니다. 만약 이 구간에 해시 값을 갖는 새 원소가 들어오면 이 군집은 더욱 커지게 됩니다. 만약 원소 검색을 할 경우, 해시 함수에서 반환한 위치가 큰 군집의 시작 위치를 가리킨다면 클러스터의 맨 마지막 위치까지 선형 검색을 해야 합니다. 그러므로 검색 속도가 크게 느려질 수 있습니다.

즉, 데이터가 특정 위치에 군집화(clustering)되는 경우에 문제가 발생하게 됩니다. 데이터가 군집화된다는 것은 특정 해시 값이 너무 자주 발생해서 데이터가 몇 개의 그룹으로 뭉치는 형태로 저장된다는 의미입니다. 예를 들어 크기가 100인 해시 테이블이 있는데, 대부분의 키가 3에서 7 사이의 해시 값으로 변환된다고 생각해보겠습니다. 이 경우 대부분의 데이터가 3~7 이후 위치에 차례대로 저장될 것이고, 이로 인해 검색 속도는 급격하게 느려질 것입니다.