Redis各种数据结构在我们项目中都有运用，前面写了一篇redis的常见应用场景，下面就redis的数据结构做了一些总结，各数据结构常见运用如下：
String：缓存、限流、计数器、分布式锁、分布式Session
Hash：存储用户信息、用户主页访问量、组合查询
List：微博关注人时间轴列表、简单队列
Set：赞、踩、标签、好友关系
Zset：排行榜
Redis的对象redisObject
当我们执行set key value时，会有以下数据模型：
dicEntry：redis给每个key-value键值对分配一个dictEntry，里面有着key和val的指针，next指向下一个dictEntry形成链表，这个指针可以将多个哈希值相同的键值对链接在一起，由此来解决哈希冲突问题(链地址法)。
sds：键key“hello”是以SDS（简单动态字符串）存储，后面详细介绍。
redisObject：值val“world”存储在redisObject中。实际上，redis常用5中类型都是以redisObject来存储的；而redisObject中的type字段指明了Value对象的类型，ptr字段则指向对象所在的地址。
String
字符串对象的底层实现可以是int、raw、embstr
int编码字符串对象和embstr编码字符串对象在一定条件下会转化为raw编码字符串对象。embstr：<=39字节的字符串。int：8个字节的长整型。raw：大于39个字节的字符串。
简单动态字符串（SDS），这种结构更像C++的String或者Java的ArrayList，长度动态可变：
structsdshdr{
// buf 中已占用空间的长度
intlen;
// buf 中剩余可用空间的长度
intfree;
// 数据空间
charbuf[];// ’\0’空字符结尾
};
get：sdsrange---O(n)
set：sdscpy—O(n)
create：sdsnew---O(1)
len：sdslen---O(1)
常数复杂度获取字符串长度：因为SDS在len属性中记录了长度，所以获取一个SDS长度时间复杂度仅为O(1)。
List
List对象的底层实现是quicklist（快速列表，是ziplist 压缩列表 和linkedlist 双端链表 的组合）。Redis中的列表支持两端插入和弹出，并可以获得指定位置（或范围）的元素，可以充当数组、队列、栈等。
Hash
Hash对象的底层实现可以是ziplist（压缩列表）或者hashtable（字典或者也叫哈希表）。
Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：1.哈希中元素数量小于512个；2.哈希中所有键值对的键和值字符串长度都小于64字节。
hashtable哈希表可以实现O(1)复杂度的读写操作，因此效率很高。源码如下：
typedefstructdict{
// 类型特定函数
dictType *type;
// 私有数据
void*privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
intrehashidx;/* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
intiterators;/* number of iterators currently running */
} dict;
typedefstructdictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsignedlongsize;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsignedlongsizemask;
// 该哈希表已有节点的数量
unsignedlongused;
} dictht;
typedefstructdictEntry{
void*key;
union{void*val;uint64_tu64;int64_ts64;} v;
// 指向下个哈希表节点，形成链表
structdictEntry*next;
} dictEntry;
typedefstructdictType{
// 计算哈希值的函数
unsignedint(*hashFunction)(constvoid*key);
// 复制键的函数
void*(*keyDup)(void*privdata,constvoid*key);
// 复制值的函数
void*(*valDup)(void*privdata,constvoid*obj);
// 对比键的函数
int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key2);
// 销毁键的函数
void(*keyDestructor)(void*privdata,void*key);
// 销毁值的函数
void(*valDestructor)(void*privdata,void*obj);
} dictType;
这个结构类似于JDK7以前的HashMap，当有两个或以上的键被分配到哈希数组的同一个索引上时，会产生哈希冲突。Redis也使用链地址法来解决键冲突。即每个哈希表节点都有一个next指针，多个哈希表节点用next指针构成一个单项链表，链地址法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位。
Redis中的字典使用hashtable作为底层实现的话，每个字典会带有两个哈希表，一个平时使用，另一个仅在rehash（重新散列）时使用。随着对哈希表的操作，键会逐渐增多或减少。为了让哈希表的负载因子维持在一个合理范围内，Redis会对哈希表的大小进行扩展或收缩（rehash），也就是将ht【0】里面所有的键值对分多次、渐进式的rehash到ht【1】里。
Set
Set集合对象的底层实现可以是intset（整数集合）或者hashtable（字典或者也叫哈希表）。
intset（整数集合）当一个集合只含有整数，并且元素不多时会使用intset（整数集合）作为Set集合对象的底层实现。
typedefstructintset{
// 编码方式
uint32_tencoding;
// 集合包含的元素数量
uint32_tlength;
// 保存元素的数组
int8_tcontents[];
} intset;
sadd:intsetAdd---O(1)
smembers:intsetGetO(1)---O(N)
srem:intsetRemove---O(N)
slen:intsetlen ---O(1)
intset底层实现为有序，无重复数组保存集合元素。 intset这个结构里的整数数组的类型可以是16位的，32位的，64位的。如果数组里所有的整数都是16位长度的，如果新加入一个32位的整数，那么整个16的数组将升级成一个32位的数组。升级可以提升intset的灵活性，又可以节约内存，但不可逆。
ZSet
ZSet有序集合对象底层实现可以是ziplist（压缩列表）或者skiplist（跳跃表）。
当一个有序集合的元素数量比较多或者成员是比较长的字符串时，Redis就使用skiplist（跳跃表）作为ZSet对象的底层实现。
typedefstructzskiplist{
// 表头节点和表尾节点
structzskiplistNode*header, *tail;
// 表中节点的数量
unsignedlonglength;
// 表中层数最大的节点的层数
intlevel;
} zskiplist;
typedefstructzskiplistNode{
// 成员对象
robj *obj;
// 分值
doublescore;
// 后退指针
structzskiplistNode*backward;
// 层
structzskiplistLevel{
// 前进指针
structzskiplistNode*forward;
// 跨度---前进指针所指向节点与当前节点的距离
unsignedintspan;
} level[];
} zskiplistNode;
zadd---zslinsert---平均O(logN), 最坏O(N)
zrem---zsldelete---平均O(logN), 最坏O(N)
zrank--zslGetRank---平均O(logN), 最坏O(N)
skiplist的查找时间复杂度是LogN，可以和平衡二叉树相当，但实现起来又比它简单。跳跃表(skiplist)是一种有序数据结构，它通过在某个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
网友评论