📌 데이터 입, 출력 구현 - 검색 : 이분 검색/해싱

 

 

목차

 

이분 검색

• 이분 검색(이진 검색, Binary Search)은 전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드를 검색하는 방식이다.
• 이분 검색은 반드시 순서화된 파일이어야 검색할 수 있다.
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색한다.
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요된다.
• 중간 레코드 번호 M = (F+L)/2 (단, F : 첫 번째 레코드 번호, L : 마지막 레코드 번호)

 

🔔 예) 1~100 까지의 숫자 중 15를 찾는 데 걸리는 횟수는?

① 첫 번째 값(F)과 마지막 값(L)을 이용하여 중간 값 M을 구하여 찾으려는 값과 비교한다.

M = (1+100)/2 = 50.5 => 50(정수만 취한다.)

 

② 50이 찾으려는 값과 같은지, 아니면 작은지, 아니면 큰지를 확인한다. 50은 찾으려는 값 보다 크다. 그러므로 찾으려는 값은 1~49 사이에 있다. => 1회 비교

 

③ 이제 첫 번째 값은 1이고 마지막 값은 49이다. 찾으려는 값이 50사이에 있지만 50은 아니므로 49가 마지막 값이 된다. 다시 중간 값을 구한다.

M = (1+49)/2 = 25 => 2회 비교

 

④ 25는 찾으려는 값 보다 크다. 그러므로 찾으려는 값은 1~24 사이에 있다. 다시 중간 값을 계산한다.

M = (1+24)/2 = 12.5 => 12 => 3회 비교

 

⑤ 12는 찾으려는 값보다 작다. 그러므로 찾으려는 값은 13~24 사이에 있다.

M = (13+24)/2 = 18.5 => 18 => 4회 비교

 

⑥ 18은 찾으려는 값보다 크다. 그러므로 찾으려는 값은 13~17 사이에 있다.

M = (13+17)/2 = 15 => 15 => 5회 비교

 

⑦ 15는 찾으려는 값과 같다.

※ 총 비교 횟수는 5회이다.

 

 

해싱

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

 

📌 해시 테이블(Hash Table)

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

 

버킷 (Bucket)	하나의 주소를 갖는 파일의 한 구역을 의미한다. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.
슬롯(Slot)	한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.
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-Squre)	레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식이다.
폴딩법(Folding)	레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식이다.
기수 변환법(Radix)	키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위 맞게 조정하는 방법이다.
대수적 코딩법 (Algebraic Coding)	키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식이다.
숫자 분석법 (Digit Analysis, 계수 분석법)	키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식이다.
무작위법(Random)	난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식이다.