버킷 용량 C=2인 버킷들의 주소 공간이 0 \sim (N-1)인 해시… | [7급 국가직 데이터베이스론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 데이터베이스론] 20년 1회차
버킷 용량 인 버킷들의 주소 공간이 인 해시에서 키를 로 하는 해시 함수 이고, 값은 5이다. 이때 일련의 값들이 3, 5, 7, 9, 11, 13, 18, 14 순서로 삽입된 후 4번 버킷의 값은? (단, 버킷에서의 충돌은 충돌 발생 버킷 주소 에 대하여 을 통해 지정하는 선형탐색 개방 주소법을 이용하여 해결한다)
1
5, 14
2
3, 13
3
9, 14
4
9, 18
해설
삽입이 끝난 뒤 주소 4 버킷에는 9, 18이 저장된다.
홈 주소 에 따라 3→3, 5→0, 7→2, 9→4, 11→1, 13→3으로 저장되며, 버킷 3은 3과 13으로 용량 2가 가득 찬다.
18은 홈 주소 3이 가득 차 선형 탐색으로 다음 주소 4에 들어가 9와 함께 저장되고, 14는 홈 주소 4가 가득 차 인 버킷 0에 5와 함께 저장된다.
- 5, 14는 버킷 0의 최종 값이다.
- 3, 13은 버킷 3의 최종 값이다.
- 9, 14는 18이 먼저 버킷 4를 채워 14가 버킷 0으로 넘어간다는 점을 놓친 조합이다.
오류나 개정된 내용이 보이면 알려주세요