10亿条数据如何快速找到某个数-BitMap经典算法详解

前言BitMap字面意思，很多人认为是位图，其实翻译成基于位的映射，怎么理解呢？问题介绍有一个无序有界的int数组{1,2,5,7}，初步估计占用内存44=16字节，因为只有4个数，很容易，需要的数可以很快就找到了。但是如果有10亿个这样的数，10亿个不重复也没有排序的unsignedint整数，给定一个整数，给定的数怎么求，怎么操作呢？需求分析：Java中Int类型的存储占用4Byte，32Bit。10亿4/(102410241024)=约3.72G。这么大的数据要是要查找和排序，那么内存也可能崩溃。有人说数据不需要一次性全部加载，就是需要保存，保存必然会消耗IO。我们提倡高性能，这个方案没有考虑。问题分析如果用BitMap思维来解决，会好很多，那么BitMap是怎么解决的，如下：一个字节占8位，如果每个位的值是yes或no，即二进制0或1，如果用位的位置来表示数组值是否存在，那么0表示该值没有出现过，1表示数组值出现过。你不能也描述数据吗？具体如下：是不是很神奇，那么现在如果10亿条数据需要的空间是3.72G/32，一个占32bits的数据现在只占1bit，节省了很多空间，更不用说排序了，一切都显得那么顺利。这些数据之间没有相关性。如果是读的话，可以用多线程的方式读。时间复杂度也是O(Max/n)，其中Max是byte[]数组的大小，n是线程大小。3.应用与代码如果BitMap只是为了这个特性，我觉得还不是它的优雅，接下来继续领略它的魅力。下面的计算思路其实是对位进行逻辑运算得到的，类似这种逻辑运算的应用场景可以用在权限计算中。在再看代码之前，我们先搞清楚一个问题，对于一个数如何快速定位到它的索引号，也就是弄清楚byte[index]的索引是什么，位置在哪一位。例如，假设添加(14)。14超出了byte[0]的映射范围，在byte[1]的范围内。那么如何快速定位到它的索引。如果找到它的索引号，如何定位它的位置。Index(N)表示N的索引号，Position(N)表示N的位置号。Index(N)=N/8=N>>3；Position(N)=N%8=N&0x07;(1)add(intnum)想给位图添加数据怎么办，别着急，很简单，也很神奇。上面已经分析过，add的目的是将位置从0变为1，其他位置不变。示例代码：publicvoidadd(intnum){//num/8获取byte[]的索引intarrayIndex=num>>3；//num%8得到byte[index]中的位置intposition=num&0x07;//左移1后那个位置自然是1，然后做|bits[arrayIndex]|=1<>3;//num%8获取byte[index]的位置intposition=num&0x07;//将1移到position之后的left，那个位置自然是1，然后取反，然后用当前值做&，清空当前位置。bits[arrayIndex]&=~(1<>3;//num%8得到byte[index]的位置intposition=num&0x07;//position后左移1，那个位置自然是1，然后和前面的数据做&判断是否为0return(bits[arrayIndex]&(1<>3)+1];}publicvoidadd(intnum){//num/8得到byte[]的indexintarrayIndex=num>>3;//num%8得到byte[index]所在位置intposition=num&0x07;//左移1后，那个位置自然是1，然后做|与之前的数据，使该位置被替换为1。bits[arrayIndex]|=1<>3;//num%8得到byte[index]中的位置intposition=num&0x07;//左移1后，那个位置自然是1，然后和前面的数据做&判断是否为0return(bits[arrayIndex]&(1<>3;//num%8获取byte[index]中的位置intposition=num&0x07;//左移1后，位置自然为1，然后取反，然后用当前值做&，清空当前位置。bits[arrayIndex]&=~(1<