在这样的一个场景下,租户的信息下面有很多子租户,租户的标示一般会关联一个手机号码或者唯一标识,如何校验这个手机号码或者唯一标识就摆在我们的眼前。
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;
}
}
All comments