实现网页爬虫中的URL去重功能==》
散列表、红黑树、跳表，都支持快速地插入、查找数据，内存消耗呢？
位图==》比较特殊的散列表
我们有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢？==》申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组。我们将这 1 千万个整数作为数组下标，将对应的数组值设置成 true
package day0815; /** * 位图通过数组下标来定位数据，访问效率非常高 * 每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省*/ public class BitMap {//Java中char类型占16bit，也即是2个字节 private char[] bytes; private int nbits; //char==>2字节 public BitMap(int nbits) { this.nbits = nbits; this.bytes = new char[nbits/16 + 1]; } public void set(int k) { if (k > nbits) return; int byteIndex = k / 16; int bitIndex = k % 16; bytes[byteIndex] |= (1 << bitIndex); //为什么左移一位？ } public boolean get(int k) { if (k > nbits) return false; int byteIndex = k / 16; int bitIndex = k % 16; return (bytes[byteIndex] & (1 << bitIndex)) != 0; } }
数字范围不是很大时，使用位图；数字范围很大时，使用布隆过滤器
使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 X1，X2，X3，…，XK。我们把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK]都设置成 true，也就是说，我们用 K 个二进制位，来表示一个数字的存在。
当我们要查询某个数字是否存在的时候，我们用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK。我们看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。
它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。
布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。
布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。当我们往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高了。所以，对于无法事先知道要判重的数据个数的情况，我们需要支持自动扩容的功能。当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中。但是，如果要判断某个数据是否在布隆过滤器中已经存在，我们就需要查看多个位图，相应的执行效率就降低了一些。
假设我们有 1 亿个整数，数据范围是从 1 到 10 亿，如何快速并且省内存地给这 1 亿个数据从小到大排序？
1、1亿个整数，存储需要400M空间，排序时间复杂度最优 N×log(N)
2、数字范围是1到10亿，用位图存储125M就够了，然后将1亿个数字依次添加到位图中，然后再将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 N