赞
踩
Bitmap 又称位图,是redis中的一种数据结构,它的出现对于redis来说具有什么意义,它具有哪些作用,它又是如何使用的?它的实现机制又是什么?下面就让我们来走进bitmap的世界。
什么是bitmap?
在文字说明之前,先来看一张图
这个在二进制里表示数字7 (00000111)2 = (7)10
那么这个在bitmap中表示什么呢?
它在bitmap中表示6,7, 8号位上都为1,也就是说6, 7, 8号位上都有数据。【注意:bitmap低位在左,高位在右】
总结:bitmap 中的每一位都表示数字1,该数组的index即位数据的存放位。例如0010 表示2号位上有数据,0100 表示3号位上有数据,1000 表示4号位上有数据。那么大家可以想象一下,在大量数据需要存储的场景,是不是用bitmap比string更方便、节省空间呢?
Bitmap底层是 bytes 数组,并且该数组支持自动扩展,如果设置了某个偏移位置超出了现有的内容范围,位数组就会自动扩充。内存模型如下
Redis官方已为bitmap配置了一些操作函数
set bitmap1 hello
ok
get bitmap1
"hello"
# hello二进制(低位在左):
# 01101000 01100101 01101100 01101100 01101111
bitcount bitmap1
(Integer) 21
bitcount bitmap 0 1 # 取0-1字符上1的个数(注意不是0、1位)
(Integer)7
bitpos bitmap1 0
(Integer)0 #第一个0在最左边的0号位
bitpos bitmap 0 1
(Integer)8 #从第一个字符开始算起,第一个0在8号位(从左往右数)
getbit bitmap1 0
(Integer) 0
# 下面两步将hello 改成 heolo (“l” -----01101100, “0” ------01101111)
setbit bitmap1 22 1
(Integer) 0
setbit bitmap1 23 1
(Integer) 0
get bitmap1
"heolo"
# 从bitmap1二进制数的0号位开始取4位无符号数【注意:高位在左边】
bitfield bitmap1 get u4 0 #(0110)2
(integer) 6
# 从bitmap1二进制数的1号位开始取4位无符号数【注意:高位在左边】
bitfield bitmap1 get u4 1
(integer) 13 #(1101)2
# 从bitmap1二进制数的1号位开始取4位有符号数【注意:高位在左边】
bitfield bitmap1 get i4 1
(integer) -3 #(1101)2
特殊用法【语法糖】:
bitfield bitmap1 get u4 0 get u4 1 get i4 1
(integer) 6
(integer) 13
(integer) -3
# 将第八位开始的一个字符替换成‘a’
bitfield bitmap1 set u8 8 97
(integer) 101
Get bitmap1
”haolo”
由于bitmap便于存储大量的数据,它可以被应用于存储当前在线用户、 计算当前在线用户数量,存储用户日常打卡、计算用户连续打卡天数等场景。此外,它还可以用于URL黑白名单的过滤,著名的应用有布隆过滤器。
场景分析:
package bitmap; import java.util.Arrays; /** * 尝试实现一下redis的bitmap */ public class MyBitmap { /** * init_factor 初始化因子,模仿hashmap */ private static final int INIT_FACTOR = 16; /** * bitmap扩容临界点1M * 为了防止浪费内存,1M前每次扩容两倍扩容,否则就1M扩容 */ private static final int RESIZE_THRESHOLD = 1 * 1024 * 1024 * 8; /** * myBits - 位数组 */ private byte[] myBits; public MyBitmap() { myBits = new byte[INIT_FACTOR]; } /** * 存放位数组 * @param numb 位的索引 * @param bit 当前的位 * @return this */ public MyBitmap setBit(int numb, byte bit) { if (numb > myBits.length) { resize(numb); } myBits[numb] = bit; return this; } /** * 获取位数组长度 * @return 位数组长度 */ public int getLength() { return myBits.length; } /** * 存放位数组 * @param numb 位的索引 * @param bit 当前的位 * @return this */ public byte getBit(int numb) { if (numb > myBits.length) { return -1; } return myBits[numb]; } /** * 扩容 * @param newSize 新的内存空间 */ private void resize(int newSize) { byte[] temp; if (newSize < RESIZE_THRESHOLD) { // 两倍扩容 newSize = bitTableSizeFor(newSize); } else if (newSize < Integer.MAX_VALUE) { // 每次增加1M newSize = bitTableSizeForOverThreshold(newSize); } else { // integer的最大值 newSize = Integer.MAX_VALUE; } temp = new byte[newSize]; //复制数据 for (int i = 0; i < myBits.length; i++) { temp[i] |= myBits[i]; } myBits = temp; } /** * 获取离目标容量最近的1M的倍数 * @param newSize * @return 离目标容量最近的1M的倍数 */ private int bitTableSizeForOverThreshold( int newSize ) { int temp = (newSize - 1) >> 23; // 获取高位 return (temp + 1) << 23; } /** * 获取离目标容量最近的2的幂次方,模仿hashmap jdk7.0 * @param newSize * @return 离目标容量最近的2的幂次方 */ private int bitTableSizeFor(int newSize) { int temp = newSize - 1; temp |= temp >> 1; temp |= temp >> 2; temp |= temp >> 4; temp |= temp >> 8; temp |= temp >> 16; return (temp < 0) ? 1 : (temp + 1); } public static void main(String[] args) { MyBitmap map = new MyBitmap(); Stopwatch sw = new Stopwatch(); System.out.println(map.setBit(1000000200,(byte) 1).getBit(1000000200)); System.out.println(map.getLength()); System.out.println("持续时间: " + sw.countTime()); } }
输出结果
1
1006632960
持续时间: 0.391
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。