40亿个QQ号，限度1G内存，如何去重？

40亿个unsigned int，如果间接用内存存储的话，须要：

4*4000000000 /1024/1024/1024 = 14.9G ，思考到其中有一些反复的话，那1G的空间也基本上是不够用的。

想要实现这个性能，能够借助位图。

应用位图的话，一个数字只须要占用1个bit，那么40亿个数字也就是：

4000000000 * 1 /8 /1024/1024 = 476M

相比于之前的14.9G来说，大大的节俭了很多空间。

比方要把我的QQ号"907607222"放到Bitmap中，就须要找到第907607222这个地位，而后把他设置成1就能够了。

这样，把40亿个数字都放到Bitmap之后，所有地位上是1的示意存在，不为1的示意不存在，雷同的QQ号只须要设置一次1就能够了，那么，最终就把所有是1的数字遍历进去就行了。

什么是BitMap？有什么用？

位图（BitMap），根本思维就是用一个bit来标记元素，bit是计算机中最小的单位，也就是咱们常说的计算机中的0和1，这种就是用一个位来示意的。

所谓位图，其实就是一个bit数组，即每一个地位都是一个bit，其中的取值能够是0或者1

像下面的这个位图，能够用来示意1，4，6：

如果不必位图的话，咱们想要记录1，4，6 这三个整型的话，就须要用三个unsigned int，已知每个unsigned int占4个字节，那么就是3*4 = 12个字节，一个字节有8 bit，那么就是 12*8 = 96 个bit。

所以，位图最大的益处就是节俭空间。

位图有很多种用处，特地适宜用在去重、排序等场景中，驰名的布隆过滤器就是基于位图实现的。

然而位图也有着肯定的限度，那就是他只能示意0和1，无奈存储其余的数字。所以他只适宜这种能示意ture or false的场景。

举荐一个开源收费的 Spring Boot 实战我的项目：

https://github.com/javastacks/spring-boot-best-practice

什么是布隆过滤器，实现原理是什么？

布隆过滤器是一种数据结构，用于疾速检索一个元素是否可能存在于一个汇合(bit 数组)中。

它的基本原理是利用多个哈希函数，将一个元素映射成多个位，而后将这些位设置为 1。当查问一个元素时，如果这些位都被设置为 1，则认为元素可能存在于汇合中，否则必定不存在

所以，布隆过滤器能够精确的判断一个元素是否肯定不存在，然而因为哈希抵触的存在，所以他没方法判断一个元素肯定存在。只能判断可能存在。

所以，布隆过滤器是存在误判的可能的，也就是当一个不存在的Hero元素，通过hash1、hash2和hash3之后，刚好和其余的值的哈希后果抵触了。那么就会被误判为存在，然而其实他并不存在。

想要升高这种误判的概率，次要的方法就是升高哈希抵触的概率及引入更多的哈希算法。

上面是布隆过滤器的工作过程：

1、初始化布隆过滤器

在初始化布隆过滤器时，须要指定汇合的大小和误判率。布隆过滤器外部蕴含一个bit数组和多个哈希函数，每个哈希函数都会生成一个索引值。

2、增加元素到布隆过滤器

要将一个元素增加到布隆过滤器中，首先须要将该元素通过多个哈希函数生成多个索引值，而后将这些索引值对应的位设置为 1。如果这些索引值曾经被设置为 1，则不须要再次设置。

3、查问元素是否存在于布隆过滤器中

要查问一个元素是否存在于布隆过滤器中，须要将该元素通过多个哈希函数生成多个索引值，并判断这些索引值对应的位是否都被设置为 1。如果这些位都被设置为 1，则认为元素可能存在于汇合中，否则必定不存在。

布隆过滤器的次要长处是能够疾速判断一个元素是否属于某个汇合，并且能够在空间和工夫上实现较高的效率。然而，它也存在一些毛病，例如：

  1. 布隆过滤器在判断元素是否存在时，有肯定的误判率。、
  2. 布隆过滤器删除元素比拟艰难，因为删除一个元素须要将其对应的多个位设置为 0，但这些位可能被其余元素共享。

利用场景

布隆过滤器因为他的效率十分高，所以被宽泛的应用，比拟典型的场景有以下几个：

1、网页爬虫： 爬虫程序能够应用布隆过滤器来过滤掉曾经爬取过的网页，防止反复爬取和浪费资源。

2、缓存零碎： 缓存零碎能够应用布隆过滤器来判断一个查问是否可能存在于缓存中，从而缩小查问缓存的次数，进步查问效率。布隆过滤器也常常用来解决缓存穿透的问题。

3、分布式系统： 在分布式系统中，能够应用布隆过滤器来判断一个元素是否存在于分布式缓存中，防止在所有节点上进行查问，缩小网络负载。

4、垃圾邮件过滤： 布隆过滤器能够用于判断一个邮件地址是否在垃圾邮件列表中，从而过滤掉垃圾邮件。

5、黑名单过滤： 布隆过滤器能够用于判断一个IP地址或手机号码是否在黑名单中，从而阻止歹意申请。

如何应用

Java中能够应用第三方库来实现布隆过滤器，常见的有Google Guava库和Apache Commons库以及Redis。

如Guava:

import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;public class BloomFilterExample {    public static void main(String[] args) {        // 创立布隆过滤器，预计插入100个元素，误判率为0.01        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);        // 插入元素        bloomFilter.put("Lynn");        bloomFilter.put("666");        bloomFilter.put("八股文");        // 判断元素是否存在        System.out.println(bloomFilter.mightContain("Lynn")); // true        System.out.println(bloomFilter.mightContain("张三"));  // false    }}

Apache Commons:

import org.apache.commons.lang3.StringUtils;import org.apache.commons.collections4.BloomFilter;import org.apache.commons.collections4.functors.HashFunctionIdentity;public class BloomFilterExample {    public static void main(String[] args) {        // 创立布隆过滤器，预计插入100个元素，误判率为0.01        BloomFilter<String> bloomFilter = new BloomFilter<>(HashFunctionIdentity.hashFunction(StringUtils::hashCode), 100, 0.01);        // 插入元素        bloomFilter.put("Lynn");        bloomFilter.put("666");        bloomFilter.put("八股文");        // 判断元素是否存在        System.out.println(bloomFilter.mightContain("Lynn")); // true        System.out.println(bloomFilter.mightContain("张三"));  // false    }}

Redis中能够通过Bloom模块来应用，应用Redisson能够：

Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379");RedissonClient redisson = Redisson.create(config);RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myfilter");bloomFilter.tryInit(100, 0.01);bloomFilter.add("Lynn");bloomFilter.add("666");bloomFilter.add("八股文");System.out.println(bloomFilter.contains("Lynn"));System.out.println(bloomFilter.contains("张三"));redisson.shutdown();

首先创立一个RedissonClient对象，而后通过该对象获取一个RBloomFilter对象，应用tryInit办法来初始化布隆过滤器，指定了最多能增加的元素数量为100，误判率为0.01。

而后，应用add办法将元素"犬小哈"、"666"和"八股文"增加到布隆过滤器中，应用contains办法来查看元素是否存在于布隆过滤器中。

或者Jedis也能够：

Jedis jedis = new Jedis("localhost");jedis.bfCreate("myfilter", 100, 0.01);jedis.bfAdd("myfilter", "Lynn");jedis.bfAdd("myfilter", "666");jedis.bfAdd("myfilter", "八股文");System.out.println(jedis.bfExists("myfilter", "Lynn"));System.out.println(jedis.bfExists("myfilter", "张三"));jedis.close();

版权申明：本文为CSDN博主「code.song」的原创文章，遵循CC 4.0 BY-SA版权协定，转载请附上原文出处链接及本申明。原文链接：https://blog.csdn.net/songmulin/article/details/130814507

近期热文举荐：

1.1,000+ 道 Java面试题及答案整顿(2022最新版)

2.劲爆！Java 协程要来了。。。

3.Spring Boot 2.x 教程，太全了！

4.别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！

5.《Java开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞+转发哦！