不积跬步，无以至千里；不积小流，无以成江海。
前言
前一节对 Redis 和 Memcache 做了对比，我们知道了 Redis 的一些优良特性；
由于是 <strong>纯内存 操作，Redis 的性能非常出色，来自官网统计每秒可以处理超过 10 万次读写操作，是已知 <strong>性能最快 的KV DB;（ 期待能有更优秀的软件诞生 ）
国内各大互联网公司也都在使用Redis，也是后台开发者绕不开的必备技能；由于内存的宝贵，所以只有合适的数据结构用在最正确的地方才能发挥最大作用。
下面分析下 Redis 的基本数据结构及适用场景。
正文
Redis 有 5 种基础数据结构，分别为：<strong>string (字符串)、<strong>list (列表)、<strong>set (集合)、<strong>hash (哈希) 和 <strong>zset (有序集合)。
Tips:至于更高级的 BloomFilter、Geo、pub/sub、HyperLogLog 后面会单独介绍
Redis 所有操作都是 <strong>原子性 的，要么成功执行要么失败完全不执行。多个操作也 <strong>支持事务
，通过 MULTI 和 EXEC 把所有单个指令包起来。Redis 所有的数据结构都是以 <strong>唯一 的 key 字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。不同类型的数据结构的差异就在于 value 的结构不一样。
1. String
常用命令： get/set mget/mset incr/decr等
介绍： 字符串 string 是 Redis 最简单的数据结构,也是我们日常用的最多的一种类型。
string 是二进制安全的。也就是说 Redis 的 string 可以包含任何数据。比如 jpg 图片或者序列化的对象。
Redis 的字符串是动 <strong>态字符串，是可以修改的字符串，内部结构采用 <strong>预分配冗余空间 的方式来减少内存的频繁分配，内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。当字符串长度小于 <strong>1M 时，扩容都是 <strong>加倍 现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 <strong>512M。
字符串是由 <strong>多个字节 组成，每个字节又是由 8 个 <strong>bit 组成，如此便可以将一个字符串看成很多 bit 的组合，这便是 <strong>bitmap「位图」数据结构，后续也会拎出来说。
使用场景： 一个常见的用途就是缓存用户信息。我们将用户信息结构体使用 JSON 序列化成字符串，然后将序列化后的字符串塞进 <strong>Redis 来缓存。同样，取用户信息会经过一次 <strong>反序列化 的过程。还有如：计数器、分布式系统共享 session 等
2. List
常用命令： lpush/rpush/lpop/rpop/lrange等；
介绍： Redis list的实现为一个 <strong>双向链表,这意味着 list 的插入和删除操作非常快，时间复杂度为 <strong>O(1)，但是索引定位很慢，时间复杂度为 O(n)，这点让人非常意外。
再深入一点，你会发现 Redis 底层存储的还不是一个简单的 <strong>linkedlist，而是称之为快速链表 <strong>quicklist 的一个结构。
首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 <strong>ziplist，也即是<strong>压缩列表。
它将所有的元素紧挨着一起存储，分配的是一块 <strong>连续的内存。当数据量比较多的时候才会改成 <strong>quicklist。因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的 <strong>碎片化。比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next。所以 Redis 将链表和 ziplist 结合起来组成了 <strong>quicklist。也就是将多个 ziplist 使用 <strong>双向指针 串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。不得不说Redis为了高性能，真的是把内存用到了<strong>极致。
当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。
使用场景： 常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符串塞进 list，另一个线程从这个列表中轮询数据进行处理。
3. Hash
常用命令： hget/hset/hgetall等
介绍： Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。
不同的是，Redis 的字典的值只能是字符串，另外它们 <strong>rehash 的方式不一样，因为 Java 的 HashMap 在字典很大时，rehash 是个耗时的操作，需要一次性全部 rehash。Redis 为了高性能，不能堵塞服务，所以采用了 <strong>渐进式 rehash 策略。
何为渐进式 rehash
就是把拷贝节点数据的过程平摊到后续的操作中，而不是一次性拷贝。
所谓平摊到后续的操作中，就是对节点操作，例如再次插入，查找，删除，修改时都会进行拷贝。
要想实现这个过程，一个hash结构必须要有以下字段：
两个hash表。一个表拷贝到另一个表的容器。一个标识 rehashidx 来标明是否在进行 rehash 中。如果是，那么对节点的操作启动 rehash 过程。
何时启动 rehash
每次插入键值对时，都会检查是否需要扩容。当hash结构的第一个hash表 ht[0] 达到扩容条件就可以启动了。此时重新调整并分配新的空间，将hash结构的第二个hash表 ht[1] 指向这个空间。
rehash 具体过程
1，为 ht[1] 分配空间， 让 hash 同时持有 ht[0] 和 ht[1] 两个哈希表。
2，在字典中维持一个索引计数器变量 rehashidx， 并将它的值设置为0， 表示 rehash 工作正式开始。
3，在 rehash 进行期间， 每次对 hash 执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增 1。
4，随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1]， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
渐进式 <strong>rehash 的好处在于它采取<strong>分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。
当全部节点搬移完成之后需要做什么呢？
由于只有两个 hash 表容器（也只需要两个 hash 表容器就够了）
如果 ht[1] 需要 rehash 时再搬移到 ht[0] 吗？
当然这样也是没有问题的，但是显得有点混乱，因为搞不清楚哪个容器是要搬移的。
巧妙的做法是搬移完成之后，让 ht[0] 指向新的hash容器。这样 ht[0] 永远是那个要被搬移的对象，ht[1]是搬移过程中的中转。
<strong>思路比结论更重要
当 hash 移除了最后一个元素之后，该数据结构自动被删除，内存被回收。
使用场景： 我们要存储一个用户信息对象数据，其中包括用户ID、用户姓名、年龄和生日，通过用户ID我们希望获取该用户的姓名或者年龄或者生日；
hash 结构存储，不同于字符串一次性需要全部序列化整个对象，hash 可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时可以进行部分获取。而以整个字符串的形式去保存用户信息的话就只能一次性全部读取，这样就会比较浪费网络流量。
hash 也有缺点，hash 结构的存储消耗要高于单个字符串，到底该使用 hash 还是字符串，需要根据实际情况再三权衡。
4. Set
常用命令： sadd/spop/smembers/sunion等；
介绍： Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是 <strong>无序的唯一的。 它的内部实现相当于一个特殊的 hash，hash中所有的 value 都是一个值NULL。集合中最大的成员数为 2^32 - 1 (4294967295, 每个集合可存储40多亿个成员)。
当集合中最后一个元素移除之后，数据结构自动删除，内存被回收。
使用场景： 存储活动中奖的用户 ID，因为有去重功能，可以保证同一个用户不会中奖两次。另外还可以用在有交集，并集的需求上。
5. Sorted Set
常用命令： zadd/zrange/zrem/zcard等；
介绍： zset 可能是 Redis 提供的最为特色的数据结构，它也是在面试中面试官最爱问的数据结构。它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。
它的内部实现用的是一种叫做「<strong>跳跃表」的数据结构。使用跳跃表的结构可以获得比较高的查找效率
使用场景： zset 可以用来存粉丝列表，value 值是粉丝的用户 ID，score 是关注时间。我们可以对粉丝列表按关注时间进行排序。
zset 还可以用来存储学生的成绩，value 值是学生的 ID，score 是他的考试成绩。我们可以对成绩按分数进行排序就可以得到他的名次。
容器型数据结构的通用规则
list/set/hash/zset 这四种数据结构是容器型数据结构，它们共享下面两条通用规则：
- create if not exists 如果容器不存在，那就创建一个，再进行操作。比如 rpush 操作刚开始是没有列表的，Redis 就会自动创建一个，然后再 rpush 进去新元素。
- drop if no elements 如果容器里元素没有了，那么立即删除元素，释放内存。这意味着 lpop 操作到最后一个元素，列表就消失了
点关注 不迷路
以上就是这篇的全部内容，能看到这里的都是 <strong>人才。
如果你从本篇内容有收获，求 <strong>点赞，求 <strong>关注，求 <strong>转发 ，让更多的人看到。
如果本文有任何错误，请批评指教，不胜感激 ！
閱讀更多 不住隔壁的王老師 的文章
