本文共 3544 字,大约阅读时间需要 11 分钟。
bitmap是很有用的结构。所谓的bitmap就是用一个bit位来标记某个元素,而数组下标是该元素。
bitmap经常用在大数据的题中,比如10亿个int类型的数,如果用int数组存储的话,那么需要大约4G内存,浪费内存。如果用bitmap解决,就比较方便。bitmap可以用int来模拟,也可以用byte来模拟,它只是逻辑上的概念,在java语言中写不出来,我们采用byte。一个byte占8个bit,如果每一个bit的值是有或者没有,即1或0,则如下图所示:
第一步:构建特定长度的byte数组(new byte[capacity/8 + 1]),其中capacity为整数数组长度(如:10亿个数字等)
byte[] bits = new byte[getIndex(n) + 1];
第二步:计算数字num在byte[]中的位置(num/8和num >> 3一样),也就是说num在byte[k],算这个k是几
/** * num/8得到byte[]的index * @param num * @return */ public int getIndex(int num){ return num >> 3; }
第三步:计算数字num在byte[index]中的位置,就是在byte[index]的第几位,每个byte有8位(num % 8)
/** * num%8得到在byte[index]的位置 * @param num * @return */ public int getPosition(int num){ return num & 0x07; }
第四步:将所在位置从0变成1,其它位置不变
/** * 标记指定数字(num)在bitmap中的值,标记其已经出现过 * 将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了 * @param bits * @param num */ public void add(byte[] bits, int num){ bits[getIndex(num)] |= 1 << getPosition(num); }
解释如下图:
第五步:判断指定数字num是否存在
/** * 判断指定数字num是否存在 * 将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可 * @param bits * @param num * @return */ public boolean contains(byte[] bits, int num){ return (bits[getIndex(num)] & 1 << getPosition(num)) != 0; }
第六步:重置某一数字对应在bitmap中的值
/** * 重置某一数字对应在bitmap中的值 * 对1进行左移,然后取反,最后与byte[index]作与操作。 * @param bits * @param num */ public void clear(byte[] bits, int num){ bits[getIndex(num)] &= ~(1 << getPosition(num)); }
全部代码如下:
public class Test { /** * 创建bitmap数组 */ public byte[] create(int n){ byte[] bits = new byte[getIndex(n) + 1]; for(int i = 0; i < n; i++){ add(bits, i); } System.out.println(contains(bits, 11)); int index = 1; for(byte bit : bits){ System.out.println("-------" + index++ + "-------"); showByte(bit); } return bits; } /** * 标记指定数字(num)在bitmap中的值,标记其已经出现过 * 将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了 * @param bits * @param num */ public void add(byte[] bits, int num){ bits[getIndex(num)] |= 1 << getPosition(num); } /** * 判断指定数字num是否存在 * 将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可 * @param bits * @param num * @return */ public boolean contains(byte[] bits, int num){ return (bits[getIndex(num)] & 1 << getPosition(num)) != 0; } /** * num/8得到byte[]的index * @param num * @return */ public int getIndex(int num){ return num >> 3; } /** * num%8得到在byte[index]的位置 * @param num * @return */ public int getPosition(int num){ return num & 0x07; } /** * 重置某一数字对应在bitmap中的值 * 对1进行左移,然后取反,最后与byte[index]作与操作。 * @param bits * @param num */ public void clear(byte[] bits, int num){ bits[getIndex(num)] &= ~(1 << getPosition(num)); } /** * 打印byte类型的变量 * 将byte转换为一个长度为8的byte数组,数组每个值代表bit */ public void showByte(byte b){ byte[] array = new byte[8]; for(int i = 7; i >= 0; i--){ array[i] = (byte)(b & 1); b = (byte)(b >> 1); } for (byte b1 : array) { System.out.print(b1); System.out.print(" "); } System.out.println(); } public static void main(String[] args) { int n = 100; new Test().create(n); }}
转载地址:http://rwlii.baihongyu.com/