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

(資料圖片僅供參考)

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

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

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

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

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

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

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

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

什么是BitMap？有什么用？

位圖（BitMap），基本思想就是用一個(gè)bit來(lái)標(biāo)記元素，bit是計(jì)算機(jī)中最小的單位，也就是我們常說(shuō)的計(jì)算機(jī)中的0和1，這種就是用一個(gè)位來(lái)表示的。

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

像上面的這個(gè)位圖，可以用來(lái)表示1，4，6：

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

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

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

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

推薦一個(gè)開源免費(fèi)的 Spring Boot 實(shí)戰(zhàn)項(xiàng)目：

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

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

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

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

所以，布隆過(guò)濾器可以準(zhǔn)確的判斷一個(gè)元素是否一定不存在，但是因?yàn)楣_突的存在，所以他沒(méi)辦法判斷一個(gè)元素一定存在。只能判斷可能存在。

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

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

下面是布隆過(guò)濾器的工作過(guò)程：

1、初始化布隆過(guò)濾器

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

2、添加元素到布隆過(guò)濾器

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

3、查詢?cè)厥欠翊嬖谟诓悸∵^(guò)濾器中

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

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

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

應(yīng)用場(chǎng)景

布隆過(guò)濾器因?yàn)樗男史浅８撸员粡V泛的使用，比較典型的場(chǎng)景有以下幾個(gè)：

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

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

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

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

5、黑名單過(guò)濾：布隆過(guò)濾器可以用于判斷一個(gè)IP地址或手機(jī)號(hào)碼是否在黑名單中，從而阻止惡意請(qǐng)求。

如何使用

Java中可以使用第三方庫(kù)來(lái)實(shí)現(xiàn)布隆過(guò)濾器，常見的有Google Guava庫(kù)和Apache Commons庫(kù)以及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)建布隆過(guò)濾器，預(yù)計(jì)插入100個(gè)元素，誤判率為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)建布隆過(guò)濾器，預(yù)計(jì)插入100個(gè)元素，誤判率為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中可以通過(guò)Bloom模塊來(lái)使用，使用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)建一個(gè)RedissonClient對(duì)象，然后通過(guò)該對(duì)象獲取一個(gè)RBloomFilter對(duì)象，使用tryInit方法來(lái)初始化布隆過(guò)濾器，指定了最多能添加的元素?cái)?shù)量為100，誤判率為0.01。

然后，使用add方法將元素"犬小哈"、"666"和"八股文"添加到布隆過(guò)濾器中，使用contains方法來(lái)檢查元素是否存在于布隆過(guò)濾器中。

或者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)載請(qǐng)附上原文出處鏈接及本聲明。原文鏈接：https://blog.csdn.net/songmulin/article/details/130814507

近期熱文推薦：

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

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

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

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

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

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

關(guān)鍵詞：