전산공무원 - 해싱(hashing)에서 오버플로 처리

홍재연 입니다.
전산공무원 강의 전문 사이트 pass25.com 을 운영 중이고
전산공무원 전문 카페 cafe.daum.net/... 를 운영 중입니다.
최소비용으로 전산공무원에 합격할 수 있는 길을 제공합니다.
전산공무원 시험에 대한 궁금한 내용을 해결할 수 있습니다.
전산공무원 시험 준비에 기본적인 내용입니다.
선형조사법(linear probing)
2차조사법(quadratic probing)
2차계수조사법(quadrafic quotient probing)
이중해싱(double hashing)
연결체인법(linked chaining)
그리고
전산7급에 도전해 보세요.
그 만큼 가치가 있고
전산7급은 그냥 접수될 수 있습니다.
목표는 최소비용으로 전산직 공무원에 합격!

[@user-sp5wr6zh5d]

// 2차계수조사법(quadrafic quotient probing) 2차계수조사법은 키 k로부터 산출되는 몫에 X^2을 곱하여 후속주소로 한다. 즉, 동의어는 홈주소는 같아도 그 몫은 서로 다르기 때문이다. 2차계수조사법은 제2밀집현상을 제거하기 위한 방법이다.

[@user-sp5wr6zh5d]

// 선형조사법(linear probing) •오버플로(overflow)가 발생한 곳에서 가장 가까운 빈 버킷을 찾아 저장한다.(색인증가를 1) •선형개방주소법(linear open addressing)이라고도 한다.

[@user-sp5wr6zh5d]

•선형조사법은 overflow 발생시 색인증가를 1로 한다. •알고리즘은 간단하나 제1밀집(first clustering) 현상이 일어난다. •밀집현상은 키들이 어느 한 곳에 모이는 것으로 충돌이 빈번해지고 검색시간은 증가된다.

[@user-sp5wr6zh5d]

// 2차조사법(quadratic probing) 이차조사법은 충돌이 발생하여 오버플로가 발생하면, 이차함수를 색인증가에 사용한다.

[@user-sp5wr6zh5d]

// 이중해싱(double hashing) •말 그대로 두 개의 해시함수를 이용하는 기법이다. •첫번째 해시함수를 적용하여 충돌과 동시에 오버플로가 발생하면 두 번째 해시함수를 이용한다. •두번째 해시함수의 함수값은 버킷의 빈곳을 탐색하기 위한 조사간격으로 사용된다.

[@user-sp5wr6zh5d]

// 해싱 정리 ① 해시표에서 기본적인 연산은 삽입, 삭제, 탐색 연산으로 효율적으로 구현되어야 한다. ② 해싱 기법은 평균적으로는 균형탐색트리를 이용하는 것보다 우수하다. // Overflow가 발생되는 경우 •연산시간은 반드시 O(1)이 될 수 없다. •최악의 경우는 O(n)이 된다.(성능 저하) // Overflow가 발생되지 않는 경우 •키의 삽입, 삭제, 탐색 연산시간은 O(1)이다. •키 개수와 무관하게 연산시간은 O(1)이다. •단지, 해시함수 계산시간과 버킷탐색시간에 좌우된다.

[@user-sp5wr6zh5d]

•2차조사법은 특정 수만큼 떨어진 곳을 순환적으로 빈 공간을 찾아 저장하는 방법이다. •해서, 2차조사법은 선형조사법에 비해 밀집현상이 줄어든다. •그러나, K와 K'의 i번째 후속주소가 같다면 제2밀집 현상이 일어난다.

[@user-sp5wr6zh5d]

4. 해시테이블에서 오버플로 처리에 관한 설명 중 올바르지 않은 것은? [2002년 기술고시] ① 재해싱(rehashing)은 오버플로를 처리하는 기법 중의 하나이다. ② 선형탐색은 식별자를 밀집시켜 탐색시간을 느리게 만드는 경향이 있다. ③ 이차탐색(quadratic probing)은 오버플로가 발생했을 때 주소를 i^2, -i^2 만큼씩 변경시켜 사용 가능한 버킷(bucket)을 찾는 방법이다. ④ 둘 이상의 식별자가 같은 주소로 사상되면 항상 오버플로가 발생한다. ⑤ 체이닝은 해시표의 버킷을 연결리스트로 구현하여 오버플로 문제를 해결한다.

[@user-sp5wr6zh5d]

2. 해싱에서 충돌 해결법인 Open addressing에 대한 설명으로 틀린 것은? [2001년 서울 7급] ① Linear probing에서는 밀집 현상이 생긴다. ② 오버플로가 일어나면 그 다음 버킷을 하나씩 검사하게 된다. ③ 나누는 수가 소수가 아니면 충돌 발생이 심하게 일어난다. ④ 하나의 버킷이 하나의 슬롯이면, 충돌이 일어나면 바로 오버플로가 일어난다. ⑤ Quadratic probing에서는 밀집 현상이 생기지 않는다.

[@user-sp5wr6zh5d]

3. 해싱의 오버플로(overflow) 처리기법에 대한 설명 중 가장 적절하지 않은 것은? [2021년 군무원 7급] ① 체이닝(chaining)은 버킷을 연결리스트로 구현하는 오버플로(overflow) 처리 기법이다. ② 재해싱(rehashing)은 해시테이블 크기를 늘려서 테이블에 저장된 모든 원소에 대해서 해시값을 재계산한 후 다시 새로운 해시테이블에 저장해야 하므로 시간이 많이 걸린다. ③ 선형조사법(linear probing)은 군집현상(clustering)이 발생하므로 해시테이블의 탐색연산을 위해서는 매우 효율적이다. ④ 이차조사법(quadratic probing)은 선형조사법보다는 군집 현상이 덜 발생한다.

[@user-sp5wr6zh5d]

// 연결체인법(linked chaining) 같은 버킷주소를 갖는 동의어(synonym)들을 연결리스트로 구성하는 방법이다.

[@user-sp5wr6zh5d]

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