最近看到 一个20亿手机号存储检索的问题，这里做一下记录，方便学习
1、场景描述
在20亿个随机整数中找出某个数m是否存在其中，并假设32位操作系统，4G内存。
1byte=8bit 1kb=1024byte 1mb=1024kb 1gb=1024mb java中 int类型占用4个字节=4*8=32bit
如果将20亿个整数放入内存中，需要占用多少内存？
-
如果每个数字都以int类型存储 20亿整数占用内存=20亿*4byte/1024/1024/1024 约等于 7.45G
-
如果使用bit-map的思想，按位存储，即一位就可以代表一个数字 20亿整数占用内存=20亿*1bit/8/1024/1024/1024=约等于0.233G
从上述结果来看，按位存储比按字节存储数字节约了（7.45/0.233-1约等于31倍空间），而且按字节存储根据内存4G的要求无法一次性在内存中进行处理。
2、BitMap算法原理
如何用一位来表示一个数呢？
假如现在有一个字节也就是8位的空间，那么按照BitMap，可以表示8个数字，
按照上图所示，该字节的8位表示了整数数组[6,5,2,0]。那么java中int类型占用了4个字节，也就是32位，那么就可以最多表示32个数字。超过32位数字呢？那就使用两个以上int去表示。
假设我们要存储的数字最大值位N，则申请int temp[1+N/32]的数组空间，其中： temp[0]可表示 0~31 temp[1]可表示 32-63 …..以此类推 给定任一整数M，M数字所在数组中的下标位置就应该是M/32，M数字所在的位就是M%32
添加整数M
总共两步 1.找到整数所在数组temp的下标 int index = M/32 2.将temp[index] 的第M%32位置1
temp[index]=temp[index] | (1<<(M%32))
清除
根据bitMap的原理可知，想要清除掉一个数字，那就是将对应的位置0 总共两步 1.找到整数所在数组temp的下标 int index = M/32 2.将temp[index] 的第M%32位置0 temp[index]=temp[index] &（~ (1<<(M%32))）
查找
根据每一位代表一个数字，1表示存在，0表示不存在，那么只需要判断整数对应位是否位1即可 总共两步 1.找到整数所在数组temp的下标 int index = M/32 2.将temp[index] 的第M%32位置0 temp[index] &(1<<(M%32) ！= 0？”存在”:”不存在”
分桶理论
//电话号 135 2333 3222
BitSet bitSet = new BitSet();
bitSet.set(23333222);
Map<String,BitSet> map = new HashMap();
//当Key存在时,BiFunction一定会被执行
BitSet bitSet135 = map.computeIfAbsent("135", k -> bitSet);
System.out.println(bitSet135.get(23333222));
System.out.println(bitSet135.get(23333221));4、BitMap实现
/**
* 位图类：
* 1.最多可以储存（2^37-2^6）个2种状态值的点;
* 2.理论上有（2^37-2^6）个位空间，实际上可能不能完全使用（见无参构造器中的介绍），
* 故使用时所选的点的状态值种数（stateNum）最好满足 64% ⌈ log2(stateNum) ⌉ = 0，即stateNum的补码的位数正好是64的因数；（听不明白的话，自行体会）
* 3.没有删除点的方法，只有增加，更新，查找操作；（问为什么没有删除方法的人不是脑子有病，就是脑子有病。。。）
* 4.回答3中问题：首先不是实现不了，是没有必要，因为删除一个点需要在数组中通过移位来填充被删除的位置，由于数据量过大可能会极其浪费时间，
* 而且位图本身存在的意义是表示海量数据中每一条数据的可能性，对于海量数据而言，出现极个别错误并不会影响其最终统计结果（对于偷跑，出错的数据仍然可以在下一层中进行重新过滤，要是听不懂就算了。。。），
* 这里建议使用update方法将不需要的点置0，用于表示该点被弃用，具体的逻辑需要使用者自己去编辑；
* 5.该类所花费的理论持久存储空间大约为260MB也就是elementData数组的大小的极限值，实际可能会多一点，但几乎可以忽略不计，最终实现存储2种状态值的点的数量大约20亿个，
* 也可以自定义每个点的状态值种数stateNum和点的数量length最大可以设置成（2^63-1）个，但最终要满足 length > ⌈ log2(stateNum) ⌉（向上取整） / 64 * Integer.MAX_VALUE，
* 对于日常使用一定是足够的；（在这里，总有杠精会问超过了怎么办？就算是2种状态值的点有20亿个话，我还是不够用啊？）
* 6.回答5中的问题：你不会搞个数组吗？你不能多new几个一起用吗！！！
*/
public class Bitmap {
/*
*使用long型数组保存点
*/
private final long[] elementData;
/*
* 位图中能存储的所有点的位数之和的最大值MAX_STATE_SIZE=137,438,953,408；
* 64（MAX_STATE_SIZE=long类型的位数） * 0x7fffffff（int类型的最大值Integer.MAX_VALUE）= MAX_STATE_SIZE （2^37-2^6）
*/
// private static final long MAX_STATE_SIZE = 0x1fffffffc0L;//结果没用上，大意了。。。
/*
位图保存的点的状态种数
*/
private final long stateNum;
/*
存储一个位图保存的点的状态值所需要的位数
*/
private final int stateBitNum;
/*
位图可以储存的最大点数，初始化Bitmap类时指定
*/
private final long MAX_SIZE;
/*
一个long型变量可以保存的点的数量
*/
private final long numOfOneLong;
/*
该位图已经保存的点的数量
*/
private long size;
/**
* @param stateNum 位图中点的状态数量,state>1
* @param length 位图大小,0<length
* 如果 length > ⌈ log2(stateNum) ⌉（向上取整） / 64 * Integer.MAX_VALUE，则说明该 Bitmap 类无法储存 length 个 stateNum 种数的点，抛出异常
*/
public Bitmap(long stateNum, long length) {
if (stateNum > 1 && length > 0) {
/*
计算状态值需要多少位来表示
*/
stateBitNum = 64 - Long.numberOfLeadingZeros(stateNum - 1);
/*
计算一个long型里面最多可以存放几个状态值，
如果不能整除的话，就舍弃余下位数，
因为在数组中跨元素进行位值的存取计算极其复杂，故舍弃部分位空间，方便位图的各项操作
*/
numOfOneLong = 64 / stateBitNum;
/*
一个long型最多可以存储numOfOneLong个状态值，
所以该位图最大能存取numOfOneLong*Integer.MAX_VALUE个点，
如果需要存储的数量length大于位图的最大存储数（numOfOneLong*Integer.MAX_VALUE）就说明该类Bitmap无法满足要求，抛出异常
*/
if (length > numOfOneLong * Integer.MAX_VALUE)
throw new RuntimeException("初始化的位图过大，无法存储！！！");
this.stateNum = stateNum;
MAX_SIZE = length;
if (length % numOfOneLong == 0)
elementData = new long[(int) (length / numOfOneLong)];
/*
如果length个点不能被数组正好放下，就需要多添加一个数组元素来存储点
*/
else elementData = new long[((int) (length / numOfOneLong)) + 1];
} else
throw new RuntimeException("位图类的初始化传入参数值中没有负整数！！！");
}
/**
* 顺序添加点
*
* @param state 点的状态
* @return true表示添加成功，产生false的情况有：位图满了；状态值越界
*/
public boolean add(long state) {
if (state > stateNum - 1 || state < 0 || size == MAX_SIZE)
return false;
int index = (int) (size / numOfOneLong);
int left = (int) (size % numOfOneLong);
elementData[index] |= state << (64 - stateBitNum * (1 + left));
++size;
return true;
}
public long find(long index) {
if (index < 0 || index > size - 1)
return -1;
/*
计算数组中哪一个元素保存着index索引对应的点
*/
int arrayIndex = (int) (index / numOfOneLong);
/*
计算元素中从哪一位开始的位保存着index索引对应的点
*/
int elementIndex = (int) (index % numOfOneLong);
/*
通过左移，清空掉左边无用的位，再通过无符号右移清空掉右边无用的位，最终正好是需要查找的index位置对应的state值
*/
return elementData[arrayIndex] << (stateBitNum * elementIndex) >>> (64 - stateBitNum);
}
public boolean update(long index, long state) {
if (index < 0 || index > size - 1 || state > stateNum - 1 || state < 0)
return false;
int arrayIndex = (int) (index / numOfOneLong);
int left = (int) (index % numOfOneLong);
elementData[arrayIndex] |= state << (64 - stateBitNum * (1 + left));
return true;
}
/**
* 返回位图中点的状态数量
*/
public long getStateNum() {
return stateNum;
}
/**
* 返回位图可以存储的点的最大数量
*/
public long getMaxSize() {
return MAX_SIZE;
}
/**
* 返回位图中实际已使用的数量
*/
public long getSize() {
return size;
}
/**
* 辅助toString()方法，主要用于打印位图的具体显示
*/
private String elementDataToString() {
StringBuilder result = new StringBuilder("[\n");
for (long element : elementData) {
String eleString = Long.toBinaryString(element);
StringBuilder one = new StringBuilder();
for (int i = 0; i < 64 - eleString.length(); i++)
one.append("0");
one.append(eleString);
for (int i = 0; i < numOfOneLong + 1; i++)
one.insert((stateBitNum + 1) * i, ',');
result.append(one.substring(1, one.lastIndexOf(","))).append(",\n");
}
return result.append("]").toString();
}
@Override
public String toString() {
return "Bitmap{\n" +
"elementData=" + elementDataToString() +
", \nstateNum=" + stateNum +
", \nstateBitNum=" + stateBitNum +
", \nMAX_SIZE=" + MAX_SIZE +
", \nsize=" + size +
"\n}";
}
}
没有回复内容