哈希表—位图-创新互联
原文链接：http://blog.csdn.net/qq_38646470/article/details/79427038[1.什么是位图？
2.位图的用处？
3.位图的结构
4.位图题目操练
5.总结（优缺点分析）]
1.什么是位图？
位图就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器，其实就是位图。
所以我们可以了解到，位图就是一个只用每一位来保存数的状态的结构。
2.位图的用处？
位图主要用于海量数据处理，索引，数据压缩等方面有广泛应用
3.位图的结构
关于位图的结构，类似于哈希，位图就是一个用每一位的0，1来表示一个数的状态。
比如，我们现在有一个文件，这个文件中有数 1，5，4294967295。我们就把第1位，第5位，第4294967295位改为状态1。
4.位图题目操练
给4 0 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这4 0 亿个数中。
题目分析：这是一道关于海量数据查找的题，其实这道题，我们就可以和哈希表联系在一起，为何说是海量数据呢，对于一个40亿整数，我们如果要存的话，按照无符号整数来存储，那么下来，大概就需要40亿*4这么些字节，下来大概就是16G的 内存。
对于现在的64位机，普遍标配内存也就是4-8G的内存，显而易见，16G是没有办法一次性处理的。那么我们如何是好？进行拆分？这样显然也是不好的，怎么拆，还有效率问题。
所以在这里我们采取一种新的思路，这种思路就是位图。
位图结构定义
typedef struct BitMap
{
size_t* _bits;
size_t _range;
}BitMap;
位图相关接口
void BitMapInit(BitMap *bm,size_t range) //初始化
{
assert(bm);
bm->_bits = NULL;
bm->_range = range;
bm->_bits = (size_t *)malloc(sizeof(char)*bm->_range/8);
assert(bm->_bits);
memset(bm->_bits,0,sizeof(char)*bm->_range/8);
}
void BitMapSet(BitMap *bm,size_t x)//标记相应位
{
size_t num = x>>5;
size_t bit = x%32;
bm->_bits[num] |=(1<>5;
size_t bit = x%32;
bm->_bits[num] &= (~(1<>5;
size_t bit = x%32;
if ((1<_bits[num])
return 0;
return -1;
} 测试案例及结果截图：
void TestBitMap()
{
BitMap bm;
BitMapInit(&bm,-1);
BitMapSet(&bm,5);
BitMapSet(&bm,6);
BitMapSet(&bm,7);
BitMapSet(&bm,8);
BitMapSet(&bm,-1);
printf("%d\n",BitMapTest(&bm,4));
printf("%d\n",BitMapTest(&bm,5));
printf("%d\n",BitMapTest(&bm,6));
printf("%d\n",BitMapTest(&bm,7));
printf("%d\n",BitMapTest(&bm,8));
printf("%d\n",BitMapTest(&bm,-1));
}
这道题中位图结构代码不难，注意理解思路，必须熟练掌握位运算。
5.总结
优缺点：
(1)可读性差
(2)位图存储的元素个数虽然比一般做法多，但是存储的元素大小受限于存储空间的大小。位图存储性质：存储的元素个数等于元素的大值。比如， 1K 字节内存，能存储 8K 个值大小上限为 8K 的元素。（元素值上限为 8K ，这个局限性很大！）比如，要存储值为 65535 的数，就必须要 65535/8=8K 字节的内存。要就导致了位图法根本不适合存 unsigned int 类型的数（大约需要 2^32/8=5 亿字节的内存）。
(3)位图对有符号类型数据的存储，需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数，元素值大小上限减半。 比如 8K 字节内存空间存储 short 类型数据只能存 8K*4=32K 个，元素值大小范围为 -32K~32K 。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网页标题：哈希表—位图-创新互联
文章路径：http://6mz.cn/article/deidpi.html