알고리즘에서 '해시 충돌(Hash Collision)' 해결 방법 중 '선형 탐사(Linear Probing)'의 문제점은?

해설

선형 탐사는 충돌 시 다음 빈 슬롯(index+1, index+2...)을 순차 탐색합니다. 채우기율이 높아지면 충돌된 항목들이 연속으로 뭉치는 1차 클러스터링이 발생하여, 삽입/검색 시 긴 연속 구간을 탐사해야 합니다. 이를 개선하기 위해 이차 탐사(Quadratic Probing)나 이중 해싱(Double Hashing)을 사용합니다.