31. 검색 - 이분 검색 / 해싱

이분 검색

• 이분 검색(이진 검색, Binary Search)은 전체 파일을 두 개의 서브파일로 분리해가면서 Key 레코드를 검색하는 방식이다.
• 이분 검색은 반드시 순서화된 파일이어야 검색할 수 있다.
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색한다.
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요된다.
• 중간 레코드 번호 M= $(F+L)/2$ (단, F: 첫 번째 레코드 번호, L: 마지막 레코드 번호)
• 예제 1~100까지의 숫자 중 15를 찾는 데 걸리는 횟수는?
  1. 첫 번째 값(F)과 마지막 값(L)을 이용하여 중간값 M을 구하여 찾으려는 값과 비교한다. M = $(1+100)/2$ = 50.5 → 50(정수만 취한다.)
  2. 50이 찾으려는 값과 같은지, 아니면 작은지, 아니면 큰지를 확인한다. 50은 찾으려는 값보다 크다. 그러므로 찾으려는 값은 1~49 사이에 있다. → 1회 비교
  3. 이제 첫 번째 값은 1이고 마지막 값은 49이다. 찾으려는 값이 50 사이에 있지만 50은 아니므로 49가 마지막 값이 된다. 다시 중간값을 구한다.
     M = $$(1+49)/2 = 25 → 2회 비교
  4. 25는 찾으려는 값보다 크다. 그러므로 찾으려는 값은 1~24 사이에 있다. 다시 중간값을 계 산한다. M = $$(1+24)/2 = 12.5 → 12 → 3회 비교
  5. 12는 찾으려는 값보다 작다. 그러므로 찾으려는 값은 13~24 사이에 있다.M = $$(13+24)/2 = 18.5 → 18 → 4회 비교
  6. 18은 찾으려는 값보다 크다. 그러므로 찾으려는 값은 13~17 사이에 있다. M = $$(13+17)/2 = 15 → 5회 비교
  7. 15는 찾으려는 값과 같다.
     ※ 총 비교 횟수는 5회이다.

해싱

• 해싱(Hashing)은 해시 테이블(Hash Table)이라는 기억공간을 할당하고, 해시 함수(Hash Function)를 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소(Home Address)를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다.

• 해시 테이블(HashTable)

  • 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있다.

    버킷(Bucket)	- 하나의 주소를 갖는 파일의 한 구역을 의미한다. - 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.
    슬롯(Slot)	한개의 레코드를 저장할 수 있는 공간으로 개의 슬롯이 모여 하나의 버킷을 형성한다.
    Collision(충돌 현상)	서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상이다.
    Synonym	충돌로 인해 같은 Home Address를 갖는 레코드들의 집합이다.
    Overflow	계산된 Home Address Bucket 내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러 개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수 있다.

• 해싱 함수(Hashing Function)

  제산법(Division)	레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, 즉 h(K) = K mod Q이다.
  제곱법(Mid-Square)	레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식이다.
  폴딩법(Folding)	레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식이다.
  기수 변환법(Radix)	키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법이다.
  대수적 코딩법 (AlgebraicCoding)	키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식이다.
  숫자 분석법(Digit Analysis, 계수 분석법)	키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식이다.
  무작위법(Random)	난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식이다.

• Collision(충돌 현상) 해결 방법

  • 체이닝(Chaining): Collision이 발생하면 버킷에 할당된 연결 리스트(Linked List)에 데이터를 저장하는 방법입니다.
  • 개방 주소법(Open Addressing): Collision이 발생하면 순차적으로 그 다음 빈 버킷을 찾아 데이터를 저장하는 방법입니다.
  • 재해싱(Rehashing): Collision이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방법입니다.

출처: 2024 시나공 정보처리기사 필기 기본서