이중해싱(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은 , 3은 3에 저장된다. 8은 3에서 충돌하고 2차 해싱 이동 폭 로 에 저장된다.
18은 에서 충돌(1회), 이동 폭 로 0에서 충돌(2회), 다음 는 비어 있어 저장된다.
- 0회: 1차 해시 주소 3은 이미 3이 차지하고 있다.
- 1회: 이동한 주소 0도 8이 차지하고 있다.
- 3회: 세 번째 탐사 위치 2는 비어 있어 더 충돌하지 않는다.
오류나 개정된 내용이 보이면 알려주세요