騰訊二面：有 40 億個 QQ 號，限制 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 實戰專案：

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

什么是布隆過濾器，實作原理是什么？

布隆過濾器是一種資料結構，用于快速檢索一個元素是否可能存在于一個集合(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最新版)

2.勁爆！Java 協程要來了，，，

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

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

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

覺得不錯，別忘了隨手點贊+轉發哦！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/553806.html

標籤：Java

上一篇：JavaWeb

下一篇：返回列表