2.2.1Redis链表的特性
Redis的链表有以下特性：
- 无环双向链表
- 获取表头指针，表尾指针，链表节点长度的时间复杂度均为O(1)
- 链表使用
void *指针来保存节点值，可以保存各种不同类型的值
2.3哈希表
声明：《Redis设计与实现》里边有“字典”这么一个概念，我个人认为还是直接叫哈希表比较通俗易懂。从代码上看：“字典”也是在哈希表基础上再抽象了一层而已。
在Redis中，key-value的数据结构底层就是哈希表来实现的。对于哈希表来说，我们也并不陌生。在Java中，哈希表实际上就是数组+链表的形式来构建的。下面我们来看看Redis的哈希表是怎么构建的吧。
在Redis里边，哈希表使用dictht结构来定义：
typedef struct dictht{ //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码，用于计算索引值 //总是等于size-1 unsigned long sizemark; //哈希表已有节点数量 unsigned long used; }dictht
哈希表的数据结构
哈希表的数据结构
我们下面继续写看看哈希表的节点是怎么实现的吧：
typedef struct dictEntry { //键 void *key; //值 union { void *value; uint64_tu64; int64_ts64; }v; //指向下个哈希节点，组成链表 struct dictEntry *next; }dictEntry;
从结构上看，我们可以发现：Redis实现的哈希表和Java中实现的是类似的。只不过Redis多了几个属性来记录常用的值：sizemark(掩码)、used(已有的节点数量)、size(大小)。
同样地，Redis为了更好的操作，对哈希表往上再封装了一层(参考上面的Redis实现链表)，使用dict结构来表示：
typedef struct dict { //类型特定函数 dictType *type; //私有数据 void *privdata; //哈希表 dictht ht[2]; //rehash索引 //当rehash不进行时，值为-1 int rehashidx; }dict; //----------------------------------- typedef struct dictType{ //计算哈希值的函数 unsigned int (*hashFunction)(const void * key); //复制键的函数 void *(*keyDup)(void *private, const void *key); //复制值得函数 void *(*valDup)(void *private, const void *obj); //对比键的函数 int (*keyCompare)(void *privdata , const void *key1, const void *key2) //销毁键的函数 void (*keyDestructor)(void *private, void *key); //销毁值的函数 void (*valDestructor)(void *private, void *obj); }dictType
所以，最后我们可以发现，Redis所实现的哈希表最后的数据结构是这样子的：
从代码实现和示例图上我们可以发现，Redis中有两个哈希表：
- ht[0]：用于存放真实的
key-vlaue数据 - ht[1]：用于扩容(rehash)
Redis中哈希算法和哈希冲突跟Java实现的差不多，它俩差异就是：
- Redis哈希冲突时：是将新节点添加在链表的表头。
- JDK1.8后，Java在哈希冲突时：是将新的节点添加到链表的表尾。
2.3.1rehash的过程
下面来具体讲讲Redis是怎么rehash的，因为我们从上面可以明显地看到，Redis是专门使用一个哈希表来做rehash的。这跟Java一次性直接rehash是有区别的。
在对哈希表进行扩展或者收缩操作时，reash过程并不是一次性地完成的，而是渐进式地完成的。
Redis在rehash时采取渐进式的原因：数据量如果过大的话，一次性rehash会有庞大的计算量，这很可能导致服务器一段时间内停止服务。
Redis具体是rehash时这么干的：
- (1:在字典中维持一个索引计数器变量rehashidx，并将设置为0，表示rehash开始。
- (2:在rehash期间每次对字典进行增加、查询、删除和更新操作时，除了执行指定命令外；还会将ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。
- (3:字典操作不断执行，最终在某个时间点，所有的键值对完成rehash，这时将rehashidx设置为-1，表示rehash完成
- (4:在渐进式rehash过程中，字典会同时使用两个哈希表ht[0]和ht[1]，所有的更新、删除、查找操作也会在两个哈希表进行。例如要查找一个键的话，服务器会优先查找ht[0]，如果不存在，再查找ht[1]，诸如此类。此外当执行新增操作时，新的键值对一律保存到ht[1]，不再对ht[0]进行任何操作，以保证ht[0]的键值对数量只减不增，直至变为空表。
2.4跳跃表(shiplist)
跳跃表(shiplist)是实现sortset(有序集合)的底层数据结构之一！
跳跃表可能对于大部分人来说不太常见，之前我在学习的时候发现了一篇不错的文章讲跳跃表的，建议大家先去看完下文再继续回来阅读：
- 漫画算法：什么是跳跃表？http://blog.jobbole.com/111731/
Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成。其中zskiplist保存跳跃表的信息(表头，表尾节点，长度)，zskiplistNode则表示跳跃表的节点。
按照惯例，我们来看看zskiplistNode跳跃表节点的结构是怎么样的：
typeof struct zskiplistNode { // 后退指针 struct zskiplistNode *backward; // 分值 double score; // 成员对象 robj *obj; // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; } zskiplistNode;
zskiplistNode的对象示例图(带有不同层高的节点)：
带有不同层高的节点
示例图如下：
跳跃表节点的示例图
zskiplist的结构如下：
typeof struct zskiplist { // 表头节点，表尾节点 struct skiplistNode *header,*tail; // 表中节点数量 unsigned long length; // 表中最大层数 int level; } zskiplist;
最后我们整个跳跃表的示例图如下：
跳跃表示例图
2.5整数集合(intset)
整数集合是set(集合)的底层数据结构之一。当一个set(集合)只包含整数值元素，并且元素的数量不多时，Redis就会采用整数集合(intset)作为set(集合)的底层实现。
整数集合(intset)保证了元素是不会出现重复的，并且是有序的(从小到大排序)，intset的结构是这样子的：
typeof struct intset { // 编码方式 unit32_t encoding; // 集合包含的元素数量 unit32_t lenght; // 保存元素的数组 int8_t contents[]; } intset;
intset示例图：
说明：虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值：
- INTSET_ENC_INT16
- INTSET_ENC_INT32
- INTSET_ENC_INT64
从编码格式的名字我们就可以知道，16,32,64编码对应能存放的数字范围是不一样的。16明显最少，64明显最大。
如果本来是INTSET_ENC_INT16的编码，想要存放大于INTSET_ENC_INT16编码能存放的整数值，此时就得编码升级(从16升级成32或者64)。步骤如下：
- 1）根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
- 2）将底层数组现有的所以元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。
- 3）将新元素添加到底层数组。
另外一提：只支持升级操作，并不支持降级操作。
2.6压缩列表(ziplist)
压缩列表(ziplist)是list和hash的底层实现之一。如果list的每个都是小整数值，或者是比较短的字符串，压缩列表(ziplist)作为list的底层实现。
压缩列表(ziplist)是Redis为了节约内存而开发的，是由一系列的特殊编码的连续内存块组成的顺序性数据结构。
压缩列表结构图例如下：
下面我们看看节点的结构图：
压缩列表从表尾节点倒序遍历，首先指针通过zltail偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。
