标题用了了海量数据（Massive datasets）而不用大数据（Big data）。感觉大数据还是略微有点 虚，来点实际的。
一、需求
现在我们需要设计一个在线过滤垃圾邮件地址的方案，我们的数据库里面已经有10亿个合法的邮件 地址（称为合法地址集S），当有新的邮件发过来时，要检查这个邮件地址是不是在我们的数据库里面 ，如果在，我们接收邮件，如果不在，我们就把它当做垃圾邮件过滤掉。
二、直觉想到的方法
一拿到这个问题，我就想到了用log(n)的折半查找，先将10亿个邮件地址排序，当收到一个邮件地 址时，我利用折半查找，看邮件地址是否在S中，log(1,000,000,000) = 29.89约等于30，对每一个邮 件地址我最多也只需要查找30次，感觉也挺快的，应该能满足要求。仔细想一下，折半查找必须放入 内存，10个邮件地址还差不多，10亿个邮件地址我们来算一算有多大，邮件地址平均长度按20个字符 计算，一个字符占用1Byte，一个email就占了20B，1,000,000,000X20B = 20GB，内存顶得住么，当然 可以分多段进行折半，当分段需要多次I/O操作，需要的时间已经不是在线过滤所能承受的了。
三、利用hash处理问题
当数据量很大时，我们一些快速的方法已经不是多给点时间就能解决的，是压根解决不了，折半查 找的方法在可接受的范围内是不可行的。我们来介绍一种神奇的方法，利用hash和位图实现常量时间 确定邮件地址是否在S中。
1、过滤器初步设计
我们申请一个1GB的内存（虽然大了点，但现在的PC都顶得住了），1B共8位，1GB共有80亿位（实 际应该为8X2^30=8,589,934,592位，但为了方便叙述，我们这里用80亿位）这个位图用B表示，B[i]表 示位图的第i位；设计一个hash函数，将邮件地址映射到1-80亿的整数空间上。先将80亿位全部置为0 ，然后对S中的每一个邮件地址进行hash，hash得到一个整数k，就将第k位 置为1，即B[k]=1，如果 hash函数设计得好，hash完S后，80亿的位图应该有10亿个(实际值比10亿小，后面会详细分析)位的值 为1，当收到邮件时，对邮件地址进行hash，记hash得到的结果为p，如果B[p]=0，则邮件地址一定不 再S中，即当作垃圾邮件过滤；如果B[p]=1，则邮件通过过滤，接收邮件。可以结合下图理解：
注意当B[p]=1时，我们并不是说新邮件地址一定在S中，而是说很可能在S中。B[p]=1只能说明S中 一定有一个邮件地址URL，使得hash(URL)=p，而这不能保证其他垃圾邮件地址的hash值不等于p。B [p]=0说明S中不存在邮件地址URL，使得hash(URL)=p，从而新邮件地址一定不在S中。因此，被当作垃 圾邮件过滤的邮件一定不包含合法的地址，而通过过滤的地址仍然有可能是垃圾邮件地址，大约有1/8 （1/8=10亿/80亿，不过实际值比1/8小，后面会详细分析）的垃圾邮件通过过滤，1/8也称为伪阳率。
这样的方案直接上线还是有问题的，因为伪阳率比较高，我们来计算一下照这种方案我们接收的邮 件中垃圾邮件的比率是多少。根据新闻报道全球80%的邮件是垃圾邮件，于是P(接收到的垃圾邮件/接 收的邮件)=(1/8*80%)/(20%+1/8*80%)=1/3(33.33%)，也就是说平均收三封邮件就有一封是垃圾邮件， 这对用户来说是不能忍受的，方案必须优化，不过我们应该看到，我们在不漏掉任何一个合法邮件的 前提下过滤了7/8的垃圾邮件，已经初显hash利器之锋芒了。