해싱함수와 검색 알고리즘

💡 해싱 함수(Hashing Function) 개념

➡️ 해싱 함수(해시 함수)는 데이터를 키로 변환하는 함수. 예를 들어 길고 복잡한 문자열을 짧고 단순한 문자열(또는 수열)로 변경하는 함수이다.

 

📍 해싱 함수 종류

• 해싱 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
• 해싱 함수를 선택할 때 계산과정의 단순화, 충돌의 최소화, 기억장소 낭비의 최소화, 오버플로우(더 이상의 저장할 곳이 없는 상태)가 최소화를 고려해야 한다.

함수	설명
제산법 (Division)	나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방식
제곱법 (Mid Square)	레코드 키값을 제곱한 후에 결과값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용하는 방식
숫자 분석법 (Digit Analysis)	레코드 키를 구성하는 수들이 모든 키들 내에서 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법
폴딩법 (Folding)	레코드 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 사용하는 방식
기수 변환법 (Radix Conversion)	어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방식(어떤 키값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키값을 변환하여 홈 주소를 계산)
무작위 방법 (Random)	난수를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방식

 

💡 검색 알고리즘

📍 순차 검색(Sequential Search)

• 순차 검색은 배열의 처음부터 끝까지 차례대로 비교하여 원하는 테이터를 찾아내는 알고리즘이다.
• 순차 검색은 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고, 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다.

📌 순차 탐색 예제
아래  리스트에서 50을 찾는다.

10

40

30

20

70

100

80

90

50

60

1) 첫 번째 레코드에 있는 10이 50과 같은지 확인한다.(순차 검색 1번 시도)
2) 첫 번째 레코드에 있는 40이 50과 같은지 확인한다.(순차 검색 2번 시도)
...
9) 첫 번째 레코드에 있는 50이 50과 같은지 확인한다.(순차 검색 9번 시도)
➡️ 찾으려는 값과 같으므로 순차 탐색을 종료한다. (총 10개의 데이터에서 50을 찾는데, 9번의 시도로 찾을 수 있다.)

 

📍 이진 검색(Binary Search)

• 이진 검색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘이다.
• 탐색 효율이 좋고 탐색 시간이 적게 소요된다.
• 가운데 레코드 번호를 찾기 위해서는 다음 식을 사용한다. (소수점이 나올 경우 버림 처리한다.)

📌 [공식] 이진 탐색 가운데 레코드 번호

M = (F+L)/2

 

F : 남은 범위 내에서 첫 번째 레코드 번호

L : 남은 범위 내에서 마지막 레코드 번호

M : 남은 범위 내에서 가운데 레코드 번호

 

📌 이진 탐색 예제
아래 정렬되어 있는 레코드에서 14를 찾는다

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1) 데이터의 개수는 15개이므로 가운데 레코드 번호는 (1+15)/2 = 8이다.
2) 14는 8보다 크므로 9부터 15 사이 값이 되며, 가운데 레코드 번호는 (9+15)/2 = 12이다.
3) 14는 12보다 크므로 13과 15 사이 값이 되며, 가운데 레코드 번호는 (13+15)/2 = 14이다.
14를 찾았으므로 이진 검색 종료. ( 15개의 데이터에서 14 레코드를 찾는데 3번의 시도로 찾을 수 있다.)