> 40億個QQ號，限制1G記憶體，如何去重？ 40億個unsigned int，如果直接用記憶體存儲的話，需要： `4*4000000000 /1024/1024/1024 = 14.9G` ，考慮到其中有一些重覆的話，那1G的空間也基本上是不夠用的。 想要實現這個功能，可以藉助點陣圖。 使用點陣圖的話， ...
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 實戰項目：
什麼是布隆過濾器，實現原理是什麼？
布隆過濾器是一種數據結構，用於快速檢索一個元素是否可能存在於一個集合(bit 數組)中。
它的基本原理是利用多個哈希函數，將一個元素映射成多個位，然後將這些位設置為 1。當查詢一個元素時，如果這些位都被設置為 1，則認為元素可能存在於集合中，否則肯定不存在
所以，布隆過濾器可以準確的判斷一個元素是否一定不存在，但是因為哈希衝突的存在，所以他沒辦法判斷一個元素一定存在。只能判斷可能存在。
所以，布隆過濾器是存在誤判的可能的，也就是當一個不存在的Hero元素，經過hash1、hash2和hash3之後，剛好和其他的值的哈希結果衝突了。那麼就會被誤判為存在，但是其實他並不存在。
想要降低這種誤判的概率，主要的辦法就是降低哈希衝突的概率及引入更多的哈希演算法。
下麵是布隆過濾器的工作過程：
1、初始化布隆過濾器
在初始化布隆過濾器時，需要指定集合的大小和誤判率。布隆過濾器內部包含一個bit數組和多個哈希函數，每個哈希函數都會生成一個索引值。
2、添加元素到布隆過濾器
要將一個元素添加到布隆過濾器中，首先需要將該元素通過多個哈希函數生成多個索引值，然後將這些索引值對應的位設置為 1。如果這些索引值已經被設置為 1，則不需要再次設置。
3、查詢元素是否存在於布隆過濾器中
要查詢一個元素是否存在於布隆過濾器中，需要將該元素通過多個哈希函數生成多個索引值，並判斷這些索引值對應的位是否都被設置為 1。如果這些位都被設置為 1，則認為元素可能存在於集合中，否則肯定不存在。
布隆過濾器的主要優點是可以快速判斷一個元素是否屬於某個集合，並且可以在空間和時間上實現較高的效率。但是，它也存在一些缺點，例如：
- 布隆過濾器在判斷元素是否存在時，有一定的誤判率。、
- 布隆過濾器刪除元素比較困難，因為刪除一個元素需要將其對應的多個位設置為 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最新版)
4.別再寫滿屏的爆爆爆炸類了，試試裝飾器模式，這才是優雅的方式！！
覺得不錯，別忘了隨手點贊+轉發哦！
