字符串横向对比：C、Golang、Redis

C语言中的字符串

C语言的字符串是通过字符数组实现的，每个字符串以'\0'结束。C语言字符串的三大操作函数也是常见笔试题。

int strlen(char *s) {
	char *p = s;
	while (*p != '\0')
		p++
	return p -s;
}

void strcpy(char *s, char *t) {
	int i;
	i = 0;
	while ((s[i] = t[i]) != '\0')
		i++;
}

void strcmp(char *s, char *t) {
	for ( ; *s == *t; s++, t++)
		if (*s == '\0')
			return 0;
	return *s - *t;

}

具体实现的方式为就不说了，主要说说这里的问题。

• 在计算字符串长度的时候，每次都是需要遍历整个数组，直到'\0'为止，时间复杂度是O(n)，如果字符串较长，性能还是会受到影响；
• 在字符串复制的时候，有可能会导致越界。如果此时的内存结构是：

要给前面的一个字符串a赋值abc，那么结果就是后面紧跟着的字符串b也会被修改；

• 字符串相加的时候，也有可能会引起越界的问题。

Golang的字符串

在Golang1.5之前，底层代码是用C语言写的。Golang1.5实现了自举，这个我还不懂是怎么具体实现的，就说1.4的。字符串不再像C语言那样用比较简易的字符数组实现，而是封装了字符串类型string。

struct String
{
	byte* str;
	intgo len;
}

• 这里定义了一个结构体，包含str和len字段。新增的len字段用于保存字符串长度。这样计算字符串长度的时间复杂度就是O(1)，用空间换取了时间性能。
• 字符串数据依然是用数组存储，但是由于有了len字段存储长度，所以不再需要'\0'来表示结束了。
• 字符串的赋值就是指针指向对象的变化，不会有赋值操作，这样就不会导致越界问题了。
• 如果两个字符串相加，操作方案是重新申请内存，保存相加的两个字符串相加的结果，这样也不会导致越界。
• 但是还不是很完美，字符串是常量，不能通过数据下标的方式访问和修改。每次修改字符串，需要将字符串转换成[]byte数组。这样修改完之后，再转成字符串，这个字符串和之前的字符串已经不是同一个变量了。
• 字符串相加操作也是，任何修改都会导致重新申请内存，时间复杂度是O(m+n)。Golang字符串修改一般是用copy或者bytes包的bytes.WriteString实现。

Redis的字符串

Redis是用C语言开发的，Redis支持字符串保存数据。它肯定不会用字符数组来做字符串实现。。。它开发了一个叫做简单动态字符串（simpledynamic string，SDS）的类型来实现字符串。定义的结构体如下：

struct sdshdr {    
	// 记录buf数组中已使用字节的数量    
	// 等于SDS所保存字符串的长度，用空间解决时间问题
	int len;    
	// 记录buf数组中未使用字节的数量。用于避免缓冲区溢出，如果当前空间不够，则再分配一个符合大小的空间  
	int free;   
	// 字节数组，用于保存字符串。用这个是为了和C语言字符串兼容
	char buf[];
};

• 和Golang的实现相比，除了长度字段len和保存内容的数组buf。计算字符串长度的时间复杂度是O(1)。
• Redis是用C语言开发的，为了和C语言兼容，buf是C语言的字符串，以'\0'结束。
• 它还增加了free字段表示空闲空间（别的类似实现可能是用容量字段，都差不多）。为了解决像Golang实现那样对于写操作不友好的问题，它会初始化一个较大的内存空间，字符串的增加会写入这些提前准备好的空间里面。一旦用完free的内容，就给buf追加空间。当追加空间的时候，性能会降到和Golang差不多的性能，一般情况还是很好的。

参考文献

1. How to efficiently concatenate strings in Go? - stackoverflow

原文链接：字符串横向对比：C、Golang、Redis，转载请注明来源！