基站扫描过滤非法终端算法

项目中的基站开启了蓝牙扫描，由于蓝牙所在的2.4G频段是公用频段，因此会把周围所有能发蓝牙信号的设备如手机、蓝牙耳机、beacon等设备都扫描到，如果在基站中不过过滤的话会把大量的非法终端都扫描并上报给平台，虽然平台可以进行过滤，但上报大量非法终端对基站计算能力、内存、带宽和平台资源都是一个极大的浪费，因此需要在基站端就能进行过滤的一个算法。有如下几种方式实现：

1. 黑白名单，平台维护黑白名单并下发到基站，这样基站能做到100%准确过滤，缺点就是黑白名单如果很大，需要占用基站一部分内存，这对小内存基站来说不可接受。
2. 上面方法的变种，即下发名单指纹，如布隆过滤器，可以大量减少内存占用，同时拦截率很高，不过需要多计算hash函数。布隆过滤器参考：https://blog.csdn.net/u010793917/article/details/103167407
3. hash+位图，这种方法误判率不如布隆过滤器，但是内置占用更少且只需要计算一次hash

以5000个终端为例，采用第一种方式需要占用12B*5K=60KB内存；第二种方式根据参考文章中的算法，假设误判率为10%，需要内存3KB，每次计算hash函数4次；采用第三种方式每次计算hash函数1次，但是误判率为却高，如果误判率定20%那么需要2.5KB内存，误判率定10%需要5KB内存。根据项目需要，使用第三种方案更符合需要。
下面是第三种方案实现代码

 @Test
    public void test10() {
        //3k个真实设备，在100w环境中，误判率22%，占用内存1.5kB;
        // 5k个设备，在10w环境中，误判率21%，占用内存2.5kB
        int count = 5000;
        int capacity = count << 2; //让位图更稀疏
        Map<String, Integer> map = new HashMap<>(capacity);
        while (true) {
            String mac = this.randomMac();
            if (!map.containsKey(mac)) {
                map.put(mac, 1);
            }
            if (map.size() >= count) {
                break;
            }
        }

        BitSet bitSet = new BitSet();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            bitSet.set(Math.abs(entry.getKey().hashCode()) % capacity);
        }
        System.out.println(bitSet.toString());

        int testCount = 1000000;
        while (true) {
            if (map.size() >= testCount) {
                break;
            }
            String mac = this.randomMac();
            map.put(mac, 1);
        }

        int found = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (bitSet.get(Math.abs(entry.getKey().hashCode()) % capacity)) {
                found++;
            }
        }
        System.out.println("误判数" + (found - count));
        //允许通过数减去系统中存在的设备即为误判允许通过数，testCount - count即为全部非法设备数
        System.out.println("误判率：" + ((found - count) * 100d / (testCount - count)));
    }

    private String randomMac() {
        return RandomStringUtils.random(12, "1234567890ABCDEF");
    }

误判数221001
误判率：22.211155778894472

可以看到这种方法对基站来说内存和cpu压力都不大，且20%的误判对于平台端也是可以接受的。