[2019 5급 공무원 2차] 자료구조론 제 2문

2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 2문

 

제 2 문. 크기가 13인 해시 테이블에서 다음과 같은 해시 함수가 주어지고 10개의 데이터를 차례대로 삽입한다고 할 때, 물음에 답하시오.

 

○ 해시 함수 : h(k) = k mod 13

○ 데이터 : 38,14,10,12,3,26,8,7,5,18

 

 

1) 오버플로우(overflow) 해결을 위해 선형조사법(linear probing)을 사용하는 경우 해시 테이블을 보이시오. (4점)

 

* 이상적인 Hash Table은 하나의 key값이 하나의 value만을 가지도록 하는게 가장 좋다. 하지만 Hash Table의 크기는 한정되어 있어서 특정 Inut 값의 해시 결과인 key값이 중복되는 경우(충돌, Overflow)가 존재하고 이를 해결하기 위한 여러 방법 중 linear probing를 쓰면 다음과 같다.

 

* linear probing key 값의 충돌,Overflow 발생시 key값의 바로 다음칸 (key+1)을 조사, 비어있다면 (key+1)에 저장, 비어있지 않다면 (key+2) 확인, 비어있지 않다면 (key+3) 확인....

즉, 선형적으로 탐색하며 비어있는 위치를 찾아 data를 저장하는 방법이다.

 

 

해설)

주어진 각각의 데이터를 해시함수 h(k)에 넣은 결과 값은 다음과 같다.

 

데이터 : 38,14,10,12,3,26,8,7,5,18

h(k) 결과값 (key)

12,1,10,12,3,0,8,7,5,5

 

linear probing 방법으로 차례대로 데이터를 넣었을 때의 Hash Table은 다음과 같다.

 

 

 

 

 

 

 

2) 오버플로우 해결을 위해 이중 해싱(double hashing) 기법을 사용하는 경우 해시 테이블을 보이시오. (단, 두 번째 해시 함수 h'(k)는 다음과 같다) (6점)

 

* double hashing : 이 방법은 두 번째 해시함수를 두고, 충돌,Overflow가 발생했을 때 원래 해시함수가 아닌 두 번째 해시함수로 비어있는 위치에 값을 할당하는 방법이다.

 

 

h'(k) = 5-( k mod 5)

 

double hashing 방법으로 차례대로 데이터를 넣었을 때의 Hash Table은 다음과 같다.

 

 

 

 

* 세 번째 충돌 : 마지막 data 18을 넣을 때 세 번째 충돌이 발생한다. 첫 번째 해시 함수로 인한 값 h(18) 의 key 값 5에서 충돌이 한번 일어나고, 이중해싱에 의한 두 번째 해시함수로 인한 값 h'(18)의 key 값 2에서 충돌이 또 발생한다. 따라서 이중해싱 방법으로는 현재 주어진 데이터와 이중 해싱함수로는 마지막 데이터 18에게 유일한 key값을 부여할 수 없다. 따라서 이차조사법, 체이닝 등 다른 방법을 사용하여 데이터를 할당해야할 것이다.

 

 

3) 오버플로우 해결을 위해 이차조사법(quadratic probing)을 사용하는 경우 해시 테이블을 보이시오. (단, 다음 조사할 위치를 결정하는 식 h'(k)는 다음과 같다. (4점)

 

h'(k) = (h(k) + inc^2) mod 13 for inc = 1,2 ...

* quadratic probing : 이 방법은 선형 조사법처럼 다음 위치를 탐색하는 방법이지만 key+n( n = 1,2,3....)이 아닌 상단에 제시된 새로운 해시 함수 h'(k)를 통해 inc값을 하나씩 늘려가며 비어있는 위치를 찾아 할당해주는 방법이다.

 

quadratic probing 방법으로 차례대로 데이터를 넣었을 때의 Hash Table은 다음과 같다.

 

 

 

4) 1),2),3)의 수행결과를 사용하여 선형조사법, 이중 해싱, 이차조사법의 성능을 충돌 횟수 기준으로 비교하시오. (6점)

 

해설 )

 

 

 주어진 데이터에서 선형조사법과 이차조사법에서는 총 충돌 횟수가 4로 동일한 성능을 보이지만 이중 해싱 방법에서는 세 번째 충돌시에도 똑같은 key값을 발견하게 되어 마지막 데이터에 대해 고유한 key값을 부여하지 못하게 된다. 따라서 이중해싱이 아닌 체이닝, 재해싱 방법이나 이미 조사를 끝낸 선형 조사법, 이차 조사법을 통해 해시테이블을 구성해야한다.