해시 확장 - 비트 맵

앞서 소 개 된 해시 표 에 서 는 표 에 정 수 를 저장 하려 면 전체 메모 리 를 신청 하여 저장 해 야 합 니 다. 하나의 전체 데 이 터 는 32 비트 나 64 비트 플랫폼 에서 모두 4 개의 바이트 를 차지 합 니 다.만약 에 지금 저장 해 야 할 데이터 가 매우 많다. 예 를 들 어 40 억 개의 중복 되 지 않 는 데 이 터 를 저장 하려 면 160 억 개의 바이트 가 필요 하 다. 1GB 의 메모 리 는 10 억 개의 바이트 를 나타 낸다. 이때 16GB 의 메모리 가 이 데 이 터 를 저장 해 야 한다. 우리 의 일반적인 컴퓨터 메모 리 는 보통 4G 의 메모리 인 데 이것 은 분명 크 지 않다.우 리 는 메모리 의 가장 작은 단 위 는 비트 비트 비트 라 는 것 을 안다.하나의 비트 비트 비트 로 정형 을 저장 할 수 있다 면 0.5GB 의 메모리 만 필요 하 다.
        비트 비트 비트 는 0 또는 1 로 설정 할 수 있 으 며, 40 억 개의 데 이 터 를 표시 하려 면 0.5GB 의 메모 리 를 신청 할 수 있다.저장 할 데이터 가 10 이면 10 번 째 비트 비트 를 1 로 설정 합 니 다.찾 으 려 는 데이터 가 100 이면 100 번 째 비트 위치의 상 태 를 보고 1 로 설명 하면 100 이 이 데이터 더미 에 존재 하 며 0 으로 설명 하면 존재 하지 않 습 니 다.이렇게 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트
        비트 맵 의 가장 큰 장점 은 공간 을 절약 하 는 것 이다.그러나 데이터 가 존재 하 는 지 여 부 를 표시 할 뿐 데 이 터 를 저장 할 수 없다 는 것 이 가장 큰 단점 이다.
        다음은 비트 맵 의 기본 동작 을 실현 하 겠 습 니 다.
1. 구조 정의
        그 중에서 capacity 는 수용 할 수 있 는 요소 가 얼마나 되 는 지 를 나타 낸다. 이것 은 초기 화 할 때 길 이 를 정 한 다음 에 공간 을 신청 해 야 한다.그 후에 공간 이 너무 작다 고 생각하면 다시 확장 할 수 있다.

#pragma once

#include 
#include //uint64_t
#include 
#include                                                                                                                                                      

#define SHOW_NAME printf("
========================%s=======================
", __FUNCTION__);

typedef uint64_t BitmapType;//uint64_t        ， 8  

typedef struct Bitmap
{
    BitmapType* data;
    uint64_t capacity;
}Bitmap;

2. 초기 화

//1.   
void BitmapInit(Bitmap* bm, uint64_t capacity)//   
{
    if(bm == NULL)//    
        return;
    bm->capacity = capacity;//           (bit )
    uint64_t size = bm->capacity/(sizeof(bm->data[0])*8) + 1;//        
    bm->data = (BitmapType*)malloc(sizeof(BitmapType)*size);
    memset(bm->data, 0, sizeof(BitmapType)*size);//     
    return;
}

3. 소각

//2.  
void BitmapDestroy(Bitmap* bm)
{
    if(bm == NULL)
        return;
    bm->capacity = 0;
    free(bm->data);
    return;
}

4. 테스트 함수 - 어떤 비트 가 0 인지 1 인지 테스트 합 니 다.

//3.    —      0   
void GetOffset(uint64_t index, uint64_t* n, uint64_t* offset)//                    
{//n      ，offset      
    *n = index / (sizeof(BitmapType)*8);
    *offset = index % (sizeof(BitmapType)*8);
    return;
}

int BitmapTest(Bitmap* bm, uint64_t index)// bit   1  1， 0  0
{//index           bit
    if(bm == NULL || index >= bm->capacity)//    
        return 0;
    uint64_t n,offset;
    GetOffset(index, &n, &offset);
    
    uint64_t ret = bm->data[n] & (0x1ul << offset);//    0x1ul                      
    return ret > 0 ? 1 : 0;
}

5. 비트 비트 비트 를 1 로 설정

//4.        1
void BitmapSet(Bitmap* bm, uint64_t index)
{
    if(bm == NULL || index >= bm->capacity)//    
        return;
    uint64_t n,offset;
    GetOffset(index, &n, &offset);
    bm->data[n] |= (0x1ul << offset);// 1    1
    return;
}

6. 비트 비트 비트 를 0 으로 설정

//5.        0
void BitmapUnSet(Bitmap* bm, uint64_t index)
{
    if(bm == NULL || index >= bm->capacity)//    
        return;
    uint64_t n,offset;
    GetOffset(index, &n, &offset);
    bm->data[n] &= ~(0x1ul << offset);// 0    0
    return;
}

7. 모든 비트 비트 비트 를 1 로 설정

//6.        1
void BitmapFill(Bitmap* bm)
{
    if(bm == NULL)//    
        return;
    uint64_t size = bm->capacity/(sizeof(bm->data[0])*8) + 1;
    memset(bm->data, 0xff, sizeof(BitmapType)*size);
    return;
}

8. 모든 비트 비트 비트 를 0 으로 설정

//7.        0
void BitmapEmpty(Bitmap* bm)
{
    if(bm == NULL)//    
        return;
    uint64_t size = bm->capacity/(sizeof(bm->data[0])*8) + 1;
    memset(bm->data, 0x0, sizeof(BitmapType)*size);
    return;
}

다음은 테스트 함수:

void Test()
{
    SHOW_NAME;
    Bitmap bm;
    BitmapInit(&bm, 100);
    printf("capacity: expected is 100, actual is %d
", bm.capacity);
    printf("expected is 0, actual is %lu
", bm.data[0]);//uint64_t   %lu  
    BitmapSet(&bm, 4);
    printf("expected is 1, actual is %d
", BitmapTest(&bm, 4));
    BitmapUnSet(&bm, 7);
    printf("expected is 0, actual is %d
", BitmapTest(&bm, 7));
    BitmapFill(&bm);
    printf("expected is 1, actual is %d
", BitmapTest(&bm, 31));
    BitmapEmpty(&bm);
    printf("expected is 0, actual is %d
", BitmapTest(&bm, 27));
    BitmapDestroy(&bm);
    printf("expected is 0, actual is %d
", bm.capacity);
}