확장성 해싱 설계 및 구현

소개글

확장성 해싱 설계 및 구현에 대한 보고서 자료입니다.

목차

1. 과제 설명

2. 프로그램 설명

3. 프로그램 실행 과정 설명

4. 프로그램 소스 분석

본문내용

값과
s=0;//대상 버킷의 모조키값을 비교한다.
for(j=0;j if(exHashing->key[i][j]!=bucket[target].bit[j])//그 모조키의 p-1비트들은 모두 같은 버킷을 찾는다.
s=1;
if(s==0)//s가 0이라면 p-1비트까지 모두 같다는 의미이므로
if(bucket[target].p==exHashing->ptr[i]->p//대상 버킷의 지역깊이 p와 해당 버킷의 지역깊이가 같은지 확인하여
&&bucket[target].th!=exHashing->ptr[i]->th)
buddy=exHashing->ptr[i]->th;//만약 같다면 그 버킷이 대상 버킷의 버디버킷이 된다.
}
return buddy;
}
//확장성 해싱의 두번째 버킷을 찾아서 버킷의 인덱스를 리턴하는 함수
int findSecondBucket(void){
int i, find=0, first, second=-1;
first=exHashing->ptr[0]->th;//디렉터리의 처음 포인터가 가리키는 버킷이 첫번째 버킷이다.
i=0;
while(find!=1){//디렉터리의 버킷 포인터를 처음부터 확인하여
if(exHashing->ptr[i]->th!=first){//첫번째 버킷과 다른 버킷이 나오면
second=exHashing->ptr[i]->th;//그것이 두번째 버킷이고
find=1;
}
i++;
}
return second;//이것을 두번째 버킷으로 리턴해준다.
}
//주어진 데이터를 적절한 주소로 변환 후, 주소를 2진수로 바꾸어 mojokey[]에 저장하는 함수
int* hash_function(int data){
int i, tmp;
float temp;
tmp=data%8192;//제산 잔여 함수를 사용하였다. 제수는 8192이다.
temp=(float)127/(float)8192;
tmp=(int)((float)tmp*temp);//주소값을 0-127사이의 값으로 조정하였다.
for(i=0;i<6;i++){//0-127사이의 값을 이진수로 바꾸어준다.
mojokey[5-i]=tmp%2;
tmp=tmp/2;
}
srand((unsigned)data);//실 데이터를 랜덤함수 초기값으로 사용한다.
for(i=6;i<12;i++)
mojokey[i]=rand()%2;//나머지 6자리 비트는 랜덤함수에 의해 부여한다.
return mojokey;
}
//주어진 버킷이 가득 찼는지 확인하는 함수
int isFull(int target){
int i, count=0;
for(i=0;i<3;i++)//버킷을 조사하여 비어있는 곳이 있다면
if(bucket[target].stg[i]==-1)count++;//count변수값을 1증가시킨다.
if(count==0)return 1;//count값이 0이라면 비어있는 곳이 없다는 의미이므로 즉 가득찼음을 의미.
elsereturn 0;//가득 찼다면 1을, 빈 공간이 있다면 0을 리턴한다.
}
//주어진 버킷이 빈 버킷인지 확인하는 함수
int isEmpty(int target){
int i, count=0;
for(i=0;i<3;i++)//버킷을 조사하여 비어있는 곳이 있다면
if(bucket[target].stg[i]==-1)//count변수값을 1 증가시킨다.
count++;
if(count==3)return 1;//count값이 3이라면 모두 비어있다는 의미이므로 1을 리턴
elsereturn 0;//count값이 3이 아니라면 가득찼거나 하나이상 차있다는 뜻이므로 0을 리턴
}
//주어진 확장성 해싱의 내용을 출력하는 함수
void show_hash(struct st_drt* exHashing){
int i,j,k,m=1;
for(i=0;id;i++)m=m*2;
fprintf(ofp,"d = %d\n",exHashing->d);
for(i=0;i for(j=0;jd;j++)//전역깊이에 맞는 비트수를 보여준다.
fprintf(ofp,"%d",exHashing->key[i][j]);
if(i!=0&&exHashing->ptr[i]->th==exHashing->ptr[i-1]->th)
fprintf(ofp," ───┘\n");
else{
fprintf(ofp," ────> ");
fprintf(ofp,"%d |",exHashing->ptr[i]->p);
for(k=0;k<3;k++)
if(exHashing->ptr[i]->stg[k]!=-1)
fprintf(ofp," %4d",exHashing->ptr[i]->stg[k]);
fprintf(ofp,"\n");
}}
}
//확장성 해시를 만들고 디렉터리의 주소를 리턴해주는 함수
struct st_drt* make_exHashing(void){
int i;
directory.d=1;//디렉터리의 전역 깊이를 1로 한다.
directory.key=(int(*)[12])malloc(sizeof(int)*12*2);
directory.ptr=(struct st_bkt**)malloc(sizeof(struct st_bkt*)*2);
directory.key[0][0]=0;//디렉터리의 전역깊이에 해당하는 모조키를 key변수에 저장.
directory.key[1][0]=1;
directory.ptr[0]=&bucket[0];//디렉터리의 모조키에 해당하는 버킷을 포인터에 연결
directory.ptr[1]=&bucket[1];
bucket_count=2;//생성된 버킷은 2개가 된다.
for(i=0;i<3;i++){
bucket[0].stg[i]=-1;//버킷의 내용은 -1로 초기화 해준다.
bucket[1].stg[i]=-1;
}
bucket[0].p=1;//각 버킷의 지역 깊이도 1로 초기화 해준다.
bucket[1].p=1;
bucket[0].th=0;
bucket[1].th=1;
bucket[0].bit[0]=0;
bucket[1].bit[0]=1;
return &directory;//디렉터리의 주소를 리턴한다.
}

키워드

확장성,   해싱,   화일,   구현,   설계,   extendible,   hashing