이중해싱(double hashing)을 이용하는 크기가 5인 해시테이블… | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 13년 1회차
이중해싱(double hashing)을 이용하는 크기가 5인 해시테이블(hash table)에 데이터 6, 3, 8, 18이 순서대로 입력된다. 마지막 데이터인 18이 입력될 때 발생하는 충돌의 횟수는? (단, 1차 해싱함수는 h(k) = k mod 5이고, 2차 해싱함수는 h'(k) = 5-(k mod 5) 이다)
1
0
2
1
3
2
4
3
해설

18을 넣을 때 충돌은 2회 발생한다.

6은 6 mod 5=16 \bmod 5=1, 3은 3에 저장된다. 8은 3에서 충돌하고 2차 해싱 이동 폭 h′(8)=5−3=2h'(8)=5-3=2로 (3+2) mod 5=0(3+2) \bmod 5=0에 저장된다.

18은 18 mod 5=318 \bmod 5=3에서 충돌(1회), 이동 폭 h′(18)=2h'(18)=2로 0에서 충돌(2회), 다음 (0+2) mod 5=2(0+2) \bmod 5=2는 비어 있어 저장된다.

  • 0회: 1차 해시 주소 3은 이미 3이 차지하고 있다.
  • 1회: 이동한 주소 0도 8이 차지하고 있다.
  • 3회: 세 번째 탐사 위치 2는 비어 있어 더 충돌하지 않는다.

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

이어서 풀어보기

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