先說一下大前提

所有的判重題目一定要有一個大前提，數(shù)據(jù)是什么類型的？

如果是字符串，快速高效判重的方式都是模糊判重。想要精確判重需要記住分而治之的方式。

如果是數(shù)字，使用Roaring Bitmap可以實現(xiàn)精確判重。

一般的Roaring Bitmap是基于32位數(shù)字實現(xiàn)的，還有64位的升級版，邏輯相似。

如果對Roaring Bitmap算法不了解的，可以看下什么是Roaring Bitmap？。

直接上代碼

我們先引入依賴：

<dependency>
    <groupId>org.roaringbitmap</groupId>
    <artifactId>RoaringBitmap</artifactId>
    <version>1.3.0</version>
</dependency>

我們這里就先使用數(shù)字實現(xiàn)了：

final RoaringBitmap a = new RoaringBitmap();
final RoaringBitmap b = new RoaringBitmap();
final Random random = new Random(Integer.MAX_VALUE);

final int nums = 1_000_000_000;
for (int i = 0; i < nums; i++) {
    a.add(random.nextInt());
    b.add(random.nextInt());
}

final RoaringBitmap intersection = RoaringBitmap.and(a, b);
System.out.println("重復(fù)數(shù)量：" + intersection.getLongCardinality());

我們使用sdk中的RoaringBitmap類創(chuàng)建Roaring Bitmap對象，然后循環(huán)向其中加入int類型數(shù)字。

然后借助RoaringBitmap.and計算交集，交集就是重復(fù)數(shù)據(jù)。

代碼是不是很簡單。

有時候，我們站在前人的肩膀上，就可以快速實現(xiàn)一些高效的邏輯。

如果數(shù)據(jù)是字符串呢？

前面提到，如果基礎(chǔ)數(shù)據(jù)是字符串，比如url鏈接判重，上面的邏輯就只能是模糊判重了。

但是如何實現(xiàn)呢？

其實邏輯和布隆過濾器類似，借助離散hash算法，將字符串轉(zhuǎn)換為數(shù)字，然后再將數(shù)字放入到Roaring Bitmap中。

因為這種方式一定會有hash碰撞，所以結(jié)果是模糊判重。

但是在實際場景中，我們其實是可以避免出現(xiàn)字符串判重情況的。

比如，我們想要判斷兩個人看的視頻或者文章的重復(fù)內(nèi)容時，我們可以記錄視頻或文章的ID。一般來說，為了更好的DB查找，ID我們會設(shè)置成數(shù)字。

這個時候，字符串的場景直接轉(zhuǎn)變?yōu)閿?shù)字場景了。

所以說，有的時候，路就在那，有石頭堵住了前路，就迂回過去。

“曲成萬物而不遺。”這世間萬物，向來都是迂回曲折、無往不復(fù)的。水能直至大海，就是因為它巧妙地避開了各種障礙，不斷拐彎前行；人能走向成功，就是因為能夠靈活變通，及時拐彎調(diào)頭。

曲成萬物而不遺

文末總結(jié)

本文借助Roaring Bitmap實現(xiàn)10億數(shù)據(jù)的精確判重。

假設(shè)我們需要對10億URL精確判重如何實現(xiàn)呢？我們下回接著聊。