数据结构之位图和布隆过滤器

系列文章目录

数据结构之ArrayList_arraylist o(1) o(n)-CSDN博客

数据结构之LinkedList-CSDN博客

数据结构之栈_栈有什么方法-CSDN博客

数据结构之队列-CSDN博客

数据结构之二叉树-CSDN博客

数据结构之优先级队列-CSDN博客

常见的排序方法-CSDN博客

数据结构之Map和Set-CSDN博客

数据结构之二叉平衡树-CSDN博客

系列文章目录

前言

一、位图

1. 位图的概念

2. 位图的模拟实现

3. 位图的应用

二、布隆过滤器

1. 布隆过滤器的概念

2. 布隆过滤器的模拟实现

3. 布隆过滤器误判

4. 布隆过滤器和哈希表对比

5. 布隆过滤器的应用

三、海量数据问题的解决思路

问题 1：

问题 2：

问题 3：

问题 4：

问题 5：

问题 6：

四、一致性哈希

1. 普通的哈希算法

2. 一致性哈希算法

五、哈希与加密

前言

本文介绍了两种高效处理海量数据的数据结构：位图和布隆过滤器。位图通过二进制位存储状态，适合整数查询，40亿数据仅需500M空间。布隆过滤器扩展到位图存储字符串，通过多个哈希函数减少冲突，但存在误判可能。文章还讨论了海量数据问题的解决思路，包括哈希切割、双位图统计等，并对比了一致性哈希与普通哈希的区别。最后区分了哈希算法（不可逆）与加密算法（可逆）的特性。这些数据结构和技术特别适用于需要高效查询和节省内存的大数据场景。

一、位图

1. 位图的概念

位图是利用某个位存放某种状态的数据结构，例如可以用一个字节中的 8 个位，用来表示 0 ~ 7 这 8 个数字是否存在，如果第 i 位是 1，表示 i 存在，是 0 表示不存在；

2. 位图的模拟实现

elem 定义一个 byte[] 数组，用来存放某个数字是否在位图中存在；

usedSize 表示存放数字的个数；

MyBitSet() 构造方法，默认开辟的空间为 1 个字节；

set(int val): void 将 val 存放到位图中；

思路：将位图中的第 val 个位置 1;

定义 byteIndex 表示第几个字节，bitIndex 表示第几个位；例如存放数字 12 到位图中，就需要将第 1 字节的第 4 位置 1；

存放数据是要注意是否存满，满了存放之前要扩容；存放完成后，usedSize++；

get(int val): boolean 表示 val 是否在位图中存在，存在返回 true，不存在返回 false；

reset(int val): void 将 val 在位图中删除，删除完成后 usedSize--；

getUsedSize()：返回存放元素的个数；

public class MyBitSet {public byte[] elem;private int usedSize;public MyBitSet(){this.elem = new byte[1];}public MyBitSet(int n){this.elem = new byte[n / 8 + 1];}public void set(int val){if(val < 0){throw new PosOutOfBoundsException();}int byteIndex = val / 8;int bitIndex = val % 8;if(byteIndex >= this.elem.length){this.elem = Arrays.copyOf(this.elem, byteIndex + 1);}this.elem[byteIndex] |= (1 << bitIndex);this.usedSize++;}public boolean get(int val){if(val < 0 || val / 8 >= this.elem.length){throw new PosOutOfBoundsException();}int byteIndex = val / 8;int bitIndex = val % 8;if(((this.elem[byteIndex] >> bitIndex) & 1) == 1){return true;}return false;}public void reset(int val){if(val < 0 || val / 8 >= this.elem.length){throw new PosOutOfBoundsException();}int byteIndex = val / 8;int bitIndex = val % 8;this.elem[byteIndex] &= ~(1 << bitIndex);this.usedSize--;}public int getUsedSize(){return this.usedSize;}
}

3. 位图的应用

位图适合海量数据的查询：

假设有 40 亿个不重复的整数，并且没有进行过排序，如何判断某个数是否在这 40 亿个数中？

通常使用遍历一遍进行查找的时间复杂度是 O(N)；使用排序加二分的查找方式，时间复杂度是 O(N*logN) + O(logN)；

如果使用位图，将这 40 亿个整数都放在位图当中，查询某个整数的时间复杂度只是 O(1)，因为只需要判断该整数对应的位是否被置 1 即可；

位图的优势：存放 40 亿个整数大于需要 16G，通常来说内存是存不下的，如果使用位图，500M就能存下，因此位图更适用于海量数据的查询；

位图的缺点：位图只能存放整数，适用于数据无重复的场景；

二、布隆过滤器

1. 布隆过滤器的概念

布隆过滤器利用哈希函数，可以将字符串转化为某个整数，再存放在位图里，解决了位图不能存放字符串的问题，更适合实际应用；它是一种紧凑的，概率型数据结构，可以进行高效的插入和查询；

2. 布隆过滤器的模拟实现

DEFAULT_SIZE 默认开辟空间的大小；

bitSet 位图，用于存放通过哈希函数生成的整数；

usedSize 存放元素的个数；

seeds 随机种子，用于不同的哈希函数生成不同的哈希算法；

simpleHashes 简单的哈希函数；

MyBloomFilter() 构造方法，定义一个布隆过滤器，开辟默认大小的空间，生成多个不同的哈希函数；

add(String val): void 在布隆过滤器中存放元素；

思路：针对同一个字符串，利用不同的哈希函数，生成多个不同的整数，都存放再位图当中；

contains(String val): boolean 判断布隆过滤器中是否包含 val，包含返回 true，不包含返回 false；

思路：对同一个字符串，利用不同的哈希函数，生成多个不同的整数，在位图中检查这些整数对应的位是否被置 1；

public class MyBloomFilter {public static final int DEFAULT_SIZE = 1 << 20;// 位图public BitSet bitSet;public int usedSize;public static final int[] seeds = {5, 7, 11, 13, 27, 33};public SimpleHash[] simpleHashes;public MyBloomFilter(){bitSet = new BitSet(DEFAULT_SIZE);simpleHashes = new SimpleHash[seeds.length];for(int i = 0; i < seeds.length; i++){simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);}}public void add(String val){for(int i = 0; i < simpleHashes.length; i++){int index = simpleHashes[i].hash(val);bitSet.set(index);}this.usedSize++;}public boolean contains(String val){for(int i = 0; i < simpleHashes.length; i++){int index = simpleHashes[i].hash(val);if(!bitSet.get(index)) return false;}return true;}
}class SimpleHash{public int cap;public int seed;public SimpleHash(int cap, int seed){this.cap = cap;this.seed = seed;}public int hash(String key){int h;// (n - 1) & hashreturn (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));}
}

3. 布隆过滤器误判

布隆过滤器中存在多个哈希函数，但仍然会有一定的概率多个哈希函数针对不同的字符串 s1 和 s2计算出了相同的哈希值，如果容器里面存放了 s1，进行查询的时候就会误以为也存了 s2；

因此布隆过滤器确定某个元素不存在时，该元素一定不存在；确定某个元素存在时，该元素只是可能存在，并不一定存在，因为会存在误判的情况；

4. 布隆过滤器和哈希表对比

哈希表查询速度很快，但是对空间的利用率并不高，通常只有 50%；当在海量数据的应用场景下，哈希表存储效率的问题就会显现出来；

而布隆过滤器使用哈希加位图的思想，通过不同的哈希函数，计算出不同对象的哈希值，在位图当中存储，既解决了哈希表空间利用率低的问题，又保证了查询效率，但是它会存在误判的情况，在准确性方面是不如哈希表的。

5. 布隆过滤器的应用

布隆过滤器是在哈希和位图的基础上实现的，因此布隆过滤器也适用于海量数据的查询，并且占用的内存较小；

布隆过滤器的优点：

查询元素的时间复杂度为 O(k)，k 为哈希函数的个数；
哈希函数之间没有关系，方便硬件并行运算；
布隆过滤器不需要存储元素本身，在对保密要求比较严格的场合有很大优势；
在能够承受一定的误判率时，布隆过滤器比其他的数据结构有很大的空间优势；

布隆过滤器的缺点：

布隆过滤器会存在误判的情况，因为哈希函数针对不同的字符串有可能计算出相同的哈希值，即哈希冲突；
布隆过滤器不能获取元素本身；
一般情况不能从布隆过滤器中删除元素；

google 的 guava 包中有对布隆过滤器的实现；

布隆过滤器可用于网页爬虫时，对 URL 进行去重，避免重复爬相同的 URL；

垃圾邮件过滤，可以从十几亿个垃圾邮件地址判断某邮箱是否是垃圾邮箱；

三、海量数据问题的解决思路

问题 1：

假设有一个超过 100G 大小的 log file，log 中存放这 IP地址，如何找到出现次数最多的 IP 地址，及如何找到出现频率前 k 的IP地址？

解法一：哈希表

如果不考虑占用空间的大小，可以使用哈希表来统计每一个 IP 的数量，找到出现次数最多的即可；

解法二：哈希切割

但 100G 的数据是无法一次性加载到内存当中，需要将 100G 的数据分割成若干个小文件；分别统计每一个文件中出现次数最多的 IP 地址及次数,找出出现次数前 k 个 IP 地址即可；

注意：分割不能采用均分方式，因为一个小文件中出现最多次数的 IP 不一定是所有 IP 中出现次数最多的IP；

分割文件采用哈希切割的方式，即对不同的 IP 计算哈希值，哈希值相同的 IP 存放到一个文件当中，读取每一个文件，统计每个 IP 出现的次数，找到前 k 个即可；

问题 2：

给定 100 亿个整数，设计算法找到其中只出现一次的数字；

解法一：哈希切割

使用哈希切割的方式，分成若干个小文件，计算所有数字的哈希值，将具有相同哈希值的数字放到一个文件中，读取每一个文件，找到只出现一次的数字；

解法二：两个位图

使用两个位图 bitSet1 和 bitSet2，遍历 100 亿整数：

出现一次就将 bitSet1 中的对应位置 1；

出现两次则将 bitSet2 中的对应位置 1，bitSet1 中的对应位置 0；

出现三次或者三次以上，就将 bitSet1 和 bitSet2 中的对应位都置 1；

遍历位图，找到只出现一次的数字。

解法三：一个位图

使用位图中连续的两个位来表示出现的次数，00 表示没出现，01 表示出现一次，10 表示出现两次，11 表示出现三次及三次以上；

遍历位图，找到出现一次的整数；

在位图中存放时：

字节序号：byteIndex = val / 4；位序号：bitIndex = （val % 4）* 2；

问题 3：

给两个文件，每个文件有 100 亿个整数，只有 1G 内存，如何找到两个文件的交集？

解法一：哈希切割

遍历第一个文件，将所有的整数都通过哈希计算，具有相同哈希值的数字，都放到一个文件当中，形成若干个小文件，用 A[i] 表示；

遍历第二个文件，将所有的整数都通过哈希计算，具有相同哈希值的数字，都放到一个文件当中，形成若干个小文件，用 B[i] 表示；

将 A[i] 和 B[i] 缓存到内存中，找到相同的数字，都存放到结果文件中；

最终遍历完所有的小文件，得到的就是结果文件就是交集；

解法二：位图

创建一个位图 bitSet，遍历第一个文件，将第一个文件的整数都放到 bitSet 中；

遍历第二个文件，并在 bitSet 中查找，找到的所有数据就是两个文件的交集；

衍生问题：如果求上述问题中数据的并集和差集？

创建一个位图 bitSet1，遍历第一个文件，将第一个文件的所有的数字都放到 bitSet1 中；

创建一个位图 bitSet2，遍历第二个文件，将第二个文件的所有的数字都放到 bitSet2 中；

遍历位图，将第一个位图和第二个位图的每一位进行按位或操作，得到的新的位图 bitSet3；

遍历 bitSet3，将位图中的数字都存到新的文件当中，新的文件就是并集；

如果进行按位与操作，得到的数据就是交集；

如果进行按位异或操作，得到的数据就是差集；

问题 4：

一个文件有 100 亿个整数，现有 1G 内存，设计算法找到出现不超过两次的所有整数；

解法一：哈希切割

遍历文件，将所有的整数都通过哈希计算，具有相同哈希值的数字，都放到一个文件当中，形成若干个小文件；

遍历每一个小文件，统计所有数字的出现次数，找出出现次数不超过两次的整数；

解法二：两个位图

创建两个位图 bitSet1 和 bitSet2：

出现一次就将 bitSet1 中的对应位置 1；

出现两次则将 bitSet2 中的对应位置 1，bitSet1 中的对应位置 0；

出现三次或者三次以上，就将 bitSet1 和 bitSet2 中的对应位都置 1；

遍历位图，找到只出现一次和出现两次的数字。

问题 5：

给两个文件，分别有 100 亿个 query，我们只有 1G 内存，如何找到两个文件的交集，分别给出精确算法和近似算法；

精确算法：哈希切割

遍历第一个文件，使用哈希函数计算每一个 query 对应的哈希值，相同哈希值的 query 放到同一个文件中，形成若干个小文件 A[i]；

遍历第二个文件，使用哈希函数计算每一个 query 对应的哈希值，相同哈希值的 query 放到同一个文件中，形成若干个小文件 B[i]；

分别求 A[i] 和 B[i] 的交集，得到所有的交集的并集就是两个大文件的交集；

近似算法：布隆过滤器

遍历第一个文件，将所有的 query 都映射到布隆过滤器中，读取第二个文件，去布隆过滤器中查找，得到的所有 query 就是交集，但有可能会出现误判；

问题 6：

如何扩展布隆过滤器，使它能够支持删除操作？

将布隆过滤器的每个位都扩展成一个小的计数器，插入元素时给 k 个计数器加 1，删除元素时给每个计数器减 1；

但是当哈希冲突多了，计数器有可能溢出；

四、一致性哈希

1. 普通的哈希算法

假设有一张图片需要缓存到服务器上，如果有三台服务器，通过哈希函数求到图片对应的哈希值，哈希值 % 3 就找到了对应的服务器，将图片缓存即可。“哈希值 % 服务器数量”的这种算法，就是普通的哈希算法；

普通哈希算法的缺陷：

如果新增服务器，或者某台服务器损坏，服务器的数量就会发生改变；

如果哈希函数不变，同一张图片算出来的哈希值就会改变，那么所有的缓存就会失效，造成缓存的雪崩；

应用获取不到这些图片，就会向后端发送请求，大量的请求会带给服务器巨大的压力，有可能导致服务器宕机。

2. 一致性哈希算法

一致性哈希算法：使用服务器的 IP 或者编号，主机名等 % 2^32；

一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环，称为 Hash 环；

将各个主机使用哈希函数进行哈希，确定主机在哈希环上的位置；

将图片使用同样的哈希函数进行哈希，确定图片在哈希环上的位置；因为图片不一定正好和主机在同一个位置，因此需要将图片存到它顺时针旋转遇到的第一台服务器；

优点：即使出现服务器宕机，也会只有一部分图片需要缓存到下一台服务器，不会出现大量缓存雪崩；也不会向后端发送大量的请求，带给服务器巨大压力；

缺点：如果哈希环出现倾斜（服务器分布不均匀），大部分数据缓存在某一台服务器上，可能导致这台服务器宕机，之后所有图片再缓存到下一台服务器，再造成下一台服务器宕机，最终会导致服务器集群宕机；

解决方法：使用服务器虚拟节点，每个服务器创建多个虚拟节点，均匀分布在哈希环上，这样图片缓存就会均匀分布在多态服务器上；

五、哈希与加密

哈希算法往往设计成输出相同长度的哈希值，例如 MD5 算法，是不可逆的；

加密算法输出的加密数据往往和输入数据的长度成正比，不一定都是长度相同的，是可逆的；