29. Python 是怎么存储字符串的？

楔子

上一篇文章我们介绍了字符集，它是一系列字符组成的集合，但不同的字符集所能容纳的字符是有限的。于是为了能将全世界的字符统一起来，便诞生了 unicode。

unicode 字符集对世界上出现的所有字符都进行了系统的整理，包括各种 emoji，不管是哪个国家的语言，都可以使用 unicode 字符集。

print(ord("a"))  # 97
print(ord("憨"))  # 25000
print(ord("て"))  # 12390

不管什么文字，都可以用一个 unicode 来表示，它们在字符集中对应一个唯一的码点。所谓码点，就是字符在字符集中的索引，或者说唯一编号。

但是问题来了，unicode 能表示这么多的字符，占用的内存一定不低吧。的确，根据当时的编码，一个 unicode 字符最高会占用到 4 字节，因此对西方人来说就有点苦不堪言了，明明一个字节就够用了，为啥需要那么多。于是又出现了 utf-8，它是为 unicode 提供的一个新的编码规则，具有可变长的功能。不同种类的字符占用的大小不同，比如英文字符使用一个字节存储，汉字使用 3 个字节存储，emoji 使用 4 个字节存储。

但 Python 在表示 unicode 字符串时，使用的却不是 utf-8 编码，至于原因我们下面来分析一下。

unicode 的三种编码

从 Python3 开始，字符串使用的是 unicode。而根据编码的不同，unicode 的每个字符最大可以占用 4 字节，从内存的角度来说，这种编码有时会比较昂贵。为了减少内存消耗并且提高性能，Python 的内部使用了三种编码方式来表示 unicode。

Latin-1 编码：每个字符占 1 字节;
UCS2 编码：每个字符占 2 字节；
UCS4 编码：每个字符占 4 字节；

在 Python 编程中，所有字符串的行为都是一致的，而且大多数时候我们都没有注意到差异。然而在处理大文本的时候，这种差异就会变得异常显著，甚至有些让人出乎意料。为了看到内部表示的差异，我们看一下字符串所占的内存大小。

>>> sys.getsizeof("a")
50
>>> sys.getsizeof("憨")
76
>>> sys.getsizeof("😂")
80

我们看到都是一个字符，但它们占用的内存却是不一样的。因为 Python 面对不同的字符会采用不同的编码，进而导致大小不同。但需要注意的是，Python 的每一个字符串都需要额外占用至少 49 个字节，因为要存储一些元数据，比如：公共的头部、哈希、长度、字节长度、编码类型等等。

import sys

# 对于 ASCII 字符，一个占 1 字节，此时是 Latin-1 编码
print(sys.getsizeof("ab") - sys.getsizeof("a"))  # 1

# 对于汉字，日文等等，一个占 2 字节，此时是 UCS2 编码
print(sys.getsizeof("憨憨") - sys.getsizeof("憨"))  # 2
print(sys.getsizeof("です") - sys.getsizeof("で"))  # 2

# 像 Emoji，则是一个占 4 字节 ，此时是 UCS4 编码
print(sys.getsizeof("😂😂") - sys.getsizeof("😂"))  # 4

而采用不同的编码，底层结构体实例的元数据也会占用不同大小的内存。

# 所以一个空字符串占用 49 个字节
# 此时会采用占用内存最小的 Latin-1 编码
print(sys.getsizeof(""))  # 49
# 此时使用 UCS2
print(sys.getsizeof("憨") - 2)  # 74
# UCS4
print(sys.getsizeof("🍌") - 4)  # 76

如果编码是 Latin-1，那么结构体实例的元数据会占 49 个字节；编码是 UCS2，占 74 个字节；编码是 UCS4，占 76 个字节。然后字符串所占的字节数就等于：元数据 + 字符个数 * 单个字符所占的字节。

为什么不使用 utf-8 编码

上面提到的三种编码是 Python 在底层所使用的，但我们知道 unicode 还有一个 utf-8 编码，那 Python 为啥不用呢？

先来抛出一个问题，我们知道 Python 支持通过索引查找一个字符串指定位置的字符（注意不是字节），比如 s[2] 查找的就是字符串 s 中的第 3 个字符。

s = "古明地觉"
print(s[2])  # 地

那么问题来了，通过索引查找字符串的某个字符，时间复杂度为 O(1)，那么 Python 是怎么通过索引瞬间定位到指定字符的呢？显然是通过指针的偏移，用索引乘上每个字符占的字节数，得到偏移量，然后从头部向后偏移指定数量的字节即可，这样就能在定位到指定字符的同时还保证时间复杂度为 O(1)。

但是这需要一个前提：字符串中每个字符所占的大小必须是相同的，如果字符占的大小不同，比如有的占 1 字节、有的占 3 字节，显然就无法通过指针偏移的方式了。这个时候若还想准确定位的话，只能按顺序对所有字符都逐个扫描，但这样的话时间复杂度肯定不是 O(1)，而是 O(n)。

我们以 Go 为例，Go 字符串默认就是使用的 utf-8 编码。

package main

import "fmt"

func main() {
    s := "古明地觉"
    fmt.Println(s[2])  // 164
    fmt.Println(string(s[2]))  // ¤
}

惊了，我们看到打印的并不是我们希望的结果。因为 Go 底层使用的是 utf-8 编码，不同的字符可能会占用不同的字节。但 Go 通过索引定位的时间复杂度也是 O(1)，所以定位的时候是以字节为单位、而不是字符。在获取的时候也只会获取一个字节，而不是一个字符。

所以 s[2] 在 Go 里面指的是第 3 个字节，而不是第 3 个字符，而汉字在 utf-8 编码下占 3 个字节，所以 s[2] 指的就是汉字古的第三个字节。我们看到打印的时候，该字节的值为 164。

s = "古明地觉"
print(s.encode("utf-8")[2])  # 164

这就是采用 utf-8 编码带来的弊端，它无法让我们以 O(1) 的时间复杂度去准确地定位字符，尽管它在存储的时候更省内存。

Latin-1、UCS2、UCS4 该使用哪一种

Python 会使用 3 种编码来表示 unicode，所占字节大小分别是 1、2、4 字节。

因此 Python 在创建字符串的时候会先扫描，尝试使用占字节数最少的 Latin-1 编码存储，但是范围肯定有限。如果发现存储不下的字符，只能改变编码，使用 UCS2，然后继续扫描。但如果又发现 UCS2 也无法存储的字符，因为两个字节最多表示 65535 个不同的字符，那么会再次改变编码，使用 UCS4。UCS4 占四个字节，肯定能存下了。

一旦改变编码，字符串中的所有字符都会使用同样的编码，因为它们不具备可变长功能。比如字符串 "hello 古明地觉"，肯定都会使用 UCS2，不存在 "hello " 使用 Latin-1，"古明地觉" 使用 UCS2，因为一个字符串只能有一个编码。

当通过索引获取的时候，会将索引乘上每个字符占的字节数，这样就能跳到准确位置上，因为字符串的所有字符占的字节都是一样的，然后获取的时候也会获取指定的字节数。比如使用 UCS2 编码，那么定位到某个字符的时候，会取两个字节，这样才能表示一个完整的字符。

import sys

# 此时全部是 ascii 字符，那么 Latin-1 编码可以存储
# 所以结构体实例的元数据占 49 个字节
s1 = "hello"
# 有 5 个字符，一个字符一个字节，所以加一起是 54 个字节
print(sys.getsizeof(s1))  # 54

# 出现了汉字，那么 Latin-1 肯定存不下，于是使用 UCS2
# 所以结构体实例的元数据占 74 个字节
# 但是别忘了此时的英文字符也是 UCS2，所以也是一个字符两字节
s2 = "hello憨"
# 6 个字符，74 + 6 * 2 = 86
print(sys.getsizeof(s2))  # 86

# 这个牛逼了，UCS2 也存不下，只能 UCS4 存储了
# 所以结构体实例的元数据占 76 个字节
s3 = "hello憨🍌"
# 此时所有字符一个占 4 字节，总共 7 个字符
# 76 + 7 * 4 = 104
print(sys.getsizeof(s3))  # 104

除此之外，我们再举一个例子更形象地证明这个现象。

import sys

s1 = "a" * 1000
s2 = "a" * 1000 + "🍑"

# 我们看到 s2 只比 s1 多了一个字符
# 但是两者占的内存，s2 却将近是 s1 的 4 倍。
print(sys.getsizeof(s1))  # 1049
print(sys.getsizeof(s2))  # 4080

s2 和 s1 的差别只是 s2 比 s1 多了一个字符，但就是这么一个字符导致 s2 比 s1 多占了 3031 个字节。然而这 3031 个字节不可能是多出来的字符所占的大小，什么字符一个会占到三千多个字节，这是不可能的。

尽管如此，它也是罪魁祸首，但前面的 1000 个字符也是共犯。我们说 Python 会根据字符串选择不同的编码，s1 全部是 ASCII 字符，所以 Latin1 能存下，因此一个字符只占一个字节，所以大小就是 49 + 1000 = 1049。

对于 s2，Python 发现前 1000 个字符 Latin1 能存下，但不幸的是最后一个字符存不下，于是只能使用 UCS4。而字符串的所有字符只能有一个编码，为了保证索引查找的时间复杂度为 O(1)，前面一个字节就能存下的字符，也需要用 4 字节来存储，这是 Python 的设计策略。

而使用 UCS4，结构体的元数据会占 76 个字节，因此 s2 的大小就是 76 + 1001 * 4 = 4080。

# 74 + 7 * 2 = 88
>>> sys.getsizeof("爷的青春回来了") 
88

# 76 + 7 * 4 = 104
>>> sys.getsizeof("👴的青春回来了")
104

字符数量相同但是占用内存大小不同，相信原因你肯定能分析出来。

所以如果字符串中的所有字符都是 ASCII 字符，则使用 1 字节 Latin1 编码。Latin1 能表示前 256 个 unicode 字符，它支持多种拉丁语，如英语、瑞典语、意大利语、挪威语。但是它们不能存储非拉丁语言，比如汉语、日语、希伯来语、西里尔语。这是因为它们的码点（数字索引）定义在 1 字节（0 ~ 255）范围之外。

大多数自然语言的文字都采用 2 字节（UCS2）编码，但当字符串包含特殊符号、Emoji 或稀有语言时，则使用 4 字节（UCS4）编码。unicode 标准有将近 300 个块（范围），你可以在 0XFFFF 块之后找到 4 字节块。

假设我们有一个 10G 的 ASCII 文本，想把它加载到内存中，但如果在文本中插入一个表情符号，那么字符串的大小将增加 4 倍。这是一个巨大的差异，你可能会在实践当中遇到，比如处理 NLP 问题。

print(ord("a"))  # 97
print(ord("憨"))  # 25000
print(ord("😁"))  # 128513

所以最著名和最流行的 unicode 编码都是 utf-8，但 Python 不在内部使用它，而是使用 Latin1、UCS2、UCS4。至于原因我们上面已经解释的很清楚了，主要是字符串的索引是基于字符，而不是字节。

当一个字符串使用 utf-8 编码存储时，每个字符会根据自身选择一个合适的大小，这是一种存储效率很高的编码，但它有一个明显的缺点。由于每个字符的字节长度可能不同，就导致无法按照索引瞬间定位到单个字符，即便能定位，也无法定位准确。如果想准，那么只能逐个扫描所有字符。

假设要对使用 utf-8 编码的字符串执行一个简单的操作，比如 s[5]，就意味着解释器需要扫描每一个字符，直到找到需要的字符，这样效率是很低的。但如果是固定长度的编码就没有这样的问题，所以当 Latin1 存储的 "hello"，在和 UCS2 存储的 "古明地觉" 组合之后，整体每一个字符都会向大的方向扩展，变成 2 字节。

这样定位字符的时候，只需要将索引 * 2 便可计算出偏移的字节数，然后跳转该字节数即可。但如果原来的 "hello" 还是 1字节，而汉字是 2 字节，那么只通过索引是不可能定位到准确字符的，因为不同类型的字符的大小不同，必须要扫描整个字符串才可以。但是扫描字符串，效率又比较低，所以 Python 内部才会使用这个方法，而不是使用 utf-8。

因此对于 Go 来讲，如果想像 Python 一样，那么需要这么做：

package main

import "fmt"

func main() {
    s := "hello古明地觉"
    // 我们看到长度为 17，因为使用 utf-8 编码，并且 len 函数统计的是字节的数量
    fmt.Println(s, len(s))  // hello古明地觉 17
    
    // 如果想像 Python 一样，那么可以使用 Go 提供的 rune，相当于 int32
    // 此时每个字符均使用 4 个字节，所以长度变成了 9
    r := []rune(s)
    fmt.Println(string(r), len(r))  // hello古明地觉 9
    // 虽然打印的内容是一样的，但此时每个字符都使用 4 字节存储
    
    // 此时跳转会偏移 5 * 4 个字节，然后获取也会获取 4 个字节，因为一个字符占 4 个字节
    fmt.Println(string(r[5]))  // 古
}

由于 utf-8 编码的 unicode 字符串里面的字符可能占用不同的字节，显然没办法实现 Python 字符串的索引查找效果，因此 Python 没有使用 utf-8 编码。

Python 的做法是让字符串的所有字符都占用相同的字节，先使用占用内存最少的 Latin1，不行的话再使用 UCS2，还不行则使用 UCS4。但不管使用哪种编码，都会确保每个字符占用的字节是一样的。至于原因上面分析的很透彻了，因为无论是索引还是切片，还是计算长度等等，都是基于字符来的，显然这也符合人类的思维习惯。

小结

以上就是 Python 字符串的存储策略，它并没有使用最为流行的 utf-8，归根结底就在于这种编码不适合 Python 字符串。当然，我们在将字符串转成字节序列的时候，一般使用的都是 utf-8 编码。

下一篇文章来介绍字符串的底层实现，看看字符串在底层是如何设计的。

欢迎大家关注我的公众号：古明地觉的编程教室。

如果觉得文章对你有所帮助，也可以请作者吃个馒头，Thanks♪(･ω･)ﾉ。

CPython3.8 源码探秘

楔子

unicode 的三种编码

为什么不使用 utf-8 编码

Latin-1、UCS2、UCS4 该使用哪一种

小结