算法是程序员在学习软件编程开发技术的时候需要重点掌握的编程知识之一，而今天我们就通过案例分析来了解一下，大数据常用数据结构和算法类型。

一、基本概念

所谓海量，就是数据量很大，可能是TB级别甚至是PB级别，导致无法一次性载入内存或者无法在较短时间内处理完成。面对海量数据，我们想到的简单方法即是分治法，即分开处理，大而化小，小而治之。我们也可以想到集群分布式处理。

二、常用数据结构和算法

2.1 Bloom Filter

即布隆过滤器，它可以用于检索一个元素是否在一个集合中。在垃圾邮件的黑白名单过滤、爬虫(Crawler)的网址判重等中经常被用到。

Bloom Filter(BF)是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不在集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。即：宁可错杀三千，绝不放过一个。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter相比其他常见的算法(如hash，折半查找)，极大的节省了空间。

它的优点是空间效率和查询时间都优于一般的算法，缺点是有一定的误识别率和删除困难。

add和query的时间复杂度都为O(k)，与集合中元素的多少无关，这是其他数据结构都不能完成的。

Bloom-Filter算法的核心思想就是利用多个独立的Hash函数来解决“冲突”。Hash函数将一个元素(比如URL)映射到二进制位数组(位图数组)中的某一位，如果该位已经被置为1，只能说明该元素可能已经存在。因为Hash存在一个冲突(碰撞)的问题，即不同URL的Hash值有可能相同。为了减少冲突，我们可以多引入几个独立的hash函数，如果通过其中的一个Hash值我们得出某元素不在集合中，那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能在很大概率上认为该元素存在于集合中。

原理要点：一是m位的bit数组， 二是k个独立均匀分布的hash函数，三是误判概率p。

m bits的bit数组：使用一个m比特的数组来保存信息，每一个bit位都初始化为0

k个独立均匀分布的hash函数：为了添加一个元素，用k个hash函数将它hash得到bloom filter中k个bit位，将这k个bit位置1(超过m的取余%m)。

误判概率p：为了查询一个元素，即判断它是否在集合中，用k个hash函数将它hash得到k个bit位。若这k bits全为1，则此元素以概率(1-p)在集合中;若其中任一位不为1，则此元素必不在集合中(因为如果在，则在添加时已经把对应的k个bits位置为1)。

不允许移除元素，因为那样的话会把相应的k个bits位全置为0，而其中很有可能有其他元素对应的位。因此remove会引起误报，这是绝对不被允许的。而删除元素其实可以通过引入白名单解决。

当k很大时，设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function(例如MD5产生的128 bits数)，如果不同bit位的相关性很小，则可把此输出分割为k份。或者可将k个不同的初始值(例如0,1,2, … ,k-1)结合元素，赋值给一个hash 函数从而产生k个不同的数。