Saas系统用户数据非常多，如何设计一个占用内存小，高效去重的方案？

在这样的一个场景下，租户的信息下面有很多子租户，租户的标示一般会关联一个手机号码或者唯一标识，如何校验这个手机号码或者唯一标识就摆在我们的眼前。

这个时候我们一般会考虑到使用位图。

bitmap 索引具有非常高效的数据结构，可以用于存储大规模数据的位信息。其中每一位对应一个元素，如果当前位为1，则表示该元素存在于集合中，否则表示不存在。如果要表示一个包含 100个元素的数据集，那么我们可以创建一个包含 100 位的位数组。

这个时候有人要问，如果我们要存储手机号码？该如何处理，比如134-5678-0001，难道我们申请10^11位这么长？大家想一想可以这么设计吗？

实际上是可以这么设计的，但是如果数据很大的话，那么占用的空间会很大，我们可以考虑使用分段的策略来完成。

比如我们可以把134-5678-0001分成三段，每一段使用一个位图集，那么我们只需要三个位图集就可以处理该问题了。这样是不是就可以了？

bitmap可以支持插入与查找，但是不能对重复的数据做插入和查找。

插入操作的时候是将对应位置的位从把0 设置为 1，将元素添加到数据集中。查找操作通过检查相应位置的位来确定元素是否存在于数据集中。如果位为 1，表示元素存在；如果为 0，表示元素不存在。

bitmap 非常高效，空间复杂度是O(n)，时间复杂度为O(1)。因为位操作可以直接定位，就像Hashmap算法一样，不受数据集大小的限制。

我们使用java代码来实现它。

在这里我们先阐述几个概念.

long类型是64位，2个Long类型是可以标示2*64=128位，也相当于可以标识1-128这个数字范围。

因为我们使用的是long数组，所以我们是先要定位到时拿一个数组下标，然后再修改这个long的位。比如long[2]，我现在有一个数字是68，那么我需要先定位到是哪个数组下标,数组下标：68/64=1,如何计算修改它的位：68%64=4。所以我们就可以得出如果要插入68的话，要修改数组1下标的第4位。

Java代码来实现：

package com.mgface.platform.core.task;

import java.util.Random;

/**
 * 位图实现
 */
public class BitMap {

    private long[] bits;
    //因为long类型是64位，所以这里我们设置为64
    private int BIT_SIZE = 64;

    //我们暂定每一个对象只存储最大不超过9999，9999/64取值大于128所以设置为256
    public BitMap() {
        bits = new long[256];
    }

    public BitMap(int n) {
        bits = new long[n];
    }


    /**
     * 添加num
     */
    public void add(long num) {
        int index = getIndex(num);
        long position = getPosition(num);
        // 将1左移position位后，position那个位置就是1，
        // 然后数组的index位置做与运算，这样index索引中的position位置就替换成1了
        bits[index] = bits[index] | (1 << position);
    }

    /**
     * 判断指定数字num是否存在
     */
    public boolean contains(int num) {
        int index = getIndex(num);
        long position = getPosition(num);
        // 将1左移position后，position那个位置就是1，然后和以前的数据做与运算，判断是否为0即可
        return (bits[index] & 1 << position) != 0;
    }

    /**
     * 重置num在位图的索引位置
     */
    public void clear(long num) {
        int index = getIndex(num);
        long position = getPosition(num);
        // 对1进行左移position个位置，然后取反，最后与byte[index]进行与操作
        bits[index] &= ~(1 << position);
    }

    /**
     * 得到long[]的下标
     */
    public int getIndex(long num) {
        return (int) num / BIT_SIZE;
    }

    /**
     * 得到num在64bit数组上的分布
     */
    public long getPosition(long num) {
        return num % BIT_SIZE;
    }

    public static void main(String[] args) {
        // 假设有1亿个手机号
        long numberOfPhoneNumbers = 100_000_000L;
        // 存储前3位，3位最大标示为999，取16
        BitMap firstDigitsSet = new BitMap(16);
        // 存储后8位，8位最大标示为9999_9999/64=156_2499我们取2^21
        //这里可以使用2个位图集合，为了方便只使用1个，可以自己替换
        BitMap lastDigitsSet = new BitMap(209_7152);
        long time = System.currentTimeMillis();
        // 模拟手机号数据，将已存在的手机号设置为true
        for (long i = 0; i < numberOfPhoneNumbers; i++) {
            // 手机号
            String phoneNumber = generateRandomPhoneNumber();
            // 提取手机号的前3位和后8位,忽略掉地区编码，如有需要，自己改动
            String firstDigits = phoneNumber.substring(3, 6);
            String lastDigits = phoneNumber.substring(6);
            int firstDigitsIndex = Integer.parseInt(firstDigits);
            int lastDigitsIndex = Integer.parseInt(lastDigits);

            // 检查前3位是否重复
            if (firstDigitsSet.contains(firstDigitsIndex)) {
                // 检查后8位是否重复
                if (lastDigitsSet.contains(lastDigitsIndex)) {
                    // 打印重复的号码
                    System.out.println("重复的号码：" + firstDigits + lastDigits);
                } else {
                    // 不重复则存储号码后8位
                    lastDigitsSet.add(lastDigitsIndex);
                }
            } else {
                firstDigitsSet.add(firstDigitsIndex);
            }
        }

        time = System.currentTimeMillis() - time;
        System.out.println(time);
    }


    /**
     * 随机电话号码生成
     */
    private static String generateRandomPhoneNumber() {
        Random random = new Random();

        // 生成国家或地区代码
        String countryCode = "+86";
        // 随机生成前三位
        String prefix = String.format("%03d", random.nextInt(1000));
        // 随机生成号码4位前缀、4位后缀
        String middle = String.format("%04d", random.nextInt(10000));
        String suffix = String.format("%04d", random.nextInt(10000));
        // 拼接生成的手机号码
        return countryCode + prefix + middle + suffix;
    }
}