1、基本类型及底层实现

1.1、String

用途：

适用于简单key-value存储、setnx key value实现分布式锁、计数器(原子性)、分布式全局唯一ID。

底层：C语言中String用char[]数组表示，源码中用SDS(simple dynamic string)封装char[]，这是是Redis存储的最小单元，一个SDS最大可以存储512M信息。

struct sdshdr{
  unsigned int len; // 标记char[]的长度
  unsigned int free; //标记char[]中未使用的元素个数
  char buf[]; // 存放元素的坑
}

Redis对SDS再次封装生成了RedisObject，核心有两个作用：

说明是5种类型哪一种。

里面有指针用来指向 SDS。

当你执行set name sowhat的时候，其实Redis会创建两个RedisObject对象，键的RedisObject 和 值的RedisOjbect 其中它们type = REDIS_STRING，而SDS分别存储的就是 name 跟 sowhat 字符串咯。

并且Redis底层对SDS有如下优化：

SDS修改后大小 > 1M时 系统会多分配空间来进行空间预分配。

SDS是惰性释放空间的，你free了空间，可是系统把数据记录下来下次想用时候可直接使用。不用新申请空间。

1.2、List

查看源码底层 adlist.h 会发现底层就是个 双端链表，该链表最大长度为2^32-1。常用就这几个组合。

lpush + lpop = stack 先进后出的栈

lpush + rpop = queue 先进先出的队列

lpush + ltrim = capped collection 有限集合

lpush + brpop = message queue 消息队列

一般可以用来做简单的消息队列，并且当数据量小的时候可能用到独有的压缩列表来提升性能。当然专业点还是要 RabbitMQ、ActiveMQ等

1.3、Hash

散列非常适用于将一些相关的数据存储在一起，比如用户的购物车。该类型在日常用途还是挺多的。

这里需要明确一点：Redis中只有一个K，一个V。其中 K 绝对是字符串对象，而 V 可以是String、List、Hash、Set、ZSet任意一种。

hash的底层主要是采用字典dict的结构，整体呈现层层封装。从小到大如下：

1.3.1、dictEntry

真正的数据节点，包括key、value 和 next 节点。

1.3.2、dictht

1、数据 dictEntry 类型的数组，每个数组的item可能都指向一个链表。

2、数组长度 size。

3、sizemask 等于 size - 1。

4、当前 dictEntry 数组中包含总共多少节点。

1.3.3、dict

1、dictType 类型，包括一些自定义函数，这些函数使得key和value能够存储

2、rehashidx 其实是一个标志量，如果为-1说明当前没有扩容，如果不为 -1 则记录扩容位置。

3、dictht数组，两个Hash表。

4、iterators 记录了当前字典正在进行中的迭代器

组合后结构就是如下：

1.3.4、渐进式扩容

为什么 dictht ht[2]是两个呢？目的是在扩容的同时不影响前端的CURD，慢慢的把数据从ht[0]转移到ht[1]中，同时rehashindex来记录转移的情况，当全部转移完成，将ht[1]改成ht[0]使用。

rehashidx = -1说明当前没有扩容，rehashidx != -1则表示扩容到数组中的第几个了。

扩容之后的数组大小为大于used*2的2的n次方的最小值，跟 HashMap 类似。然后挨个遍历数组同时调整rehashidx的值，对每个dictEntry[i] 再挨个遍历链表将数据 Hash 后重新映射到 dictht[1]里面。并且 dictht[0].use 跟 dictht[1].use 是动态变化的。

整个过程的重点在于rehashidx，其为第一个数组正在移动的下标位置，如果当前内存不够，或者操作系统繁忙，扩容的过程可以随时停止。

停止之后如果对该对象进行操作，那是什么样子的呢？

1、如果是新增，则直接新增后第二个数组，因为如果新增到第一个数组，以后还是要移过来，没必要浪费时间

2、如果是删除，更新，查询，则先查找第一个数组，如果没找到，则再查询第二个数组。

1.4、Set

如果你明白Java中HashSet是HashMap的简化版那么这个Set应该也理解了。都是一样的套路而已。这里你可以认为是没有Value的Dict。看源码 t.set.c 就可以了解本质了。

int setTypeAdd(robj *subject, robj *value) {
    long long llval;
    if (subject->encoding == REDIS_ENCODING_HT) {
         // 看到底层调用的还是dictAdd，只不过第三个参数= NULL
         if (dictAdd(subject->ptr,value,NULL) == DICT_OK) {
            incrRefCount(value);
            return 1;
        }
        ....

1.5、ZSet

范围查找 的天敌就是 有序集合，看底层 redis.h 后就会发现 Zset用的就是可以跟二叉树媲美的跳跃表来实现有序。跳表就是多层链表的结合体，跳表分为许多层(level)，每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度。

每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层(level 1)包含了全部的数据；层次越高，跳跃性越大，包含的数据越少。并且随便插入一个数据该数据是否会是跳表索引完全随机的跟玩骰子一样。

跳表包含一个表头，它查找数据时，是从上往下，从左往右进行查找。现在找出值为37的节点为例，来对比说明跳表和普遍的链表。

1. 没有跳表查询 比如我查询数据37，如果没有上面的索引时候路线如下图：
2. 有跳表查询 有跳表查询37的时候路线如下图：应用场景：

积分排行榜、时间排序新闻、延时队列。

1.6、Redis Geo

以前写过Redis Geo核心原理解析，想看的直接跳转即可。他的核心思想就是将地球近似为球体来看待，然后 GEO利用 GeoHash 将二维的经纬度转换成字符串，来实现位置的划分跟指定距离的查询。

1.7、HyperLogLog

HyperLogLog ：是一种概率数据结构，它使用概率算法来统计集合的近似基数。而它算法的最本源则是伯努利过程 + 分桶 + 调和平均数。具体实现可看 HyperLogLog 讲解。

功能：误差允许范围内做基数统计 (基数就是指一个集合中不同值的个数) 的时候非常有用，每个HyperLogLog的键可以计算接近2^64不同元素的基数，而大小只需要12KB。错误率大概在0.81%。所以如果用做 UV 统计很合适。

HyperLogLog底层 一共分了 2^14 个桶，也就是 16384 个桶。每个(registers)桶中是一个 6 bit 的数组，这里有个骚操作就是一般人可能直接用一个字节当桶浪费2个bit空间，但是Redis底层只用6个然后通过前后拼接实现对内存用到了极致，最终就是 16384*6/8/1024 = 12KB。

1.8、bitmap

BitMap 原本的含义是用一个比特位来映射某个元素的状态。由于一个比特位只能表示 0 和 1 两种状态，所以 BitMap 能映射的状态有限，但是使用比特位的优势是能大量的节省内存空间。

在 Redis 中BitMap 底层是基于字符串类型实现的，可以把 Bitmaps 想象成一个以比特位为单位的数组，数组的每个单元只能存储0和1，数组的下标在 Bitmaps 中叫做偏移量，BitMap 的 offset 值上限 2^32 - 1。

1. 用户签到

key = 年份：用户id offset = （今天是一年中的第几天） % （今年的天数）

2. 统计活跃用户

使用日期作为 key，然后用户 id 为 offset 设置不同offset为0 1 即可。

PS : Redis 它的通讯协议是基于TCP的应用层协议 RESP(REdis Serialization Protocol)。

1.9、Bloom Filter

使用布隆过滤器得到的判断结果：不存在的一定不存在，存在的不一定存在。

布隆过滤器 原理：

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点(有效降低冲突概率)，把它们置为1。检索时，我们只要看看这些点是不是都是1就知道集合中有没有它了：如果这些点有任何一个为0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

想玩的话可以用Google的guava包玩耍一番。