摘要：字符串类型字符串是里非常常见的类型，而用实现的和不一样。实现了一个叫的字符串类型，其中有两个变量来分别代表字符串的长度和字符数组未使用的字符数量，这样就可以用的复杂度来获取字符串的长度了，而且同样也是使用空字符串作为结束符号。
起因
今天面试惨败，面试官问了不到10个问题就让我出来写题了……对其中的一个题目印象深刻：
Redis获取字符串长度的复杂度是多少？
刚开始我是一脸懵逼的，因为不清楚Redis的字符串类型是怎么实现的，所以完全没法答下去了……回来后马上开始学习。
字符串类型字符串是Redis里非常常见的类型，而用C实现的Redis和Java不一样。在C里字符串是用长度为N+1的字符数组实现的，且使用空字符串" "作为结束符号。获取字符串的长度需要遍历一遍，找到空字符串" "才知道字符串的长度，复杂度是O(N)。
如果有一个长度非常大的字符串，单线程的Redis获取它的长度就可能会阻塞很久，这是不能接受的，所以Redis需要一种更高效的字符串类型。
SDSRedis实现了一个叫SDS（simple dynamic string）的字符串类型，其中有两个变量来分别代表字符串的长度和字符数组未使用的字符数量，这样就可以用O(1)的复杂度来获取字符串的长度了，而且同样也是使用空字符串" "作为结束符号。
struct sdshdr {
// 字符串长度
int len;
// 字符数组未使用的字符数量
int free;
// 保存字符串的字符数组
char buf[];
}
现在已经可以回答上面的面试题了，其实是非常简单的一个问题，怪不得答不出来面试官马上就说面试结束了……
扩容机制SDS在字符数组空间不足于容纳新字符串的时候会自动扩容。
如果把一个C字符串拼接到一个SDS后面，当字符数组空间不足时，SDS会先扩容到刚好可以容纳新字符串的长度，然后再扩充新字符串的空字符长度，最终SDS的字符数组长度等于 2 * 新字符串 + 1（结束符号" "）。不过当新字符串的大小超过1MB后，扩充的空字符长度大小会固定为1MB。
之所以会有这个机制，是因为Redis作为一个NoSQL数据库，会频繁的修改字符串，扩容机制相当于给SDS做了一个缓冲池。把SDS连续增长N次字符串需要内存重分配N次优化成了SDS连续增长N次字符串最多需要内存重分配N次，这其实和Java里的StringBuilder实现思想是一样的。
后记这次翻车是有原因的，我看过两本关于Redis的书，里面都是讲Redis如何实战的但是并没有讲Redis的设计和实现。这也就导致了面试很尴尬，因为面试官最喜欢问原理相关的东西了，所以以后学习技术的时候不要从实战类的书籍开始了，还是先看懂原理比较好。
参考资料
这是《Redis设计与实现》里字符串一节的总结。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/37082.html
摘要：集合集合是等命令的操作对象它使用和两种方式编码中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是。 这篇 redis 学习笔记主要介绍 redis 的数据结构和数据类型，并讨论数据结构的选择以及应用场景的优化。 redis 是什么? Redis是一种面向键/值对类型数据的分布式NoSQL数据库系统，特点是高性能，持久存储，适应高并发的应用场景。 Redis 数据结构 动态字符...
摘要：集合集合是等命令的操作对象它使用和两种方式编码中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是。 这篇 redis 学习笔记主要介绍 redis 的数据结构和数据类型，并讨论数据结构的选择以及应用场景的优化。 redis 是什么? Redis是一种面向键/值对类型数据的分布式NoSQL数据库系统，特点是高性能，持久存储，适应高并发的应用场景。 Redis 数据结构 动态字符...
摘要：但为了提高存储效率与程序执行效率，每种对象的底层数据结构实现都可能不止一种。应该是新增的数据结构在中是没有的。 Redis 简介 REmote DIctionary Server(Redis) 是一个由SalvatoreSanfilippo写的key-value存储系统。 Redis是一个开源的使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、Key-V...
摘要：用指令来看一个值的数据结构。对象只有同时满足下面两个条件时，才会使用压缩列表哈希中元素数量小于个哈希中所有键值对的键和值字符串长度都小于字节。采用了链地址法的方法解决了哈希冲突的问题。数据类型的底层可以是整数集或者是散列表也叫哈希表。 前言 上篇文章 Redis闲谈（1）：构建知识图谱介绍了redis的基本概念、优缺点以及它的内存淘汰机制，相信大家对redis有了初步的认识。互联网的很...
摘要：用指令来看一个值的数据结构。对象只有同时满足下面两个条件时，才会使用压缩列表哈希中元素数量小于个哈希中所有键值对的键和值字符串长度都小于字节。采用了链地址法的方法解决了哈希冲突的问题。数据类型的底层可以是整数集或者是散列表也叫哈希表。 前言 上篇文章 Redis闲谈（1）：构建知识图谱介绍了redis的基本概念、优缺点以及它的内存淘汰机制，相信大家对redis有了初步的认识。互联网的很...
阅读 1597·2021-11-15 11:38
阅读 600·2021-10-09 09:58
阅读 523·2021-08-27 16:24
阅读 1588·2019-08-30 14:15
阅读 2259·2019-08-30 11:04
阅读 1933·2019-08-29 18:43
阅读 2054·2019-08-29 15:20
阅读 2477·2019-08-26 12:20
