• 基本原理：使用位数组来判断， 某些元素是否存在。比如在电话号码集合中进行去重，或者查找重复号码
• 典型场景：海量数据的排序、判重等
• 以空间换时间，需要知道集合的max值
• 应用
  • 判断集合中是否存在重复(发现某一个bit已经是1了)
  • 集合去重后的个数(统计bit数组中为1的个数)
  • 集合中，出现次数只有一次的数的个数
    • 将bit-map扩展一下，使用2bit表示一个数，00是未出现，01是出现一次，10是出现1次以上
    • 或者用两个bit-map实现
  • 给你一个文件，里面包含40亿个非负整数，写一个算法找出该文件中不包含的一个Integer整数
    • 构建一个integer.MAX_VALUE大小size的bit-map，遍历这个文件中的所有整数，最后bit为0的index，就是未出现的非负整数。这个数组占用内存 4294967295 bit = 4294967295/8 Byte = 500M
    • 如果系统提供的内存只有10M怎么办呢？
      • 我们可以将所有0-4294967295的数据平均分成64个区间，每个区间保存67108864个数，比如：第0区间[0-67108863]，第1区间[67108864-134217727]，第i区间为[67108864*i - 67108864(i+1)-1]…,
      • 实际上我们并不保存这些数，而是给每一个区间设置一个计数器(比如做个size=64的数组)。这样每读入一个数，我们就在它所在的区间对应的计数器加1。
      • 处理结束之后， 我们找到一个区间，它的计数器值小于区间大小(67108864)， 说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个区间即可。接下来我们就可以用Bit Map算法了。
      • 申请长度为67108864的bitArr，记为bitArr[0..67108863]，我们再遍历一遍数据， 把落在这个区间的数对应的位置1(当然数据要经过处理，即落在区间i的数num，则bitArr[num-67108864i]=1)。
      • 最后我们找到这个区间中第一个为0的位，其对应的数就是一个没有出现在该文件中的数。