디스크 상에서의 HashMap 구현

다음 내용은 정익사의 화일구조의 마지막에 나온 소스 (부록3. 디스크 기반 해시) 를 기반으로 설명된다.

                                                             (그림 - 1)

그림에서 주요 포인트는 :  디스크 , HashPage , HashRecord  이다. 

1. 초기화 

    -  디스크에 저장하기위해 파일을 만든다.(creat 함수, fopen 함수이용) 

    -  페이지 자체의 크기를 4096byte 로 설정한다.   (실제 디스크의 블럭크기와 일치시키면 좋을듯) 

    -  페이지의 갯수를 3000개로 설정한다. (자신이 만들 어플리케이션의 용도에 맞추면 좋고~) 

    -  HashPage  객체하나로  1->2999 번  (1개는 헤더용)  값을 바꾸어서 , 그 내용을 디스크상에 그대로 쓴다.

    -  아직 HashPage 안에 recArray 는 아직 아무 값이 없겠지요.

    -  결국 HashPage 는 아래처럼 초기화 된다. (pageNo 만 의미있는 수치를 갖음) 

           HashPage->pageNo = 1~2999

           HashPage->numOfRecords = 0;

     HashPage->prePageNo = -1;

     HashPage->nextPageNo = -1;

           HashPage->recArray = NULL;

                

2. 삽입 

 - 10,  'helloworld'  를 삽입한다고 치자.  (key 가 10 ,  value 가 "helloworld) 

1. 먼저  임의의 HashPage 객체를 만든다.

2. 10을 해쉬함수를 통해서 목표지점을 얻는다. ( key % 3000 => 10 ) 목표지점은 10 페이지. 

3. 디스크상의 10 번째 페이지를 검색해서  (검색방법은 아래 3.검색에서 살펴보자) 

     3-1. 동일한 키가 존재하면 FALSE 혹은 NULL 을 리턴한다.  (동일키 삽입 불가 정책) 

     3-2. 동일한 키가 없으면 4번으로 

4. 10번 페이지를 디스크상에서 읽어서 HashPage 객체에 저장. 

5. 해당 페이지(10번 페이지) 에 여유공간이 있는지 살펴본다.

     5-1. 여유 공간이 있으면 6 번으로 간다.

     5-2. 여유 공간이 없으면 다음 페이지 (11번 페이지) 로 넘어가서 여유공간을 확인한다.

     5-3. 모든 페이지에 여유 공간이 없으면 새로운 페이지를 만든다.  (3000개 -> 3001개의 페이지가 되겠지 )

6. HashPage 객체에 (10, "helloworld") 를 추가해서

7. 위의 객체를  디스크상의 해당 페이지 위치에 쓴다.

3. 검색 

- 위에서 말한  디스크상의 10번째 페이지를 검색해서 key 10 번이 있는지 확인해보자

1.  해당 10번 페이지를 디스크에서 읽어옴 

2.  recArray 에서 key 가 10번이 있는지 확인한다. 

     2-1.  있으면  멈추고  리턴 해줌.  ( 동일 키가 있다고 알려줌)  

3. 해당 페이지 (10 번 페이지) 에 키가 없으면 , 다음 페이지를 검색한다.( 페이지 끝까지 검색한다. 좀 비효율적) 

4. 모든 페이지에서 key 10 번을 못찾으면 FALSE 를 리턴해준다. 

정리를 해보자.

- 디스크상에 파일을 통해서 고정크기를 할당해두고, 고정크기만큼 나누어준다.

- 고정크기를 페이지라고하고 , 해당 페이지에는 같은 값으로 해슁된 키를 우선 넣어둔다.

- 한곳의 페이지에 키들이 몰리면, 나머지 페이지들의 공간에 낭비가 생기기때문에,

  페이지에 공간이 없으면 다음 페이지에 키를 넣어둔다. (다음페이지도 없으면 다다음) 

- 덕분에, 검색할때는 모든 페이지를 검색해야하는 단점이 있다.

코드 몇 조각  (전체소스는 책 참고. 인터넷에 소스는 없는듯)

struct hashRecord{

Key key;

Value value;

} ;

struct hashPage{

int pageNo;

int numOfRecords;

int prevPageNo;

int nextPageNo;

HashRecord * recArray;

};

struct BufferManger{

File * fp;

int pageSize;

int maxPageNo;

int lastFreePageNo;

};

BOOL readPage(int pageNo, BYTE* buffer){

int ret;

fseek(bufferManger->fp, pageNo * bufferManager->pageSize, SEEK_SET);

ret = (int) fread(buffer, sizeof(BYTE), bufferManger->pageSize, bufferManager->fp);

if(ret>0) return TRUE;

else return FALSE;

}