在java中如何實現(xiàn)海量數(shù)據(jù)去重排序bitmap

這篇文章給大家分享的是有關(guān)在java中如何實現(xiàn)海量數(shù)據(jù)去重排序bitmap的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

在海量數(shù)據(jù)中查找出重復(fù)出現(xiàn)的元素或者去除重復(fù)出現(xiàn)的元素是面試中常考的文圖。針對此類問題，可以使用位圖法來解決。例如：已知某個文件內(nèi)包含若干個電話號碼，要求統(tǒng)計不同的號碼的個數(shù)，甚至在O（n）時間復(fù)雜度內(nèi)對這些號碼進行排序。

位圖法需要的空間很少（依賴于數(shù)據(jù)分布，但是我們也可以通過一些放啊發(fā)對數(shù)據(jù)進行處理，使得數(shù)據(jù)變得密集），在數(shù)據(jù)比較密集的時候效率非常高。例如：8位整數(shù)可以表示的最大十進制數(shù)值為99999999，如果每個數(shù)組對應(yīng)于一個bit位，那么把所有的八進制整數(shù)存儲起來只需要：99Mbit = 12.375MB.

實際上，java jdk1.0已經(jīng)提供了bitmap的實現(xiàn)BitSet類，不過其中的某些方法是jdk1.4之后才有的。

下面我先自己實現(xiàn)一下bitmap 的原理，然后再直接調(diào)用jdk的BitSet類分別實現(xiàn)bitmap, 方便比較理解：

package swordoffer;
//去除重復(fù)并排序
import java.util.Arrays;
import java.util.BitSet;
import java.util.Random;
/**
 * @author Gavenyeah
 * @date Time:
 * @des:
 */
public class BitMap {
  int ARRNUM = 800;
  int LEN_INT = 32;
  int mmax = 9999;
  int mmin = 1000;
  int N = mmax - mmin + 1;
  public static void main(String args[]) {
     new BitMap().findDuplicate();
    new BitMap().findDup_jdk();
  }
  public void findDup_jdk() {
    System.out.println("*******調(diào)用JDK中的庫方法--開始********");
    BitSet bitArray = new BitSet(N);
    int[] array = getArray(ARRNUM);
    for (int i = 0; i < ARRNUM; i++) {
      bitArray.set(array[i] - mmin);
    }
    int count = 0;
    for (int j = 0; j < bitArray.length(); j++) {
      if (bitArray.get(j)) {
        System.out.print(j + mmin + " ");
        count++;
      }
    }
    System.out.println();
    System.out.println("排序后的數(shù)組大小為：" + count );
    System.out.println("*******調(diào)用JDK中的庫方法--結(jié)束********");
  }
  public void findDuplicate() {
    int[] array = getArray(ARRNUM);
    int[] bitArray = setBit(array);
    printBitArray(bitArray);
  }
  public void printBitArray(int[] bitArray) {
    int count = 0;
    for (int i = 0; i < N; i++) {
      if (getBit(bitArray, i) != 0) {
        count++;
        System.out.print(i + mmin + "\t");
      }
    }
    System.out.println();
    System.out.println("去重排序后的數(shù)組大小為：" + count);
  }
  public int getBit(int[] bitArray, int k) {// 1右移 k % 32位 與上 數(shù)組下標(biāo)為 k/32 位置的值
    return bitArray[k / LEN_INT] & (1 << (k % LEN_INT));
  }
  public int[] setBit(int[] array) {// 首先取得數(shù)組位置下標(biāo) i/32, 然后 或上
                    // 在該位置int類型數(shù)值的bit位：i % 32
    int m = array.length;
    int bit_arr_len = N / LEN_INT + 1;
    int[] bitArray = new int[bit_arr_len];
    for (int i = 0; i < m; i++) {
      int num = array[i] - mmin;
      bitArray[num / LEN_INT] |= (1 << (num % LEN_INT));
    }
    return bitArray;
  }
  public int[] getArray(int ARRNUM) {
    @SuppressWarnings("unused")
    int array1[] = { 1000, 1002, 1032, 1033, 6543, 9999, 1033, 1000 };
    int array[] = new int[ARRNUM];
    System.out.println("數(shù)組大?。?quot; + ARRNUM);
    Random r = new Random();
    for (int i = 0; i < ARRNUM; i++) {
      array[i] = r.nextInt(N) + mmin;
    }
    System.out.println(Arrays.toString(array));
    return array;
  }
}

感謝各位的閱讀！關(guān)于“在java中如何實現(xiàn)海量數(shù)據(jù)去重排序bitmap”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！