검색 - 이분 검색/해싱

💡

¹ 이분 검색

🖍️ 전체 파일을 두 개의 서브파일로 분리해가면서 key 레코드를 검색하는 방식

• 반드시 정렬된 파일이어야 검색 가능
• 찾고자 하는 값을 중간 key 값과 비교하면서 검색
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦
  ➡︎ 탐색 효율이 좋고 탐색 시간이 적게 소요됨

---

² 해싱

🖍️ 해시 테이블 할당, 해시 함수를 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색하는 방식

해시 테이블

: 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간
주, 보조기억장치에 구성 가능

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

해싱 함수

• 제산법(Division): 키 K를 해시테이블 크기보다 큰 가장 작은 소수 Q로 나눈 나머지를 주소로 삼는 방식 h(K) = K mod Q

• 제곱법(Mid-Square): 레코드 키 값을 제곱한 후 그 중간 부분 값을 주소로 삼음

• 폴딩법(Folding): 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(베타적 논리합)한 값을 주소로 삼음

• 기수 변환법(Radix): 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단, 이를 다시 주소 범위에 맞게 조정하는 방법

• 대수적 코딩법(Algebraic Coding): 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지의 다항식의 계수를 주소로 삼는 방식

• 숫자 분석법(Digit Analysis, 계수 분석법): 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 주소로 삼음

• 무작위법(Random): 난수를 발생시켜 나온 값을 주소로 삼음