哈希变形---位图

哈希变形---位图(bitmap)

位图是哈希的一种扩展，本质上是一种数组，即每个二进制位表示一种状态，0表示不存在，1表示存在

1>所谓的位图就是用bit位来存放数据的某种状态,适用于大规模的数据.

2>位图结构

我们先来用腾讯的一道大数据题引出位图结构吧。比如说：给40亿个不重复且无序的无符号整数，现在给你一个整数让你快速判断出它是否存在？（假设我们只有4G内存）

40亿个数需要160亿字节，等同于16GB，一次性是无法将40亿个数据加载到内存中的，因此引入了位图。

40亿个数我们只需要知道它存在与不存在,所以我们用40亿个bit位来标识它的存在状态就好.

那么40亿/8=5亿个字节也就是500 000 000 = 0.5G,这样一来就可以解决加载内存的问题了.

那么我们的问题是:一个数据该在哪个字节,以及该字节的哪一位呢.

一个数据arr[i]------我们假如以一个整形空间为一个单元,我们把arr[i]的值记为pos,那么该数据在该整形单元的pos>>5(pos/32)的这个字节中,在该字节的pos%32的bit位上.

3>位图实现

BitMap.h

typedef struct BitMap
{
	int * Bit_bset;//位的集合
	int _capacity;
	int _size;//有效bit位的个数
}BitMap;
void BitMapInit(BitMap * bmp,int capacity);
void BitMapSet_zero(BitMap * bmp,int pos);
void BitMapSet_one(BitMap *bmp,int pos);
int  BitMapTest(BitMap *bmp, int pos);//测试bit位为1还是为0;
int BitMapSize(BitMap *bmp);
int BitMapCount(BitMap *bmp);
void BitMapDestroy(BitMap *bmp);

BitMap.c

#include "BitMap.h"
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
void BitMapInit(BitMap * bmp, int total_Bit){
	assert(bmp); //total_Bit代表总共的bit位数
	bmp->_capacity = (total_Bit >> 5 )+ 1;//代表需要的整形空间的个数
	bmp->Bit_bset = calloc(bmp->_capacity, sizeof(int));//void *calloc(空间的个数,每个空间的字节数);
	bmp->_size = total_Bit;//有效比特位的个数
}
//将pos的位置0;
void BitMapSet_zero(BitMap * bmp, int pos){
	assert(bmp);
	int pos_Byte = pos >> 5;
	int pos_Bit = pos % 32;
	if (pos > bmp->_size)
		return;
	bmp->Bit_bset[pos_Byte] = bmp->Bit_bset[pos_Byte] &( ~(1 << pos));
	
}
//将pos的位置1;
void BitMapSet_one(BitMap *bmp, int pos){
	assert(bmp);
	int pos_Byte = pos >> 5;
	int pos_Bit = pos % 32;
	if (pos > bmp->_size)
		return;
	bmp->Bit_bset[pos_Byte] = bmp->Bit_bset[pos_Byte] |(1 << pos);
	
}
int  BitMapTest(BitMap *bmp, int pos)//测试bit位为1还是为0;
{
	assert(bmp);
	int pos_Byte = pos >> 5;
	int pos_Bit = pos % 32;
	if (pos > bmp->_size)
		return;
	return bmp->Bit_bset[pos_Byte] & (1 << pos);
}
int BitMapSize(BitMap *bmp)
{
	assert(bmp);
	return bmp->_size;
}
//统计bit位上1的个数
int BitMapCount(BitMap *bmp){
	int i = 0;
	int count = 0;
	assert(bmp);
	const char * bit1Count = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
	for ( i = 0; i <bmp->_capacity; i++)
	{
		int value = bmp->Bit_bset[i];
		int j = 0;
		//一个整数占4个字节,我们按一个字节为单元查看bit位上1的个数
		while (j<sizeof(bmp->Bit_bset[0])){
			char c = value;
			//统计一个字节的底4位
      		        count+=bit1Count[c&0x0f];
			c >>= 4;
			//统计一个字节的高4位
			count+=bit1Count[c&0x0f];
			value >>= 8;
			j++;
		}
	}
	return count;
}
void BitMapDestroy(BitMap *bmp){
	assert(bmp);
	if (bmp->Bit_bset)
		free(bmp->Bit_bset);
	bmp->_size = 0;
	bmp->_capacity = 0;
}

test.c

#include "BitMap.h"
#include<stdio.h>
#include<stdlib.h>
int main(){
	BitMap bmp;
	int i = 0;
	int len = 0;
	int array[] = {1,3,7,4,12,16,19,13,22,18};
	BitMapInit(&bmp, 24);
	len = sizeof(array) / sizeof(array[0]);
	for ( i = 0; i < len; i++)
	{
		BitMapSet_one(&bmp, array[i]);
	}
	if (BitMapTest(&bmp, 22)){
		printf("存在\n");
	}
	if (BitMapTest(&bmp, 20)){
		printf("不存在\n");
	}
	printf("%d\n", BitMapSize(&bmp));
	printf("%d\n", BitMapCount(&bmp));
	system("pause");
	return 0;
}