哈希表—位图

原文链接：http://blog.csdn.net/qq_38646470/article/details/79427038
[1.什么是位图？
2.位图的用处？
3.位图的结构
4.位图题目操练
5.总结（优缺点分析）]
1.什么是位图？
位图就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器，其实就是位图。

创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于网站设计制作、网站设计、平川网络推广、小程序开发、平川网络营销、平川企业策划、平川品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联公司为所有大学生创业者提供平川建站搭建服务，24小时服务热线：18980820575，官方网址：www.cdcxhl.com

所以我们可以了解到，位图就是一个只用每一位来保存数的状态的结构。

2.位图的用处？
位图主要用于海量数据处理，索引，数据压缩等方面有广泛应用
3.位图的结构
关于位图的结构，类似于哈希，位图就是一个用每一位的0，1来表示一个数的状态。

比如，我们现在有一个文件，这个文件中有数 1，5，4294967295。我们就把第1位，第5位，第4294967295位改为状态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 。