通过了解数据结构，就能知道对象性能，边界条件，就自然而然知道如何恰当的使用它们，做业务时就能选到最合适的对象。
上图是Redis最基本的结构体，所有Redis对象都被封装在RedisObject中。最基本的结构代码往往是最精简的。该结构中有5个成员，type 4 比特，encoding也是4比特。从代码得知：
Redis的数据类型不超过16种，编码方式不超过16种，且类型跟编码方式不一一对应，一种类型可能有多个编码方式，数据也可以共享。
首先看Object的第一个成员type，实际上Redis里面一共有5种类型：字符串、列表、集合、有序集合、哈希，这几种方式和type的对应关系见下表。
当字符串较小，Redis里字符串长度<=39时，会用EMBSTR编码方式。在这种编码方式下，字符串跟Object在连续的内存上，省去了多次内存分配。不过当字符串增长或者改变时，不能用该种方式，需要换成第一种，所以长度限制为39。
String类型还有一种特殊的编码方式，即字符串数值是整数的时候，为特殊的INT类型编码。INT类型不需要ptr指到字符空间，而是直接用指针的值代表字符串的值，因此ptr已经不是指针。这样就省去了sds开销，其内存占用最小。实际上在Redis里，程序启动时直接创建了10000个RedisObject，代表1-10000的整型，如果LRU没有意义，后面就没有其他开销，用预先分配好的值。简单来说，整数类型的Value比普通的Value节省内存，其值为0-10000，LRU无效情况下的String Object可共享，而且一般情况下没必要强求EMBSTR。
上图是压缩列表，它相当于把所有的成员都叠在一起，没有额外的数据结构，空间占用比较小。缺点是读写的时候整个压缩列表都需要修改，所以一般在数据量小的时候才使用，一般能达到10倍的压缩比。数据量大小都可以通过配置文件更改，Hash和List的默认情况是512和64，需要利用时就对业务进行改造，可以按日期拆分，每天一个Key，也可以按数值取模，或按前缀拆分等。通过合理的拆分，充分利用压缩列表特性，压缩率可达10倍，平均为5倍。
那其他容器在普通情况下用什么样的数据结构呢？算法类的数据结构里用的最多的为哈希表。因为它的读写复杂度都是O（1），是所有数据结构里面最快的一种。Redis中的哈希表使用链地址法解决hash冲突问题，若有多个key的hash值一致，通过遍历链表的形式找到目标Key。当哈希表的负载因子过大时，冲突几率变大，其性能就会下降。Redis里面哈希表槽的数目是动态增长的，HT默认初始大小为4。当负载因子超出合理范围(0.1 – 5)时进行扩缩容(rehash)，将原来哈希表里面的数值rehash，放在新的哈希表里面，也就是说同时存在两个哈希表，一旧一新。不过一次性rehash太多的Key可能导致服务长时间不可用，Redis采用渐进式rehash，分批进行。
Redis里用字典结构对Redis进行封装，主要就是两个哈希表，读写复杂度均为O(1)。DICT的读写效率最高。那什么时间进行渐进式Rehash的算法呢？每次对DICT执行添加、删除、查找或者更新操作时，除了执行指定的操作以外，还会顺带将ht[0] 哈希表在rehashidx索引上的所有键值对rehash到ht[1]，并将rehashidx的值增1；直到整个ht[0]全部完成rehash后，rehashindex设为-1，释放ht[0]，ht[1]置为ht[0]，在ht[1]中创建一个新的空白表。
跳跃表是哈希里面用来做排序的，实现简单，算法巧妙，算法效率和平衡树一样。算法核心为，每插入一个节点，节点是随机数，第n+1层的节点数目为第n层的1/4，性能如上表所示。
原地址：https://mp.weixin.qq.com/s/n4HXKXPKf87qgZ_e6s4gPg
