40億個QQ號，限制1G內(nèi)存，如何去重？

(資料圖片僅供參考)

40億個unsigned int，如果直接用內(nèi)存存儲的話，需要：

4*4000000000 /1024/1024/1024 = 14.9G，考慮到其中有一些重復的話，那1G的空間也基本上是不夠用的。

想要實現(xiàn)這個功能，可以借助位圖。

使用位圖的話，一個數(shù)字只需要占用1個bit，那么40億個數(shù)字也就是：

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

相比于之前的14.9G來說，大大的節(jié)省了很多空間。

比如要把我的QQ號"907607222"放到Bitmap中，就需要找到第907607222這個位置，然后把他設(shè)置成1就可以了。

這樣，把40億個數(shù)字都放到Bitmap之后，所有位置上是1的表示存在，不為1的表示不存在，相同的QQ號只需要設(shè)置一次1就可以了，那么，最終就把所有是1的數(shù)字遍歷出來就行了。

什么是BitMap？有什么用？

位圖（BitMap），基本思想就是用一個bit來標記元素，bit是計算機中最小的單位，也就是我們常說的計算機中的0和1，這種就是用一個位來表示的。

所謂位圖，其實就是一個bit數(shù)組，即每一個位置都是一個bit，其中的取值可以是0或者1

像上面的這個位圖，可以用來表示1，4，6：

如果不用位圖的話，我們想要記錄1，4，6 這三個整型的話，就需要用三個unsigned int，已知每個unsigned int占4個字節(jié)，那么就是3*4 = 12個字節(jié)，一個字節(jié)有8 bit，那么就是 12*8 = 96個bit。

所以，位圖最大的好處就是節(jié)省空間。

位圖有很多種用途，特別適合用在去重、排序等場景中，著名的布隆過濾器就是基于位圖實現(xiàn)的。

但是位圖也有著一定的限制，那就是他只能表示0和1，無法存儲其他的數(shù)字。所以他只適合這種能表示ture or false的場景。

推薦一個開源免費的 Spring Boot 實戰(zhàn)項目：

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

什么是布隆過濾器，實現(xiàn)原理是什么？

布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，用于快速檢索一個元素是否可能存在于一個集合(bit 數(shù)組)中。

它的基本原理是利用多個哈希函數(shù)，將一個元素映射成多個位，然后將這些位設(shè)置為 1。當查詢一個元素時，如果這些位都被設(shè)置為 1，則認為元素可能存在于集合中，否則肯定不存在

所以，布隆過濾器可以準確的判斷一個元素是否一定不存在，但是因為哈希沖突的存在，所以他沒辦法判斷一個元素一定存在。只能判斷可能存在。

所以，布隆過濾器是存在誤判的可能的，也就是當一個不存在的Hero元素，經(jīng)過hash1、hash2和hash3之后，剛好和其他的值的哈希結(jié)果沖突了。那么就會被誤判為存在，但是其實他并不存在。

想要降低這種誤判的概率，主要的辦法就是降低哈希沖突的概率及引入更多的哈希算法。

下面是布隆過濾器的工作過程：

1、初始化布隆過濾器

在初始化布隆過濾器時，需要指定集合的大小和誤判率。布隆過濾器內(nèi)部包含一個bit數(shù)組和多個哈希函數(shù)，每個哈希函數(shù)都會生成一個索引值。

2、添加元素到布隆過濾器

要將一個元素添加到布隆過濾器中，首先需要將該元素通過多個哈希函數(shù)生成多個索引值，然后將這些索引值對應(yīng)的位設(shè)置為 1。如果這些索引值已經(jīng)被設(shè)置為 1，則不需要再次設(shè)置。

3、查詢元素是否存在于布隆過濾器中

要查詢一個元素是否存在于布隆過濾器中，需要將該元素通過多個哈希函數(shù)生成多個索引值，并判斷這些索引值對應(yīng)的位是否都被設(shè)置為 1。如果這些位都被設(shè)置為 1，則認為元素可能存在于集合中，否則肯定不存在。

布隆過濾器的主要優(yōu)點是可以快速判斷一個元素是否屬于某個集合，并且可以在空間和時間上實現(xiàn)較高的效率。但是，它也存在一些缺點，例如：

1. 布隆過濾器在判斷元素是否存在時，有一定的誤判率。、
2. 布隆過濾器刪除元素比較困難，因為刪除一個元素需要將其對應(yīng)的多個位設(shè)置為 0，但這些位可能被其他元素共享。

應(yīng)用場景

布隆過濾器因為他的效率非常高，所以被廣泛的使用，比較典型的場景有以下幾個：

1、網(wǎng)頁爬蟲：爬蟲程序可以使用布隆過濾器來過濾掉已經(jīng)爬取過的網(wǎng)頁，避免重復爬取和浪費資源。

2、緩存系統(tǒng)：緩存系統(tǒng)可以使用布隆過濾器來判斷一個查詢是否可能存在于緩存中，從而減少查詢緩存的次數(shù)，提高查詢效率。布隆過濾器也經(jīng)常用來解決緩存穿透的問題。

3、分布式系統(tǒng)：在分布式系統(tǒng)中，可以使用布隆過濾器來判斷一個元素是否存在于分布式緩存中，避免在所有節(jié)點上進行查詢，減少網(wǎng)絡(luò)負載。

4、垃圾郵件過濾：布隆過濾器可以用于判斷一個郵件地址是否在垃圾郵件列表中，從而過濾掉垃圾郵件。

5、黑名單過濾：布隆過濾器可以用于判斷一個IP地址或手機號碼是否在黑名單中，從而阻止惡意請求。

如何使用

Java中可以使用第三方庫來實現(xiàn)布隆過濾器，常見的有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) {        // 創(chuàng)建布隆過濾器，預計插入100個元素，誤判率為0.01        BloomFilter 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) {        // 創(chuàng)建布隆過濾器，預計插入100個元素，誤判率為0.01        BloomFilter 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 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();

首先創(chuàng)建一個RedissonClient對象，然后通過該對象獲取一個RBloomFilter對象，使用tryInit方法來初始化布隆過濾器，指定了最多能添加的元素數(shù)量為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();

版權(quán)聲明：本文為CSDN博主「code.song」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。原文鏈接：https://blog.csdn.net/songmulin/article/details/130814507

近期熱文推薦：

1.1,000+ 道 Java面試題及答案整理(2022最新版)

2.勁爆！Java 協(xié)程要來了。。。

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

4.別再寫滿屏的爆爆爆炸類了，試試裝飾器模式，這才是優(yōu)雅的方式??！

5.《Java開發(fā)手冊（嵩山版）》最新發(fā)布，速速下載！

覺得不錯，別忘了隨手點贊+轉(zhuǎn)發(fā)哦！

關(guān)鍵詞：