技巧一：对无重复的数据集排序

对于给定的数据集，（2，4，1，12，9，7，6）如何对它排序？

        第一种方式、使用最基本的冒泡，快排、基数排序等，最小时间复杂度 0(nlogn)。

        第二种方式、使用位数组排序算法。

对于数据集排序，相信大多数都会在第一时间便能想起来，而对于方法二，就需要一定的思考了。

对于我们给定的数据集，最大数值为 12，那么我们可以开辟一个长度为 12 的字节数组，如下图，都初始化为0，

然后读取数据，例如，读取到 2 的时候，就将下标为 1 的位置为 1，即 a[2-1] = 1，此时数组状态如下图：

当读到 4 的时候，数组的状态如下图：

当读取完之后，数组的状态如下图：

此时，我们再遍历一遍该字符数组，依次记录值为 1 的所有元素的下表，即 0,1,3,5,6,8,11，也就是1,2,4,6,7,9,12。 

比较方法一和方法二：

方法一，最好情况下的时间空间复杂度为 O(nlogn),O(nlogn)。

方法二，时间复杂度和空间复杂度完全依赖于数据集中最大的数字，为 O(n)，如果数据集合适，它是十分高效的算法。它的局限也很明显：数据集需是无重复集，数据分布比较密集，数据区间上下限差不能太大，最大数不宜过大。

技巧二：对有重复的数据进行判重

对于给定数据集（2，4，1，12，2，9，7，6，1，4）如何找出重复出现的数字？

方法一、使用排序算法排序，然后遍历找出重复出现的元素。

方法二、首先开辟出长度为 12 的位数组，并初始化为0。然后遍历元素集，对于每次出现的数据，如2，则令 a[2-1] = 1 ，如此这般，一直遍历到12，此时位数组的状态如下图：

对于下一个元素 2，当访问 a[1]时发现a[1]=1，说明2之前出现过，则2即为重复出现的数。

实际应用案例

应用1：某文件中包含一些 8 位的电话号码，统计电话号码出现的个数？

8位电话号码，最大的整数,为 99999999，需建立的位数组大概占用 100000000/8 = 1250000B = 12500K = 12.5MB，可以看出需要大约 12.5MB的空间。

应用2：某文件中包含一些 8 位的电话号码，统计只出现一次的号码？

这里需要扩展一下，可以用两个 bit 表示一个号码，00 代表没有出现过，01代表出现过一次，10表示出现过两次，11表示三次。此时，大约需要 25MB 的空间。

应用3：有两个文件，文件1中有1 亿个10位的qq号码，文件2中有5千万个10位的QQ号码，判断两个文件中重复出现的QQ号？

同应用1， 10位的QQ号最大数为 9999999999 ， 需建立的数组大约占用 1250MB 即 1.25G ，全部初始化为0,。读取第一个文件，将出现过的位标记为1。标记完之后，再读取第二个文件，对于读取到每一个号码，如果该号码对应的位为1，则说明该号码为重复QQ号。

应用4：有两个文件，文件1中含有1亿个15位的QQ号码，文件2中含有5千万个15位的QQ号码，判断两个文件中重复出现的QQ号？

在这里QQ号码的位数升级为15位了，如果还采用应用3的方法，此时需要的空间大概有125000GB = 125TB，显然这是不现实的，那么我们就要寻求别的解决方案。

Bloom Filter（布隆过滤器）

对于Bit-Map分析一下，每次都会开辟一块表示最大数值大小的bit数组，比如情景1中的12，将对应的数据经过映射到bit数组的下标，这其实是一种最简单的hash算法，对1去模。在上述应用4中，当qq号码改为15位的时候，Bit-Map就不太好用了，如何改进呢？解决办法：减少bit数组的长度，增加hash函数的个数。

对于每一个qq号码，我用K个hash函数，经过k次映射，得到k个不同位置，假设k=3，那么对于一个qq号码，映射到位数组中3个不同的位置。

当读取第二个包含5千万个qq号码的文件的时候，使用同样的3个hash函数进行映射，当3个位置全部是1的时候才表示出现过，否则表示没有出现过。

这种判重算法对于大数据量的情况下是十分高效的，因为所有的操作都是在内存中完成的，避免了磁盘读写对速度的影响。

但是这种算法并不能保证 100%的准确性，只能保证可控制的误差范围。这种可控误差的精确数学公式会在 BloomFilter 有关的文章中专门介绍。

大数据下-巧用位数组排序和判重及布隆过滤器的简单应用