[2과목 소프트웨어 개발] 데이터 입·출력 구현 - 039. ⭐ 검색 - 이분검색 / 해싱

1. 이분검색 (Binary Search)

• 전체 파일을 두 개의 서브파일로 분리해가면서 Key 레코드를 검색
• 파일의 중간값과 비교하면서 검색을 반복
• 중간 레코드 번호 M = (F + L) / 2 (F:첫 번째, L:마지막)

2. 해싱 (Hashing)

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

1) 해시 테이블 (Hash Table)

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

2) 해싱 함수(Hashing Function)

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

 

📖 Reference

2023 시나공 정보처리기사 필기 : 네이버 도서