3.3.3 열린 주소 지정

충돌을 해결하는 다른 방법으로 열린 주소 지정(open addressing)이 있습니다. 이 방법은 체이닝처럼 해시 테이블에 추가적인 리스트를 붙여서 데이터를 저장하는 방식이 아니라 모든 원소를 해시 테이블 내부에 저장하는 방식입니다. 그러므로 해시 테이블의 크기가 반드시 데이터 개수보다 커야 합니다. 열린 주소 지정 방법의 핵심은 특정 해시 값에 해당하는 위치가 이미 사용되고 있다면 테이블의 다른 비어 있는 위치를 탐색하는 것입니다. 이때 다른 비어 있는 위치를 찾는 방법은 여러 가지가 있을 수 있으며, 이제부터 여러 탐색 방법을 하나씩 알아보겠습니다.