面試官：如何實現10億數據判重？
當數據量比較大時，使用常規的方式來判重就不行了。
例如，使用 MySQL 數據庫判重，或使用 List.contains() 或 Set.contains() 判重就不可行，因為 MySQL 在數據量大時查詢就會非常慢，而數據庫又是及其珍貴的全局數據庫資源。
《阿里巴巴Java開發手冊》上也說了，如果單表數據量超過 500 萬或 2GB 時就建議分庫分表了，如下圖所示：
圖片
所以數據庫去重顯然是不行的。而使用集合也是不合適的，因為數據量太大，使用集合會導致內存不夠用或內存溢出和 Full GC 頻繁等問題，所以此時我們的解決方案通常是采用布隆過濾器來實現判重，布隆過濾器的詳情請訪問：如何實現布隆過濾器？
知識擴展
除了布隆過濾器之外，我們還可以使用 BitMap（位圖）的數據類型來實現判重。
位圖（BitMap）是一種數據結構，用于表示一個特定范圍內的元素是否存在或者某種狀態，通常用二進制位來表示。在位圖中，每一個位只能是 0 或 1，分別表示元素不存在或存在。位圖通常用一個 bit 數組來實現，每個 bit 位對應一個元素，如下圖所示：
圖片
其中，上圖中的 1 表示有值，上面 BitMap 描述的值是 1,3,5。
BitMap 優點分析
位圖的優勢包括：
- 空間效率優勢：位圖極大地節省了存儲空間。對于大量稀疏數據，特別是當元素數量遠大于實際存在的項時，相比于使用傳統的列表、集合等數據結構，位圖占用的空間極小。
- 查詢速度：由于內存訪問是按字節或字進行的，因此對單個元素的存在性檢查時間復雜度為 O(1)，即常量時間，非常快速。
- 批量操作高效：對于批量插入、刪除和查詢操作，尤其是統計某一范圍內元素的數量，位圖表現出優秀的性能。
BitMap VS int
以 Java 中的 int 為例，來對比觀察 BitMap 的優勢，在 Java 中，int 類型通常需要 32 位（4 字節*8），而 BitMap 使用 1 位就可以來標識此元素是否存在，所以可以認為 BitMap 占用的空間大小，只有 int 類型的 1/32，所以有大數據量判重時，使用 BitMap 也可以實現。
PS：布隆過濾器的底層就是基于 BitMap 數據結構實現的。
BitMap 在 Java 中的使用
BitMap 在 Java 中的具體實現是 java.util 中的 BitSet，BitSet 是一個可變大小的位向量，能夠動態增長以容納更多的位數據，以下是 BitSet 基本使用示例：
import java.util.BitSet;
public class BitmapExample {
public static void main(String[] args) {
// 創建一個BitSet實例
BitSet bitmap = new BitSet();
// 設置第5個位置為1，表示第5個元素存在
bitmap.set(5);
// 檢查第5個位置是否已設置
boolean exists = bitmap.get(5);
System.out.println("Element at position 5 exists: " + exists); // 輸出: Element at position 5 exists: true
// 設置從索引10到20的所有位置為1
bitmap.set(10, 21); // 參數是包含起始點和不包含終點的區間
// 計算bitset中所有值為1的位的數量，相當于計算設置了的元素個數
int count = bitmap.cardinality();
System.out.println("Number of set bits: " + count);
// 清除第5個位置
bitmap.clear(5);
// 判斷位圖是否為空
boolean isEmpty = bitmap.isEmpty();
System.out.println("Is the bitset empty after clearing some bits? " + isEmpty);
}
}
