1、問題
問題提出：
M（如10億）個(gè)int整數(shù)，只有其中N個(gè)數(shù)重復(fù)出現(xiàn)過，讀取到內(nèi)存中并將重復(fù)的整數(shù)刪除。
2、解決方案
問題分析：
我們肯定會(huì)先想到在計(jì)算機(jī)內(nèi)存中開辟M(fèi)個(gè)int整型數(shù)據(jù)數(shù)組，來one bye one讀取M個(gè)int類型數(shù)組， 然后在一一比對(duì)數(shù)值，最后將重復(fù)數(shù)據(jù)的去掉。當(dāng)然這在處理小規(guī)模數(shù)據(jù)是可行的。
我們考慮大數(shù)據(jù)的情況：例如在java語言下，對(duì)10億個(gè)int類型數(shù)據(jù)排重。
java中一個(gè)int類型在內(nèi)存中占4byte。那么10億個(gè)int類型數(shù)據(jù)共需要開辟10^9次方*4byte≈4GB的連續(xù)內(nèi)存空間。以32位操作系統(tǒng)電腦為例，最大支持內(nèi)存為4G，可用內(nèi)存更是小于4G。所以上述方法在處理大數(shù)據(jù)時(shí)根本行不通。
思維轉(zhuǎn)化：
既然我們不能為所有 int 類型的數(shù)據(jù)開辟 int 類型數(shù)組，那么可以采取更小的數(shù)據(jù)類型來讀取緩存 int 類型數(shù)據(jù)。考慮到計(jì)算機(jī)內(nèi)部處理的數(shù)據(jù)都是 01 序列的bit，那么我們是否可以用 1bit 來表示一個(gè) int 類型數(shù)據(jù)。
位映射的引出：
使用較小的數(shù)據(jù)類型指代較大的數(shù)據(jù)類型。如上所說的問題，我們可以用1個(gè) bit 來對(duì)應(yīng)一個(gè)int 整數(shù)。假如對(duì)應(yīng)的 int 類型的數(shù)據(jù)存在，就將其對(duì)應(yīng)的 bit 賦值為1，否則，賦值為0（boolean類型）。java中 int 范圍為 -2^31 到 2^31-1. 那么所有可能的數(shù)值組成的長度為2^32. 對(duì)應(yīng)的 bit 長度也為 2^32. 那么可以用這樣處理之后只需要開辟2^32 bit = 2^29 byte = 512M 大小的 內(nèi)存空間 。顯然，這樣處理就能滿足要求了，雖然對(duì)內(nèi)存的消耗也不太小。
問題解決方案：
首先定義如下圖的int - byte 映射關(guān)系，當(dāng)然，映射關(guān)系可以自定義。但前提要保證你的數(shù)組上下標(biāo)不能越界。
但如上定義的bit[]數(shù)組顯然在計(jì)算機(jī)中是不存在的，所我們需要將其轉(zhuǎn)化為 java 中的一個(gè)基本數(shù)據(jù)類型存儲(chǔ)。顯然，byte[] 是最好的選擇。
將其轉(zhuǎn)化為byte[] 數(shù)組方案：
自定義的映射關(guān)系表，每個(gè)bit對(duì)應(yīng)一個(gè) int 數(shù)值，將 int 的最大值，最小值與數(shù)組的最大最小索引相對(duì)應(yīng)。從上圖可以看出來?int 數(shù)值與bit索引相差 2^31次方。當(dāng)然，你也可以定義其他的映射關(guān)系，只是注意不要發(fā)生數(shù)組越界的情況。
bit[]索引：由于最大值可能是2^32,故用long接收:long?bitIndex = num + (1l << 31);
byte[]索引:?int?index = (int) (bitIndex / 8);?，在字節(jié)byte[index]中的具體位置：?int?innerIndex = (int) (bitIndex % 8);
更新值：dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));
import java.util.Random;
/**
* 問題：M（如10億）個(gè)int整數(shù)，只有其中N個(gè)數(shù)重復(fù)出現(xiàn)過，讀取到內(nèi)存中并將重復(fù)的整數(shù)刪除。<br/>
* 使用位映射來進(jìn)行海量數(shù)據(jù)的去重排序，原先一個(gè)元素用一個(gè)int現(xiàn)在只用一個(gè)bit， 內(nèi)存占比4*8bit:1bit=32:1<br/>
* 亦可用java語言提供的BitSet，不過其指定bit index的參數(shù)為int類型，因此在此例中將輸入數(shù)轉(zhuǎn)為bit index時(shí)對(duì)于較大的數(shù)會(huì)越界<br><br/>
*/
public class BigDataSort {
? ? private static final int CAPACITY = 1_000_000;// 數(shù)據(jù)容量
? ? 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個(gè)數(shù): " + num);
? ? ? ? ? ? bytes = ms.setBit(num);
? ? ? ? }
? ? ? ? long endTime = System.currentTimeMillis();
? ? ? ? System.out.printf("存入%d個(gè)數(shù)，用時(shí)%dms\n", CAPACITY, endTime - startTime);
? ? ? ? startTime = System.currentTimeMillis();
? ? ? ? ms.output(bytes);
? ? ? ? endTime = System.currentTimeMillis();
? ? ? ? System.out.printf("取出%d個(gè)數(shù)，用時(shí)%dms\n", CAPACITY, endTime - startTime);
? ? }
}
class MyFullBitMap {
? ? // 定義一個(gè)byte數(shù)組表示所有的int數(shù)據(jù)，一bit對(duì)應(yīng)一個(gè)，共2^32b=2^29B=512MB
? ? private byte[] dataBytes = new byte[1 << 29];
? ? /**
? ? * 讀取數(shù)據(jù)，并將對(duì)應(yīng)數(shù)數(shù)據(jù)的 到對(duì)應(yīng)的bit中，并返回byte數(shù)組
? ? *
? ? * @param num
? ? *? ? ? ? ? ? 讀取的數(shù)據(jù)
? ? * @return byte數(shù)組 dataBytes
? ? */
? ? public byte[] setBit(int num) {
? ? ? ? long bitIndex = num + (1l << 31); // 獲取num數(shù)據(jù)對(duì)應(yīng)bit數(shù)組（虛擬）的索引
? ? ? ? int index = (int) (bitIndex / 8); // bit數(shù)組（虛擬）在byte數(shù)組中的索引
? ? ? ? int innerIndex = (int) (bitIndex % 8); // bitIndex 在byte[]數(shù)組索引index 中的具體位置
? ? ? ? // System.out.println("byte[" + index + "] 中的索引：" + innerIndex);
? ? ? ? dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));
? ? ? ? return dataBytes;
? ? }
? ? /**
? ? * 輸出數(shù)組中的數(shù)據(jù)
? ? *
? ? * @param bytes
? ? *? ? ? ? ? ? byte數(shù)組
? ? */
? ? 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個(gè)數(shù): " + number);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
原文地址：https://www.cnblogs.com/z-sm/p/6238977.html
