선형 탐색

선형 탐색(linear probing)은 가장 간단한 탐색 방법입니다. 선형 탐색은 특정 해시 값에서 충돌이 발생하면 해당 위치에서 하나씩 다음 셀(cell) 위치로 이동하면서 셀이 비어 있는지를 확인하고, 비어 있는 셀을 찾으면 원소를 삽입합니다. 즉, hash(x)에 해당하는 셀이 이미 채워져 있다면 hash(x + 1) 위치의 셀을 확인합니다. 만약 hash(x + 1) 셀도 사용 중이라면 다시 hash(x + 2) 셀을 검사합니다.

그림 3-7과 그림 3-8은 선형 탐색을 사용하는 해시 테이블의 삽입 및 검색 동작을 보여줍니다.

▲ 그림 3-7 선형 탐색을 사용하는 해시 테이블의 기본 동작