一、网页爬虫：
1、工作原理：
通过解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页。
2、去重原因：
由于同一个网页链接有可能被包含在多个页面中，这就会导致爬虫在爬取的过程中，重复爬取相同的网页。因此需要去重。
二、位图（BitMap）：
1、概念：
用一个位（bit）来标记某个数据的存放状态，由于采用了位为单位来存放数据，所以节省了大量的空间。举个具体的例子，在Java中一般一个int数字要占用32位，如果能用一位就表示这个数，就可以缩减大量的存储空间。一般把这种方法称为位图法，即Bitmap。
2、实现代码：
//char类型存储数字的时候，只占2个字节，也就是16位
public class BitMap {
private char[] bytes;
private int nbits;
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;
}
}
3、布隆过滤器：
<1>、基本思想：
当一个元素被加入集合时，通过个散列函数将这个元素映射成一个位数组中的
个点，把它们置为
。检索时，我们只要看看这些点是不是都是
就（大约）知道集合中有没有它了：如果这些点有任何一个
，则被检元素一定不在；如果都是
，则被检元素很可能在。这就是布隆过滤器的基本思想。
使用个哈希函数，对同一个数字进行求哈希值，那会得到
个不同的哈希值，分别记作
，
，
， …，
。把这
个数字作为位图中的下标，将对应的BitMap[
]， BitMap[
]， BitMap[
]， …， BitMap[
]都设置成true，也就是说，用
个二进制位，来表示一个数字的存在。当要查询某个数字是否存在的时候，用同样的
个哈希函数，对这个数字求哈希值，分别得到
，
，
， …，
。看这
个哈希值，对应位图中的数值是否都为true，如果都是true，则说明，这个数字存在，如果有其中任意一个不为true，那就说明这个数字不存在。
<2>、存在问题：
容易误判：
误判特点：
只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。
