使用BitMap怎么實現大數據排序去重

今天就跟大家聊聊有關使用BitMap怎么實現大數據排序去重，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

1、問題 問題提出：

M（如10億）個int整數，只有其中N個數重復出現過，讀取到內存中并將重復的整數刪除。

2、解決方案 問題分析：

我們肯定會先想到在計算機內存中開辟M個int整型數據數組，來one bye one讀取M個int類型數組， 然后在一一比對數值，最后將重復數據的去掉。當然這在處理小規模數據是可行的。

我們考慮大數據的情況：例如在java語言下，對10億個int類型數據排重。

java中一個int類型在內存中占4byte。那么10億個int類型數據共需要開辟10^9次方*4byte≈4GB的連續內存空間。以32位操作系統電腦為例，最大支持內存為4G，可用內存更是小于4G。所以上述方法在處理大數據時根本行不通。

思維轉化：

既然我們不能為所有 int 類型的數據開辟 int 類型數組，那么可以采取更小的數據類型來讀取緩存 int 類型數據。考慮到計算機內部處理的數據都是 01 序列的bit，那么我們是否可以用 1bit 來表示一個 int 類型數據。

位映射的引出：

使用較小的數據類型指代較大的數據類型。如上所說的問題，我們可以用1個 bit 來對應一個int 整數。假如對應的 int 類型的數據存在，就將其對應的 bit 賦值為1，否則，賦值為0（boolean類型）。java中 int 范圍為 -2^31 到 2^31-1. 那么所有可能的數值組成的長度為2^32. 對應的 bit 長度也為 2^32. 那么可以用這樣處理之后只需要開辟2^32 bit = 2^29 byte = 512M 大小的 內存空間 。顯然，這樣處理就能滿足要求了，雖然對內存的消耗也不太小。

問題解決方案：

首先定義如下圖的int - byte 映射關系，當然，映射關系可以自定義。但前提要保證你的數組上下標不能越界。

但如上定義的bit[]數組顯然在計算機中是不存在的，所我們需要將其轉化為 java 中的一個基本數據類型存儲。顯然，byte[] 是最好的選擇。

將其轉化為byte[] 數組方案：

自定義的映射關系表，每個bit對應一個 int 數值，將 int 的最大值，最小值與數組的最大最小索引相對應。從上圖可以看出來 int 數值與bit索引相差 2^31次方。當然，你也可以定義其他的映射關系，只是注意不要發生數組越界的情況。

bit[]索引：由于最大值可能是2^32,故用long接收: long bitIndex = num + (1l << 31);

byte[]索引: int index = (int) (bitIndex / 8); ，在字節byte[index]中的具體位置： int innerIndex = (int) (bitIndex % 8);

更新值： dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));

` import java.util.Random;

/**

• 問題：M（如10億）個int整數，只有其中N個數重復出現過，讀取到內存中并將重復的整數刪除。<br/>

• 使用位映射來進行海量數據的去重排序，原先一個元素用一個int現在只用一個bit， 內存占比4*8bit:1bit=32:1<br/>

• 亦可用java語言提供的BitSet，不過其指定bit index的參數為int類型，因此在此例中將輸入數轉為bit index時對于較大的數會越界<br><br/> */ public class BigDataSort {

  private static final int CAPACITY = 1_000_000;// 數據容量

  public static void main(String[] args) {

   testMyFullBitMap();

  
  

  }

  public static void testMyFullBitMap() { MyFullBitMap ms = new MyFullBitMap();

   byte[] bytes = null;
  
   Random random = new Random();
   long startTime = System.currentTimeMillis();
   for (int i = 0; i < CAPACITY; i++) {
       int num = random.nextInt();
       // System.out.println("讀取了第 " + (i + 1) + "\t個數: " + num);
       bytes = ms.setBit(num);
   }
   long endTime = System.currentTimeMillis();
   System.out.printf("存入%d個數，用時%dms\n", CAPACITY, endTime - startTime);
  
   startTime = System.currentTimeMillis();
   ms.output(bytes);
   endTime = System.currentTimeMillis();
   System.out.printf("取出%d個數，用時%dms\n", CAPACITY, endTime - startTime);

  
  

  } }

class MyFullBitMap { // 定義一個byte數組表示所有的int數據，一bit對應一個，共2^32b=2^29B=512MB private byte[] dataBytes = new byte[1 << 29];

/**
 * 讀取數據，并將對應數數據的 到對應的bit中，并返回byte數組
 * 
 * [@param](https://my.oschina.net/u/2303379) num
 *            讀取的數據
 * [@return](https://my.oschina.net/u/556800) byte數組 dataBytes
 */
public byte[] setBit(int num) {

    long bitIndex = num + (1l << 31); // 獲取num數據對應bit數組（虛擬）的索引
    int index = (int) (bitIndex / 8); // bit數組（虛擬）在byte數組中的索引
    int innerIndex = (int) (bitIndex % 8); // bitIndex 在byte[]數組索引index 中的具體位置

    // System.out.println("byte[" + index + "] 中的索引：" + innerIndex);

    dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));
    return dataBytes;
}

/**
 * 輸出數組中的數據
 * 
 * [@param](https://my.oschina.net/u/2303379) bytes
 *            byte數組
 */
public void output(byte[] bytes) {
    int count = 0;
    for (int i = 0; i < bytes.length; i++) {
        for (int j = 0; j < 8; j++) {
            if (((bytes[i]) & (1 << j)) != 0) {
                count++;
                int number = (int) ((((long) i * 8 + j) - (1l << 31)));
                // System.out.println("取出的第 " + count + "\t個數: " + number);
            }
        }
    }
}

}`

3. Bit-map應用之快速去重 　　2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。 　　首先，根據“內存空間不足以容納這2.5億個整數”我們可以快速的聯想到Bit-map。下邊關鍵的問題就是怎么設計我們的Bit-map來表示這2.5億個數字的狀態了。其實這個問題很簡單，一個數字的狀態只有三種，分別為不存在，只有一個，有重復。因此，我們只需要2bits就可以對一個數字的狀態進行存儲了，假設我們設定一個數字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲空間幾十兆左右。 　　接下來的任務就是遍歷一次這2.5億個數字，如果對應的狀態位為00，則將其變為01；如果對應的狀態位為01，則將其變為11；如果為11，,對應的轉態位保持不變。 　　最后，我們將狀態位為01的進行統計，就得到了不重復的數字個數，時間復雜度為O(n)。 轉自：https://www.cnblogs.com/yale/p/9307363.html

看完上述內容，你們對使用BitMap怎么實現大數據排序去重有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。