C로 구현한 가상해싱

소개글

C로 구현한 가상해싱입니다.
자세한 내용은 파일 참고하세요

1. 문제정의
가상 해싱(virtual hashing) 기법을 이용하여 레코드를 저장, 삭제, 검색하는 프로그램을 구현한다.

가상 해싱(virtual hashing) 기법은 해싱 함수를 하나만 사용하는 것이 아니라 여러 개의 해싱 함수를 사용하는 것이 특징이다. 해싱 함수는 제산 잔여 기법을 기초로 한다.

- 구현사항
1) 트랜잭션 파일은 삽입(I), 삭제(D), 검색(S) 3가지 명령어로 구성된다.
2) 레코드는 Key와 Item으로 구성되며 key는 양의 정수, item은 10자 이내의 문자열이다.
3) 초기 버킷의 개수는 100개, 버킷의 크기는 4이다.
4) 해싱 함수는 [ hi : 주소 = 키 mod (2i * N), I = 1, 2, … ]을 사용한다.
본 과제에서 N은 100이다.
5) 삭제 명령어로 인해 버킷이 비면 그 버킷을 회수한다.
6) 오류가 발생하면 트랜잭션을 종료하지 말고 오류 메시지를 출력 후 다음 트랜잭션을 수 행한다.

2. 프로그램 개발환경
운영체제 : windows XP
프로그래밍 언어 : C언어
프로그래밍 도구 : microsoft visual C++

3. 프로그램 매뉴얼 :

- 실제 구현상에서 각 버킷은 입력/삭제의 갱신이 일어날 때마다 bubble sort를 이용하여 항상 버킷을 오름차순으로 정렬한다.
- 버킷 사이즈가 리사이징 될 때마다 key 값을 제외한 나머지 값은 0으로 초기화 된다. 단, key값은 int 표현의 가장 큰 값, 0x7FFFFFFF 로 표현한다. 이는 위의 항목에서 오름차순으로 정렬 할 때, 값이 입력되지 않은 버킷의 공간 (NULL)을 아래쪽으로 내리기 위함이다.
- 각각의 버킷은 고유의 제수를 가지고 있다. 단, 모든 키 값에 대하여 처음으로 나누는 제수는 bucket_size에 해당하는 100이고, overflow 여부에 따라 해당 버킷의 div, 즉 제수값에 따라 버킷을 이동하며 제산잔여기법을 사용하여 삽입/분할을 한다.
- 한번의 overflow에 대해 버킷의 크기는 2배로 증가한다. 즉, 초기의 버킷 크기가 100이라면, 한번의 overflow를 거쳐 200, 2번이면 400, 3번이면 800으로, 계속해서 반복해서 증가한다.
- 만약 가장 최근에 증가된 버킷에 어떤 데이터도 입력되어 있지 않다면 그 overflow 발생 횟수를 1 감소시키며 버킷의 크기를 1/2로 감소시킨다.
가장 최근에 증가된 버킷은 (*bucket_size ~ *bucket_size-1) 로 정의되며, 이는 100~199, 200~399, 400~799, ..의 구간을 나타낸다. (단, n은 현재 overflow가 발생한 횟수, bucket_size는 기본 버킷의 크기 100을 나타낸다.)
- 입력에 대하여 다음 과정을 수행한다.
1) 동일한 입력값이 현재 저장되어 있는지를 검사한다. 만일 동일한 값이 발견되면 입력 실패를 출력한다.
2) 현재 동일한 입력값이 들어있지 않으면, 제산 잔여기법을 사용하여 해싱키를 만들어 해당 버킷에 데이터를 입력한다. 이 때, 이미 버킷에 데이터가 가득 차 있을 경우 해당 버킷의 데이터 4개와 새로 입력된 데이터 1개를 가지고 overflow 연산을 수행한다.
3) overflow연산의 결과로 다시 overflow가 발생할 경우, 제수를 증가시키며 overflow 연산을 반복한다.
4) 현재 데이터 5개가 모두 분배 되었을 경우, overflow 연산을 종료하고 입력을 종료한다.
- 삭제에 대하여 다음 과정을 수행한다.
1) 삭제하고자 하는 데이터를 키 값의 해싱을 통해 검색하여 해당 버킷에 random access를 수행한다.
2) 버킷의 데이터를 모두 선형 탐색하고, 데이터가 존재할 경우 삭제를 수행한다. 존재하지 않는 데이터에 대해서는 삭제 실패 메시지를 출력한다.
3) 데이터의 공백을 sort 연산을 통해 정리한 뒤, 해당 버킷의 데이터 개수가 0이면 버킷이 포함된 레코드를 검사하여 레코드에 데이터가 존재하지 않으면 resizing ()을 통해 버킷의 총 길이를 축소한다.
- 검색에 대하여 다음 과정을 수행한다.
1) 제산잔여기법을 통해 해싱키를 생성하고 해당 버킷으로 접근한다.
2) 버킷의 데이터를 순차 검색하여 값을 발견할 경우 성공 메시지와 item 명을 출력한다.
3) 실패할 경우 실패 메시지를 출력한다.

4. 프로그램 소스코드(주석 포함)
- 문서 후면에 별첨

5. 참고문헌 : 파일구조, 이석호저, 정익사

컴파일 실행환경

마이크로소프트 비주얼시++

압축파일 내 파일목록

Virtual hashing.cpp
virtual hashing.hwp

참고 자료

없음