《Redis 深度历险》读书笔记 -- 之位图与 HyperLogLog 位图 1、什么是位图? 位图并不是什么特殊的数据结构,而是定义在 String 类型上的一个面向字节操作的集合,也就是 byte 数组,位图的最小单位是 bit,每个 bit 的取值只能是 0 或者 1。 2、位图的基本用法 位图数据结构是可以自 ..

Redis 位图与 HyperLogLog

《Redis 深度历险》读书笔记 -- 之位图与 HyperLogLog

位图

1、什么是位图?

位图并不是什么特殊的数据结构,而是定义在 String 类型上的一个面向字节操作的集合,也就是 byte 数组,位图的最小单位是 bit,每个 bit 的取值只能是 0 或者 1。

2、位图的基本用法
零存整取

首先我们先用 python 获取‘hello’的 ASCII 码的二进制值

>>> bin(ord('h'))
'0b1101000'
>>> bin(ord('e'))
'0b1100101'
>>> bin(ord('l'))
'0b1101100'
>>> bin(ord('o'))
'0b1101111'

由于位数组的顺序和字符的位顺序是相反的
所以 hello 所对应二进制位表示为为
01101000 01100101 01101100 01101100 01101111
12345678 9....
我们只需要在为 1 的地方设置为 1 即可

127.0.0.1:6379> setbit s 1 1
(integer) 0
127.0.0.1:6379> setbit s 2 1
(integer) 0
127.0.0.1:6379> setbit s 4 1
(integer) 0
127.0.0.1:6379> setbit s 9 1
(integer) 0
127.0.0.1:6379> setbit s 10 1
(integer) 0
127.0.0.1:6379> setbit s 13 1
(integer) 0
127.0.0.1:6379> setbit s 15 1
(integer) 0
127.0.0.1:6379> get s
"he"
零存零取
127.0.0.1:6379> setbit w 1 1
(integer) 0
127.0.0.1:6379> setbit w 4 1
(integer) 0
127.0.0.1:6379> getbit w 1
(integer) 1
127.0.0.1:6379> getbit w 2
(integer) 0
整存零取
127.0.0.1:6379> set w h
OK
127.0.0.1:6379> getbit w 1
(integer) 1
127.0.0.1:6379> getbit w 2
(integer) 1
127.0.0.1:6379> getbit w 3
(integer) 0
127.0.0.1:6379> getbit w 4
(integer) 1

如果对应位的字节是不可打印字符,客户端会显示该字符的十六进制形式

127.0.0.1:6379> setbit x 0 1
(integer) 0
127.0.0.1:6379> setbit x 1 1
(integer) 0
127.0.0.1:6379> get x
"\xc0"
3、位图的统计和查找
127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitcount w
(integer) 21
127.0.0.1:6379> bitcount w 0 0 #第一个字符中1 的位数
(integer) 3
127.0.0.1:6379> bitcount w 0 1
(integer) 7
127.0.0.1:6379> bitpos w 0 #第一个0 位
(integer) 0
127.0.0.1:6379> bitpos w 1
(integer) 1
127.0.0.1:6379> bitpos w 1 1 1 #从第二个字符算起,第一个1位
(integer) 9
127.0.0.1:6379> bitpos w 1 2 2
(integer) 17
4、位图的 bitfield 指令

不知道为什么我的客户端,在敲这条命令的时候报错,所以代码就先不贴了,待以后再试试

127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitfield w get u4 0
(error) ERR unknown command 'bitfield'
127.0.0.1:6379> bitfield w get u4 0

HyperLogLog

Set 的高级数据结构,HyperLogLog,它提供了不精确的去重计数方案,标准误差是 0.81% 。
应用场景:某个网页的每天的 UV 数据

HyperLogLog 使用方法
127.0.0.1:6379> pfadd codehole user1
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 1
127.0.0.1:6379> pfadd codehole user2
(integer) 1
127.0.0.1:6379> pfadd codehole user3
(integer) 1
127.0.0.1:6379> pfadd codehole user4
(integer) 1
127.0.0.1:6379> pfadd codehole user5
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 5

接下来增大数据量

public class PfTest {
    public static void main(String[] args) {
        Jedis jedis = new Jedis("127.0.0.1");
        for (int i = 0; i < 100000; i++){
            jedis.pfadd("codehole","user"+i);
        }
        long total = jedis.pfcount("codehole");
        System.out.println(total);
        jedis.close();
    }
}

---------
99715

Process finished with exit code 0

将上述程序执行俩次,会发现俩次的结果一样,这说明 pf 确实有去重功能,而且误差率也不是很高。

  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    149 引用 • 216 回帖 • 776 关注
  • 中间件
    3 引用 • 2 回帖
  • NoSQL
    10 引用 • 3 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2355 引用 • 7823 回帖 • 890 关注
1 回帖
请输入回帖内容...