大量数据去重：Bitmap和布隆过滤器(Bloom Filter)。

曾经终败给现在 2024-02-18 23:29 8阅读 0赞

> 5TB的硬盘上放满了数据，请写一个算法将这些数据进行排重。如果这些数据是一些**32bit**大小的数据该如何解决？如果是**64bit**的呢？

在面试时遇到的问题，问题的解决方案十分典型，但对于**海量数据处理**接触少的同学可能一时也想不到什么好方案。介绍两个算法，对于空间的利用到达了一种极致，那就是Bitmap和[布隆过滤器(Bloom Filter)][Bloom Filter]。

## Bitmap算法 ##

在网上并没有找到Bitmap算法的中文翻译，在《编程珠玑》中有提及。与其说是算法，不如说是一种紧凑的数据存储结构。其实如果并非如此大量的数据，有很多排重方案可以使用，典型的就是**哈希表**。

public int[] removeDuplicates(int[] array) {
        int index = 0;
        Map<Integer, Boolean> maps = new LinkedHashMap<Integer, Boolean>();
        for(int num : array) {
            if(!maps.contains(num)) {
                array[index] = num;
                index++;
                maps.put(num, true);
            }
        }
    
        return newArray;
    }

实际上，哈希表实际上为**每一个可能出现的数字**提供了一个**一一映射**的关系，每个元素都相当于有了自己的独享的一份空间，这个映射由散列函数来提供（这里我们先不考虑碰撞）。实际上哈希表甚至还能记录每个元素出现的次数，这样的数据结构完成这个任务有点“大材小用”了。

我们拆解一下我们的需求：

1.  集合中每个元素（示例中是`int`）有一个**独享的空间**
2.  找到一个到这个空间的**映射方法**

这个空间要多大？对于我们的问题来说，一个boolean就够了，或者说，1个bit就够了，我们**只想知道某个元素出现过没有**。如果为每个所有可能的值分配1个bit，32bit的`int`所有可能取值需要内存空间为：

**232bit=229Byte=512MB**

那怎么样完成这个映射呢？其实就是Bitmap所要完成的工作了。如果我们把整型0x01、0x02、…、0x08的空间依次映射到一个Byte上，每个bit就代表这个`int`值是否出现过，初值为0（false）。

若扩展到整个`int`取值域，申请一个`byte[]`即可，示例代码如下：

public static final int _1MB = 1024 * 1024;
    //每个byte记录8bit信息,也就是8个数是否存在于数组中
    public static byte[] flags = new byte[ 512 * _1MB ];
    
    
    public static void main(String[] args) {
        //待判重数据
        int[] array = {255, 1024, 0, 65536, 255};
    
        int index = 0;
        for(int num : array) {
            if(!getFlags(num)) {
                //未出现的元素
                array[index] = num;
                index = index + 1;
                //设置标志位
                setFlags(num);
                System.out.println("set " + num);
            } else {
                System.out.println(num + " already exist");
            }
        }
    }
    
    public static void setFlags(int num) {
        //使用每个数的低三位作为byte内的映射
        //例如: 255 = 0x11111111
        //低三位(也就是num & (0x07))为0x111 = 7, 则byte的第7位为1, 表示255已存在
        flags[num >> 3] |= 0x01 << (num & (0x07));
    }
    
    public static boolean getFlags(int num) {
        return (flags[num >> 3] >> (num & (0x07)) & 0x01) == 0x01;
    }

其实，就是按`int`从小到大的顺序依次摆放到`byte[]`中，仅涉及到一些除以2的整次幂和对2的整次幂取余的位操作小技巧。很显然，对于小数据量、数据取值很稀疏，上面的方法并没有什么优势，但对于**海量的、取值分布很均匀**的集合进行去重，Bitmap极大地压缩了所需要的内存空间。于此同时，还额外地完成了对原始数组的排序工作。缺点是，Bitmap对于每个元素只能记录1bit信息，如果还想完成额外的功能，恐怕只能靠牺牲更多的空间、时间来完成了。

## 布隆过滤器（Bloom Filter） ##

然而Bitmap不是万能的，如果数据量大到一定程度，如开头写的64bit类型的数据，还能不能用Bitmap？我们来算一算：

**264bit=261Byte=2048PB=2EB**

EB（Exabyte，艾字节）这个计算机科学中统计数据量的单位有多大，有兴趣的小伙伴可以查阅下资料。这个量级的Bitmap，已经不是人类硬件所能承担的了。我相信谁也不会想用集群去计算这么一个问题吧？所以Bitmap的好处在于**空间复杂度不随原始集合内元素的个数增加而增加**，而它的坏处也源于这一点——**空间复杂度随集合内最大元素增大而线性增大**。

所以接下来，我们要引入另一个著名的工业实现——**布隆过滤器（Bloom Filter）**。如果说Bitmap对于每一个可能的整型值，通过直接寻址的方式进行映射，相当于使用了一个哈希函数，那布隆过滤器就是引入了k(k>1)个**相互独立**的哈希函数，保证在给定的空间、**误判率**下，完成元素判重的过程。下图中是k=3时的布隆过滤器。  
![图1 布隆过滤器（来源：wiki）][1 _wiki]

x,y,z经由哈希函数映射将各自在Bitmap中的3个位置置为1，当w出现时，仅当3个标志位都为1时，才表示w在集合中。图中所示的情况，布隆过滤器将判定w不在集合中。

那么布隆过滤器的误差有多少？我们假设所有哈希函数散列足够均匀，散列后落到Bitmap每个位置的**概率均等**。Bitmap的大小为m、原始数集大小为n、哈希函数个数为k：

*  1个散列函数时，接收一个元素时Bitmap中某一位置为0的概率为：
    
    1−1/m
 *  k个相互独立的散列函数，接收一个元素时Bitmap中某一位置为0的概率为：

(1−1/m)k

*  假设原始集合中，所有元素都不相等（最严格的情况），将所有元素都输入布隆过滤器，此时某一位置仍为0的概率为：

(1−1/m)nk

*  某一位置为1的概率为：

1−(1−1/m)nk

*  当我们对某个元素进行判重时，误判即这个元素对应的k个标志位**不全为1**，但**所有k****个标志位都被置为1**，误判率ε**约**为：

ε≈\[1−(1−1/m)nk\]k

*  这个误判率应当比实际值大，因为将判断正确的情况也算进去了。根据著名极限limn→∞(1+1/n)n=e可以得到：

ε≈\[1−e−nk/m\]k

ε得到最优解[1][]，当且仅当：

k=m/nln2≈0.7m/n

此时，误判率ε与数集大小和

ε≈(1−e−ln2)ln2mn=0.5ln2mn=0.5k

回到我们的问题中，有趣的是由于硬盘空间是限制死的，**集合元素个数n****的大小反而与单个数据的比特数成反比**，数据长度为64bit时，

n =5TB/64bit=5×240Byte/8Byte≈234

若以m=16n计算，Bitmap集合的大小为238bit=235Byte=32GB，此时的ε≈0.0005。并且要知道，以上计算的都是误差的**上限**。

布隆过滤器通过引入一定错误率，使得海量数据判重在可以接受的内存代价中得以实现。从上面的公式可以看出，随着集合中的元素不断输入过滤器中(n增大)，误差将越来越大。但是，当Bitmap的大小m（指bit数）足够大时，比如比**所有可能出现的不重复元素个数**还要大10倍以上时，错误概率是可以接受的。

最后我们所要做的，就是实现一个布隆过滤器，然后利用它对硬盘上的5TB数据一一判重，并写回硬盘中。这其中可能涉及到利用读写的buffer，待有时间补上。

### 基本思想 ###

我们用一个哈希算法(Hash函数)将一个集合元素映射到一个二进制位数组（位数组）中的某一位。如果该位已经被置为1，那么表示该元素已经存在。为了减少hash冲突问题,所以引用了多个哈希函数,如果通过其中的一个Hash值得出某元素不在集合中，那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能确定该元素存在于集合中。这便是Bloom-Filter的基本思想。

## 附录 ##

这里有一个google实现的布隆过滤器，我们来看看它的误判率：

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    import java.util.HashSet;
    import java.util.Random;
    
    public class testBloomFilter {
    
        static int sizeOfNumberSet = Integer.MAX_VALUE >> 4;
    
        static Random generator = new Random();
    
        public static void main(String[] args) {
    
            int error = 0;
            HashSet<Integer> hashSet = new HashSet<Integer>();
            BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), sizeOfNumberSet);
    
            for(int i = 0; i < sizeOfNumberSet; i++) {
                int number = generator.nextInt();
                if(filter.mightContain(number) != hashSet.contains(number)) {
                    error++;
                }
                filter.put(number);
                hashSet.add(number);
            }
    
            System.out.println("Error count: " + error + ", error rate = " + String.format("%f", (float)error/(float)sizeOfNumberSet));
        }
    }

在这个实现中，Bitmap的集合m、输入的原始数集合n、哈希函数k的取值都是按照上面最优的方案选取的，默认情况下保证误判率ε=0.5k<0.03≈0.55，因而此时k=5。

/**
     * Creates a {@link BloomFilter BloomFilter<T>} with the expected number of
     * insertions and a default expected false positive probability of 3%.
     */
    public static <T> BloomFilter<T> create(Funnel<T> funnel, int expectedInsertions /* n */) {
        return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
    }

而还有一个很有趣的地方是，实际使用的却并不是5个哈希函数。实际进行映射时，而是分别使用了一个64bit哈希函数的高、低32bit进行循环移位。注释中包含着这个算法的论文“Less Hashing, Same Performance: Building a Better Bloom Filter”，论文中指明其对过滤器性能没有明显影响。很明显这个实现对于m>232

时的支持并不好，因为当大于231−1的下标在算法中并不能被映射到。

enum BloomFilterStrategies implements BloomFilter.Strategy {
      /**
       * See "Less Hashing, Same Performance: Building a Better Bloom Filter" by Adam Kirsch and
       * Michael Mitzenmacher. The paper argues that this trick doesn't significantly deteriorate the
       * performance of a Bloom filter (yet only needs two 32bit hash functions).
       */
      MURMUR128_MITZ_32() {
        @Override public <T> boolean put(T object, Funnel<? super T> funnel,
            int numHashFunctions, BitArray bits) {
          long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
          int hash1 = (int) hash64;
          int hash2 = (int) (hash64 >>> 32);
          boolean bitsChanged = false;
          for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
              nextHash = ~nextHash;
            }
            bitsChanged |= bits.set(nextHash % bits.bitSize());
          }
          return bitsChanged;
        }
    
        @Override public <T> boolean mightContain(T object, Funnel<? super T> funnel,
            int numHashFunctions, BitArray bits) {
          long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
          int hash1 = (int) hash64;
          int hash2 = (int) (hash64 >>> 32);
          for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
              nextHash = ~nextHash;
            }
            if (!bits.get(nextHash % bits.bitSize())) {
              return false;
            }
          }
          return true;
        }
      };
      ...
    }

转载：[https://blog.csdn.net/zdxiq000/article/details/57626464][https_blog.csdn.net_zdxiq000_article_details_57626464]

[Bloom Filter]: https://en.wikipedia.org/wiki/Bloom_filter
[1 _wiki]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/b065998d2cf840b4ab28b64005f7e338.png
[1]: https://blog.csdn.net/zdxiq000/article/details/57626464#fn:1
[https_blog.csdn.net_zdxiq000_article_details_57626464]: https://blog.csdn.net/zdxiq000/article/details/57626464