자료구조 탐색부분 리포트

목차

1. 선형 탐색(Linear Search)

2. 제어 탐색(Controlled Search)

3. 블록 탐색(Block Search)

4. 트리탐색(Tree Search)

5-1. 해싱(Hashing)
5-2. 해싱함수(Hashing Function)의 종류
5-3. 과잉 상태의 처리

본문내용

2
3
PARK
4
LEE
CHA
5
SONG
6
7
YOON
8
KIM
HWANG
9
KWACK
SHIN
10
11
SHU
12
HONG
13
SUNG
오버플로우 공간
CHOI
HAN
※ 위 표에서 홈 주소가 같으면 일단은 버킷에 다 넣고, 그래도 홈 주소가 같은 레코드가 존재한다면 오버플로 공간에 보관한다.
5-2. 해싱함수(Hashing Function)의 종류
위에서 언급한 바와 같이 레코드를 홈 주소로 바꿀려면
① 레코드의 키를 일단 해싱함수로 정리하고,
② 정리된 입력값에 대한 해싱 함수의 값을 계산한다.
③ 계산한 값이 해쉬표의 정해진 범위의 값이 아니면, 그 범위의 값으로 조정하느
3가지의 단계를 거친다.
1) 해싱함수의 종류
방 법
함 수
제산방법
입력값을 주어진 X로 나눈 나머지
제곱방법
(키값)2한 값의 중간부분을 선택하여 번지로 선택
Folding
키를 여러 부분으로 나누고, 각 부분의 값을 계산하여 번지로 선택
숫자분석법
상품 번호나 수로 구성된 키들의 그 수 자체를 번지로 선택
진수변환법
임의의 진법으로 키를 변환하여 번지로 선택
대수적코딩법
①키를 이루고 있는 각 자리의 비트수를 다항식의 계수로 간주
②이 다항식을 해시표의 크기로부터 정한 다항식으로 나누고
③이 때, 얻은 나머지 다항식의 계수룰 번지로 선택
무작위방법
난수 발생 프로그램을 이용하여 난수를 발생시켜 각 키의
번지를 산출하는 방법
5-3. 과잉 상태의 처리
해싱의 단점은 해싱 함수로 나온 홈 번지들이 충돌할 경우가 있다는 것이다. 이 때 버킷이 충돌을 해결할 정도로 많이 준비된다면 기억공간의 낭비가 심할 것이다. 충돌과 과잉 상태의 처리기법은 다음과 같다.(단, 조건은 버킷이 하나라는 전제 아래이다.)
1) 선형방법 : 충돌이 발생할 경우, 빈 영역이 발견될 때까지 순차적으로 리스트를 계속 찾아서 충돌을 야기시킨 키를 충돌된 영역에서부터 찾아나가서 첫 번째 빈 영역에 위치시켜서 수행하는 방법. 가장 간단한 방법. 레코드를 제거할 경우 선형이라서 레코드의 작업이 쉽지 않고, 군집현상(조절한 ki의 주소와 뒤로 밀린 ki-1의 주소가 밀려서 이후 후속 주소들이 모두 같게 되는 경우)이 발생한다. 이 현상은 난수방법이나 2차계수법으로 개선될 수 있다.
2) 난수방법 : 난수 계산프로그램을 이용해 해시표의 홈 주소를 택하여 충돌을 해결하는 방법. K를 저장해야 하는데 그 자리에 이미 다른 레코드가 저장되어 있으면, 난수 프로그램으로 나온 수를 K의 홈 주소에 더해서 그 주소를 K의 후속 주소로 사용한다.
3) 2차처리법 : 선형방법의 군집현상 해소방법. K의 홈주소 자리에 이미 레코드가 존재하면 충돌이 발생한 곳에서 비교적 먼 자리에 K를 위치시키는 것
4) 2차계수법 : 2차처리법에서 K의 새로운 홈 주소를 만드는 방법은 일치하지만, 그 식에서 상수대신에 K 자신을 일정한 함수로 하여 K와 기존의 K`의 후속주소 값이 달라진다.
※ 이상 1)∼4)는 충돌을 유발한 레코드를 처리하는 기법으로 해시표 내의 자리를 한 규칙으로 결정하고, 그들(충돌을 유발한 레코드)을 저장하는 방법을 설명하였다.
5) 연결방법 : 충돌이 다른 충돌을 생기게 하는 가능성을 제거시키는 것
① 직접 연결기법 : 레코드를 저장하는 부분과 포인터를 보관하는 부분을 가진 버킷을
단위로 이루어진 해시표만을 두고 유사 레코드들을 연결 리스트로
구성하여 저장한다.
② 간접 연결기법 : 해시표와는 다른 기억 공간을 하나 더 설정하여 유사 레코드들을
처리하는 방법
6) 오버플로 공간 처리법 : 과잉상태를 유발한 레코드들을 모두 오버플로 공간에 저장
하는 방법. 오버플로 상태 발생 확률이 적을 경우 효율적.

키워드

자료구조,   탐색,   자료,   자료구조탐색,   자료 탐색,   자료구조 리포트