일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 파이썬 강좌
- Play2 로 웹 개발
- 하이퍼레저 패브릭
- 파이썬 머신러닝
- 파이썬 데이터분석
- 엔터프라이즈 블록체인
- 파이썬
- 스칼라 강좌
- hyperledger fabric
- Akka
- 스칼라 동시성
- 그라파나
- Adapter 패턴
- 스위프트
- Hyperledger fabric gossip protocol
- 파이썬 동시성
- play 강좌
- 블록체인
- CORDA
- Golang
- Actor
- 주키퍼
- play2 강좌
- 하이브리드앱
- akka 강좌
- 이더리움
- 스칼라
- 안드로이드 웹뷰
- 플레이프레임워크
- Play2
- Today
- Total
HAMA 블로그
디스크 상에서의 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;
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;
}
'알고리즘,자료구조' 카테고리의 다른 글
레드블랙트리 vs 해쉬테이블 (TreeMap vs HashMap) (0) | 2015.09.14 |
---|---|
레드블랙트리 (red-black tree) 삽입 (0) | 2015.09.10 |
Finding Kth largest element in Array (0) | 2015.05.12 |