欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

哈希变形---位图

程序员文章站 2024-03-15 21:56:12
...

哈希变形---位图(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;
}


相关标签: 位图 海量数据