梦幻西游结拜，北京汽车4s店招聘，凯美瑞2010
假设有一个需求是这样的：在200亿个随机整数中找出某个数是否存在其中？要求效率高，而且要节省内存。
我们知道，在Java中，int占4字节，1字节=8 byte，1 byte = 8 bit（位）
如果用int存储，那就是200亿个int，因而占用的空间约为
(20000000000*4/1024/1024/1024)≈74.5G。
内存消耗很大，一般的家用电脑是满足不了需求的，所以将数据存储在内存中存储是不合适的。
如果按位存储就不一样了，200亿个数就是200亿位，占用空间约为
(2000000000/8/1024/1024/1024)≈2.33G，节省了30倍的空间。
实际上这就是Bitmap的思想。Bitmap的基本思想是用一个bit位来标记某个元素对应的Value，而Key即是该元素本身。采用bit存储数据，可以大大节省存储空间。
Bitmap是什么？如何在bitmap中表示一个数呢？
我们知道计算机底层存储的都是二进制数据，二进制数只有0和1。bitmap每一位的值也只能是0或1，0表示不存在，1表示存在。
这样我们可以很容易表示{1,2,4,6}这几个数：
计算机内存分配的最小单位是字节，也就是8位，那如果要表示{12,13,15}怎么办呢？
当然是在另一个8位上表示：
这样的话，好像变成一个二维数组了
1个int占32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32] 即可存储，其中N表示要存储的这些数中的最大值，于是：
tmp[0]：可以表示0~31
tmp[1]：可以表示32~63
tmp[2]：可以表示64~95
。。。
于是，对于任意整数M，M/32可以得到下标，M%32就可以得到它在此下标的哪个位置。
那么，怎么把一个数放进Bitmap呢？比如想把5这个数字放进去
插入一个数
首先，5/32=0，5%32=5，也是说它应该在b[0]的第5个位置。我们可以把1向左移动5位，然后和b[0]按位或即可。
二进制就是:
这就相当于 86 | 32 = 118，即 86 | (1<<5) = 118，也就是 b[0] = b
[0] | (1<<5)。也就是说，要想插入一个数，将1左移相https://www.3tt.net/?mod=artinfo&aid=295应的位数，然后与原数进行按位或操作即可。
删除一个数
还是上面的例子，假设删除数字6，该怎么做呢？
只需将该数所在的位置为0即可。即1左移6位，就到达6这个数字所代表的位，然后按位取反，最后与原数按位与，这样就把该位置为0了
本文地址：http://www.reviewcode.cn/youxikaifa/207107.html 转载请注明出处！
