本文主要是介绍哈希变形之位图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 引入：为什么会有位图
当给40亿个不重复的无序的无符号整数，再给定一个无符号整数，如何快速判断出这个数是否存在在这40亿个数之中？
假如我们使用的是哈希表，将这40亿的数据按照闭散列的形式存放在哈希表中，那么每个无符号的整数如果占4个字节的话，40亿数据就需要占16G的内存，这样的操作明显是不合适的。于是就有了位图的出现，通过位图可以将40亿中的每个数据存放在哈希表转换为将这40亿数据的值所对应的bit位设置为1或0（1表示存在，0表示不存在），此时就大大节省了空间，将原本需要16G的内存空间转变为0.5G的内存空间。
2. 位图的结构体定义
用一个bit位描述某个数据的状态的结构我们称之为位图，那么对于位图结构体我们应该怎么定义呢？
既然位图是需要操作bit位的结构，那么就需要我们设置位图能表示的最大bit位，即位图需要的bit位的个数。而由于内存的申请不是通过bit位来完成而是通过字节来动态申请的，故在知道位图的bit位个数之后需要计算出该位图所占的字节数来申请位图需要的内存空间。
位图的结构体定义如下：
#include<stdint.h>
#pragma once
#define HEADER printf("=========%s=========\n",__FUNCTION__);
//定义位图的结构体类型
typedef uint64_t BitMapType;
typedef struct BitMap{BitMapType* data;//位图最大能容纳的大小BitMapType capacity;
}BitMap;3. 位图的初始化与销毁
3.1 位图的初始化
首先，根据位图的结构体我们在初始化位图时需要先动态申请内存空间，而申请内存空间的单位是字节数，那如何通过位图的结构体的最大bit位个数计算字节数从而申请内存空间呢？假如需要100个bit位，那么如果我们以每个int整型占4个字节来动态申请空间的话，就需要（100/8*4+1）个int整型的内存空间，即（100/8*4+1）*4个字节数的内存空间。我们也可以以其他数据类型来动态申请内存，如下面我将以uint64_t的数据类型来动态申请内存，此时若也需要100个bit位的话，需要（100/8*8+1）个数据类型为uint64_t（占8个字节）的内存空间，即（100/8*8+1）*8个字节数的内存空间。
其次，既然位图是通过操作bit位的0、1序列进行数据存储的，那么就需要我们在动态申请内存后将其所有的bit为初始化为0，故可以使用calloc()函数在申请空间的同时将其bit位均置为0。
下面是对位图的初始化操作：
//0.计算应该动态分配多大的空间
//思路：根据capacity(表示bit位有多少个)计算应该动态分配多大的空间
BitMapType GetSize(BitMap* bm,BitMapType capacity)
{BitMapType size=capacity/(sizeof(bm->data[0])*8)+1;return size;
}
//1.初始化
//思路：根据GetSize计算出分配的空间大小并开辟对应大小的空间以及将capacity初始化
void BitmapInit(BitMap* bm,BitMapType capacity)
{//非法输入if(bm==NULL)return; bm->capacity=capacity;BitMapType size=GetSize(bm,capacity);bm->data=(BitMapType*)calloc(sizeof(BitMapType),size);
}3.2 位图的销毁
位图的销毁：将对位图做的相关操作均恢复至初始状态，故将动态申请的内存进行释放并将所设置的位图的最大容纳bit位置为0即可。代码如下：
//2.销毁
//思路：将capacity置为0并将动态申请的内存释放
void BitmapDestroy(BitMap* bm)
{//非法判断if(bm==NULL)return;bm->capacity=0;free(bm->data);
}4. 判定bit位的某一位index是否为1
首先，通过bit位的位置index确定该bit位所在的数组元素以及该元素所在的bit位，举例说明：假如传入的index=80时，首先，通过80/8*8+1=2计算出该bit位在动态申请内存数组的第二个元素处；其次，通过80%8*8=16计算出对应的元素的第16个bit位处。故bit位为80时，表示该bit位在数组下标为1的元素的第16个bit位处，为了方便之后的表述，我们将通过bit位计算出来的该bit位所在数组的下标记为N，该bit位所在元素的bit位记为Offset。
其次，知道了bit位所在的具体元素的第多少个bit位后，如何判断对应bit位是否为1呢？我们可以将该bit位所在的元素进行按位与操作，即将1左移Offset位后与该bit位所在下标为N的元素进行&操作即可。如返回0表示该bit位所对应的二进制为0，否则表示该bit位所对应的二进制为1。
代码如下：
//3.判定某一位是否为1
//计算出这一位所在的数组位置以及在当前数组位置的第几个bit位
void GetNOffset(BitMapType index,size_t* n,size_t* offset)
{//非法输入if(n==NULL||offset==NULL)return;*n=index/(sizeof(BitMapType)*8);*offset=index%(sizeof(BitMapType)*8);
}
int BitmapTest(BitMap* bm,BitMapType index)
{//非法输入if(bm==NULL||index>=bm->capacity) return 0;//计算出这一位所在的数组位置以及在当前数组位置的第几个size_t n; //表示数组位置size_t offset; //表示第几个bit位GetNOffset(index,&n,&offset);BitMapType ret=bm->data[n]&(0x1u<<offset);return ret>0?1:0;
}5. 给某一位index设置为1
与之前判定某一位是否为1的操作类似，先计算出对应数组的下标N以及对应该元素的bit位Offset，再将1左移Offset后与数组下标为N的元素进行按位或（|）操作即可。代码如下：
//4.给某位设置为1
void BitmapSet(BitMap* bm,BitMapType index)
{//非法输入if(bm==NULL||index>=bm->capacity)return;//计算出这一位所在的数组位置以及在当前数组位置的第几个size_t n; //表示数组位置size_t offset; //表示第几个bit位GetNOffset(index,&n,&offset);bm->data[n]|=(0x1u<<offset);
}6. 给某一位index设置为0
与之前判定某一位是否为1的操作类似，首先计算出对应数组的下标N以及对应该元素的bit位Offset，其次将1左移Offset后进行取反操作，再与数组下标为N的元素进行按位与（&）操作即可。代码如下：
//5.给某一位设置为0
void BitmapUnset(BitMap* bm,BitMapType index)
{//非法输入if(bm==NULL||index>=bm->capacity)return;//计算出这一位所在的数组位置以及在当前数组位置的第几个size_t n; //表示数组位置size_t offset; //表示第几个bit位GetNOffset(index,&n,&offset);bm->data[n]&=(~(0x1u<<offset));
} 7. 将所有bit位均设置为1
将所有bit位设置为1可以通过调用memset()函数设置，但由于memset()函数是通过设置每个字节的数据内容，故要想将每个字节中的bit位均设置为1即将该字节对应的数据内容设置为0xff即可。代码如下：
//6.给所有位设置为1
void BitmapFill(BitMap* bm)
{//非法输入if(bm==NULL)return;//计算出分配空间的大小size_t size=GetSize(bm,bm->capacity);//将所有bit位设置为1memset(bm->data,0xff,sizeof(BitMapType)*8); //0xff表示一个字节
}
8. 将所有bit位均设置为0
该操作与将所有bit位均设置为1操作类似，通过调用memset()函数将每个字节中的的bit位均设置为0，而要想将每个字节的bit位均设置为0即将该字节的数据内容设置为0即可。代码如下：
//7.给所有位设置为0
void BitmapClear(BitMap* bm)
{//非法输入if(bm==NULL)return;//计算出分配空间的大小size_t size=GetSize(bm,bm->capacity);//将所有bit位设置为0memset(bm->data,0x00,sizeof(BitMapType)*8); //0x00表示一个字节
}以上就是关于位图的相关操作！
这篇关于哈希变形之位图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
