크기가 7(M=7)인 해시 테이블(hash table)에 이중 해싱(d… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
크기가 7(M=7M=7)인 해시 테이블(hash table)에 이중 해싱(double hashing) 기법을 사용하여 데이터를 삽입한다고 하자. 첫 번째 해시 함수(hash function)는 h1(k)=k mod Mh_1(k)=k \bmod M이고, 충돌이 발생할 경우 사용하는 두 번째 해시 함수는 h2(k)=5−(k mod 5)h_2(k)=5-(k \bmod 5)이다. 이러한 해시 함수를 사용하여 다음과 같은 탐색 키들을 차례대로 삽입한다고 할 때, 삽입이 완료된 후 해시 테이블의 상태는?
1, 15, 3, 6, 10
1
[0][1][2][3][4][5][6]
1153106
2
[0][1][2][3][4][5][6]
6131015
3
[0][1][2][3][4][5][6]
1153106
4
[0][1][2][3][4][5][6]
6131015
해설

삽입 완료 후 테이블은 [0]=6, [1]=1, [3]=3, [4]=10, [6]=15이다.

이중 해싱은 충돌 시 (h1(k)+i⋅h2(k)) mod 7(h_1(k)+i \cdot h_2(k)) \bmod 7 위치를 차례로 탐사한다.

1 → [1], 3 → [3]은 충돌 없이 들어간다.
15: h1=1h_1=1 충돌, h2=5h_2=5 → (1+5) mod 7=6(1+5) \bmod 7=6
6: h1=6h_1=6 충돌, h2=4h_2=4 → (6+4) mod 7=3(6+4) \bmod 7=3 충돌 → (6+8) mod 7=0(6+8) \bmod 7=0
10: h1=3h_1=3 충돌, h2=5h_2=5 → [1], [6] 충돌 → (3+15) mod 7=4(3+15) \bmod 7=4

  • [2]에 15, [4]에 10, [6]에 6인 상태: 충돌 시 한 칸씩 옮기는 선형 탐사의 결과다.
  • [0]에 6, [5]에 10, [6]에 15인 상태: 10은 [1], [6]을 거쳐 [4]에 들어가야 한다.
  • [2]에 15, [5]에 10, [6]에 6인 상태: 15부터 두 번째 해시 함수를 올바로 적용하지 않은 결과다.

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

이어서 풀어보기

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