선형 조사법(linear probing)을 사용하는 해시 테이블에서 버… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 26년 1회차
선형 조사법(linear probing)을 사용하는 해시 테이블에서 버킷(bucket)을 삭제할 때, 빈 버킷(empty bucket)으로 비워 두지 않고 삭제했음을 표시하는 이유는? (단, 버킷 내 슬롯(slot) 수는 1이다)
1
1차 군집 현상이 발생하지 않게 한다.
2
해시 테이블의 전체 크기를 자동으로 기존 크기의 두 배로 확장 시킨다.
3
충돌로 인해 원래 해시 주소와는 다른 주소에 저장된 레코드에 대한 탐색이 가능하게 한다.
4
해시 테이블에 저장된 모든 레코드의 키값이 항상 오름차순으로 정렬된 상태가 되도록 유지시킨다.
해설
삭제 표시를 남기는 이유는 충돌로 다른 주소에 밀려 저장된 레코드를 계속 탐색할 수 있게 하기 위해서다.
선형 조사법의 탐색은 빈 버킷을 만나면 “없음”으로 종료한다. 중간 버킷을 그냥 비우면 그 뒤로 밀려 저장된 레코드에 도달하기 전에 탐색이 끊기므로, 삭제 표시를 두어 탐색은 건너가고 삽입은 재사용하게 한다.
- 1차 군집은 선형 조사 자체의 성질이라 삭제 표시로 막을 수 없다.
- 테이블 크기 확장(재해싱)은 적재율에 따른 별도 처리로 삭제 표시와 무관하다.
- 해시 테이블은 키 순서를 유지하는 구조가 아니므로 오름차순 정렬과 관계없다.
오류나 개정된 내용이 보이면 알려주세요