算法改进项目中生成会议号问题或者类似黑名单问题

这次主要是把现实中项目的真实案例拿出来，使用算法改进其中的有缺陷的部分。

项目中功能背景和代码

之前看过同事写了一个生成会议号问题的代码，情况是这样的，会议号有个固定范围比如10位数，随机生成一个号码，这个号码如果已经存在，就再生成，直到生成的号码不存在为止。这里伪代码大概是这样的

boolean flag = false;
do {
  long random = new Random().nextInt(1000000000);
  flag = redis.checkExistsNumber(random);//匹配redis是否存在这个号码
} while(flag)

像这样的代码，while循环多少次才能得到结果。

改进算法：

于是有了下面的改进算法：
算法思路是这样的，假如：
100个数字，其中3,5,23,24,35这些是已经用过的数字，现在随机获取一个数字。
1,2,99,4,98...95 从左往右，碰到一个已经存在的数字的时候，就从末尾取一个数字出来填到这个存在的位置，这样随机数范围1-95，如果随机出3就返回99，这样一次随机就可以得到结果。

    public static void main(String[] args) {

        NumberUtil blacklist = new NumberUtil();
//        int[] arr = new int[]{3,5,23,24,35};
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(arr.length);
        }
        log.debug("arr={}", arr);
        for (int i = 0; i < 1000; i++) {
            long s = System.currentTimeMillis();
            blacklist.build(1000000000, arr);
            Integer integer = blacklist.genNumber();
            long e = System.currentTimeMillis();
            log.debug("time={}  value={}", e-s, integer);
        }
    }


public class NumberUtil {
        private int max;
        private Map<Integer, Integer> map = new HashMap<>();

        public void build(int n, int[] blacklist) {
            Arrays.sort(blacklist);
            int m = blacklist.length;
            for (int i = 0; i < m && blacklist[i]<n; i++) {
                for (n--; n > blacklist[i]; n--) {
                    if (n==blacklist[m-1]) {
                        m--;
                    } else {
                        map.put(blacklist[i], n);
                        break;
                    }
                }
            }
            max = n;
        }

        public Integer genNumber() {
            Integer random = new Random().nextInt(max);
            log.debug("random={}", random);
            return map.containsKey(random)?map.get(random):random;
        }
    }