redis bitmap数据结构之java对等操作 - 等你归去来
source link: https://www.cnblogs.com/yougewe/p/16795118.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
在之前的文章中，我们有说过bitmap，bitmap在很多场景可以应用，比如黑白名单，快速判定，登录情况等等。总之，bitmap是以其高性能出名。其基本原理是一位存储一个标识，其他衍生知道咱就不说了，而redis就是以这种原生格式存储的。
实际上，redis是基于string的数据结构实现了bitmap的功能。
1. redis基本的bitmap操作命令
最基本的，redis的bitmap有设置和读取两个值，即 setbit/getbit, 非常容易理解，即设置某个标识为1，那么取值判定的时候，就可以得到true.
127.0.0.1:6379> setbit bm1 222 1 (integer) 0 127.0.0.1:6379> getbit bm1 222 (integer) 1
这很容易理解，也是最基本的。当然，它还提供其他的一些操作：BITCOUNT 做数据量统计, BITOP 做bitmap的交并差运算... 我们也不必过多讨论它。
2. java中的原生bitmap
可以说redis的bitmap实现相当之简单，所以java也就顺便实现了一个bitmap的版本：BitSet .
@Test
public void testJavaBitmap() {
BitSet bitmap = new BitSet();
bitmap.set(88);
// exist = true
boolean exist = bitmap.get(88);
BitSet bitmap2 = new BitSet();
bitmap2.set(99);
// bitmap中将包含 [88, 99]
bitmap.or(bitmap2);
}
java中的bitmap实现，也是按位存储，但是是基于long的存储。
/*
* BitSets are packed into arrays of "words." Currently a word is
* a long, which consists of 64 bits, requiring 6 address bits.
* The choice of word size is determined purely by performance concerns.
*/
private final static int ADDRESS_BITS_PER_WORD = 6;
/**
* Sets the bit at the specified index to {@code true}.
*
* @param bitIndex a bit index
* @throws IndexOutOfBoundsException if the specified index is negative
* @since JDK1.0
*/
public void set(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
int wordIndex = wordIndex(bitIndex);
expandTo(wordIndex);
words[wordIndex] |= (1L << bitIndex); // Restores invariants
checkInvariants();
}
/**
* Given a bit index, return word index containing it.
*/
private static int wordIndex(int bitIndex) {
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
所以，我们可以得出一个浅显的结论，bitmap很简单，一点都不神秘。但是，大道至简，它高性能，它自然还是有好处的，咱们该用还得用。显然，java版本的bitmap虽然很很好用，但是它只是应用级别的，只能在进程内使用，有太多的其他问题没考虑，所以咱们还得要依赖于redis的bitmap.
问题：如果我有很多的数字标识想要写入redis中，然后再进行读取判定，该怎么办呢？
很简单的，我们可以一个个地调用 setbit 命令，依次写入redis中。这自然能解决问题，但是明显会带来很多的网络io。
其次，我们可以使用pipeline调用setbit进行批量写入。这当然是一种优化方案，只是仍然不是最优。
那有没有什么更好的办法呢？
3. java和redis的bitmap互操作
对于批量的操作，redis是基于string实现，而java是基于bitset实现。其功能都基本差不多，判定、写入、交并差运算。那么，除了一个个按照各自语法进行添加外，有没有可能进行数据结构上的对等呢？
这个思路是很自然的，因为我们已经完全理解了各自的实现原理，为什么不呢？直接将BitSet转换为byte[]写入redis，直接将redis的bitmap当作string读出来不就可以了吗？
事实真是如此吗？实际上有点差别，原因是一个是大端存储，一个是小端存储。
比如：比如对于存储byte值: 00000010 , redis中会解释为偏移为6的值为1, 而在java中则会解析为数字2存在于bitmap中。也就是说两个的判定结果是不一样的，一个是6，一个是2。如果把java中的值给调换一下，变成 01000000，那么就和redis是一样的了。
而从redis中转变到java中，则需要将每个byte位做一逆向操作判定，具体实现如下：
@Test
public void testSetBitmapData2Redis() {
//创建一个连接
Jedis jedis = new Jedis("localhost", 6379);
// 正向设置redis bitmap
String testBitmapKey = "mybitmap1";
jedis.set(testBitmapKey.getBytes(),
genRedisBitmap(2, 55, 133, 65537, 10_0000));
Assert.assertEquals("bitmap取值不正确", true,
jedis.getbit(testBitmapKey, 2L));
Assert.assertEquals("bitmap取值不正确", true,
jedis.getbit(testBitmapKey, 133L));
Assert.assertEquals("bitmap取值不正确", true,
jedis.getbit(testBitmapKey, 65537L));
Assert.assertEquals("bitmap取值不正确", true,
jedis.getbit(testBitmapKey, 10_0000L));
Assert.assertEquals("bitmap取值不正确", false,
jedis.getbit(testBitmapKey, 3L));
//在redis中获取name值
byte[] redisBitmapData = jedis.get("mybitmap1".getBytes());
BitSet bitSet = convertRedisBitmapToJava(redisBitmapData);
Assert.assertTrue("redisBitmap反解不正确", bitSet.get(2));
Assert.assertTrue("redisBitmap反解不正确", bitSet.get(133));
Assert.assertTrue("redisBitmap反解不正确", bitSet.get(65537));
Assert.assertTrue("redisBitmap反解不正确", bitSet.get(10_0000));
Assert.assertFalse("redisBitmap反解不正确", bitSet.get(332));
jedis.close();
}
// 将redis的bitmap转换为java 的bitset
private BitSet convertRedisBitmapToJava(byte[] redisBitmapData) {
int len = redisBitmapData.length;
BitSet bitSet = new BitSet();
// 每个 byte 8位, 所以整个bitmap 的长度为 len * 8
for (int i = 0; i < len * 8; i++) {
byte currentSegment = redisBitmapData[i / 8];
if(currentSegment == 0) {
continue;
}
if((currentSegment & (1 << (7 - (i % 8) ) ) ) != 0 ) {
bitSet.set(i);
}
}
return bitSet;
}
// 生成redis的bitmap数据
private byte[] genRedisBitmap(int... items) {
BitSet bitSet = new BitSet();
// 2 55 133
for (int k : items) {
bitSet.set(k);
}
byte[] targetBitmap = bitSet.toByteArray();
convertJavaToRedisBitmap(targetBitmap);
return targetBitmap;
}
// 将java中的字节数组转换为redis的bitmap数据形式
private void convertJavaToRedisBitmap(byte[] bytes) {
int len = bytes.length;
for (int i = 0; i < len; i++) {
byte b1 = bytes[i];
if(b1 == 0) {
continue;
}
byte transByte = 0;
for (byte j = 0; j < 8; j++) {
transByte |= (b1 & (1 << j)) >> j << (7 -j);
}
bytes[i] = transByte;
}
}
经验证，将8位的byte进行位置反转，能够完美匹配两种数据结构。
如此一来，就可以轻松将整个bitmap进行初始化设置到redis中，从而在redis的bitmap中，使用 getbit 进行高效判定了。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK