다음 그림은 키 값에 대한 해시함수 h의 결과와, 확장 가능 해싱(ex… | [7급 국가직 데이터베이스론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 데이터베이스론] 17년 1회차
다음 그림은 키 값에 대한 해시함수 h의 결과와, 확장 가능 해싱(extendible hashing) 기법에 의해 최초에 키 값 4, 8, 9를 순서대로 입력하여 수행한 결과이다. 이후 키 값 11, 7, 2, 5, 13을 순서대로 입력하는 경우에 대한 설명으로 옳은 것은? (단, 버킷(bucket)의 크기는 2이고 입력된 키 값은 삽입한 순서대로 버킷 내의 왼쪽부터 저장된다)
키 값해시함수 h(키 값)
41010
80001
91101
111110
70110
21111
50111
130101

문제 이미지
1
키 값 7이 삽입될 때 새 버킷이 생성된다.
2
모든 키 값이 삽입된 후 버킷의 개수는 5이다.
3
모든 키 값이 삽입된 후 디렉토리 인덱스 010이 가리키는 버킷에는 2개의 키 값이 존재한다.
4
모든 키 값이 삽입된 후 디렉토리 인덱스 111이 가리키는 버킷의 첫 번째 키 값은 11이다.
해설

모든 키를 삽입하면 디렉토리 인덱스 111이 가리키는 버킷의 첫 키 값은 11이 되므로 이 설명이 옳다.

디렉토리는 해시값의 앞쪽 비트를 쓴다. 11(1110) 삽입 시 인덱스 1 버킷이 넘쳐 전역 깊이 2로 분할되어 10→[4], 11→[9, 11]이 된다. 7(0110)은 0쪽 버킷 [8, 7]에 들어간다.

2(1111) 삽입 시 [9, 11]이 넘쳐 전역 깊이 3으로 분할되어 110→[9], 111→[11, 2]가 된다. 5(0111)는 0쪽 버킷을 00→[8], 01→[7, 5]로 나누고, 13(0101)은 다시 010→[13], 011→[7, 5]로 나눈다.

  • 키 값 7 삽입 때 새 버킷 생성: 0쪽 버킷에 빈자리가 있어 분할이 일어나지 않는다.
  • 최종 버킷 개수 5개: [8], [13], [7, 5], [4], [9], [11, 2]로 6개이다.
  • 인덱스 010 버킷에 키 2개: 13 하나만 저장되어 있다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 데이터베이스론] 17년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 데이터베이스론 기출문제 암기장 전체 보기