redis各类型数据结构和底层实现源码分析( 三 ) _redis

文章插图
这个结构类似于JDK7以前的HashMap<String,Object>，当有两个或以上的键被分配到哈希数组的同一个索引上时，会产生哈希冲突。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的灵活性，又可以节约内存，但不可逆。
7.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)