在海量数据中查找重复出现的元素或者去除重复元素是经常遇到的大数据领域问题，针对此类问题，可以采用位图法来实现。例如，已知某文件中包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

    本题最好的解决方案是通过使用位图法来实现，8位整数可以表示的最大十进制数值为99999999，如果每个数字对应于位图中的一个bit位,那么存储八位整数大约需要99Mbit，因为1Byte = 8bit，所以99Mbit折合成内存为99/8=12.375MB的内存，即可以只用12.375MB的内存表示所有8位数电话号码的内容。

public class Test {
    int ARRNUM = 100;
    int mmin = 10000000;
    int mmax = 99999999;
    int N = (mmax - mmin + 1);
    int BITS_PER_WORD = 32;
    int WORD_OFFSET(int b){
        return b/BITS_PER_WORD;
    }

    int BIT_OFFSET(int b){
        return b % BITS_PER_WORD;
    }

    void SetBit(int[]words,int n){
        n -=  mmin;
        words[WORD_OFFSET(n)]  |= (1 << BIT_OFFSET(n));
    }

    void ClearBit(int[]words ,int n){
        words[WORD_OFFSET(n)]&=~(1 << BIT_OFFSET(n));
    }
    boolean GetBit(int[]words,int n){
        int bit = words[WORD_OFFSET(n)]&(1 >>BIT_OFFSET(n));
        return bit != 0;
    }
    public void sort(){
        int i;
        int j;
        int arr[] = new int[ARRNUM];
        System.out.println("数组大小:"+ARRNUM);
        //用来存放位图,每一位对应mmin和mmax范围内的一个数
        int[]words = new int[1 + N/BITS_PER_WORD];
        int count = 0;
        Random r = new Random();
        //生成100个随机数存放在数组arr中
        for (j=0;j<ARRNUM;j++){
            arr[j] = r.nextInt(N);
            arr[j] += mmin;
            System.out.print(arr[j] + "  ");
        }
        System.out.println();
        for (j=0;j<ARRNUM;j++){
            SetBit(words,arr[j]);
        }
        System.out.println("排序后的a为:" );
        for (i=0;i<N;i++){
            if(GetBit(words,i)){
                System.out.print(i + mmin+"   ");
                count++;
            }
        }
        System.out.println();
        System.out.println("总个数为:"+count);
    }

    public static void main(String[] args){
        new number().sort();
    }
}

上例中，采用时间作为种子，产生了100个随机数,对这100个数进行位图法排序,进而找出其中重复的数据。与此问题相似的还有： 

1>10亿个整数，只有一个整数重复出现过，要求在O(n)的时间里找出这个数。

2>给定a,b两个文件，各存放50亿个url，每个url各占用64Byte，要求在O(n)的时间里找出a,b两个文件共同的url。

3>给40亿个不重复的unsigned int的整数（没排过序的），然后再给一个整数。如何快速判断这个数是否在那40亿个数当中。

---