点击
上方蓝字
，快速关注我们）
编译：伯乐在线 - 耶鲁怕冷
http://python.jobbole.com/83732/
如有好文章投稿，请点击 → 这里了解详情
相关阅读：《
深入 Python 列表的内部实现
》《
深入 Python 字典的内部实现
》
本文介绍了 python 内部是如何管理字符串对象，以及字符串查找操作是如何实现的。
PyStringObject 结构体
Python 中的字符串对象在内部对应一个名叫 PyStringObject 的结构体。“ob_shash” 对应字符串经计算过的 hash值， “ob_sval” 指向一段长度为 “ob_size” 的字符串，且该字符串以‘null’结尾（为了兼容C）。“ob_sval”的初始大小为1个字节，且 ob_sval[0]=0（对应空字符串）。若你还想知道“ob_size”被定义的位置，可以看一看 object.h 头文件中 PyObject_VAR_HEAD 对应部分。“ob_sstate” 用来指示某个字符串是否已经存在于intern机制对应的字典中，后面我们会再次提到这一点。
typedef
struct
{
PyObject_VAR_HEAD
long
ob_shash
;
int
ob_sstate
;
char
ob_sval
[
1
];
}
PyStringObject
;
字符串对象的创建
如下所示，当将一个新的字符串赋给一个变量时，发生了什么？
1>>> s1 = 'abc'
运行以上代码时，内部的 C 函数 “PyString_FromString” 将被调用并生成类似下面的伪代码：
arguments
:
string
object
:
'abc'
returns
:
Python string
object
with
ob_sval
=
'abc'
PyString_FromString
(
string
)
:
size
=
length of string
allocate string
object
+
size
for
'abc'
.
ob_sval will be of
size
:
size
+
1
copy
string
to ob_sval
return
object
每次用到新的字符串时，都将分配一个字符串对象。
共享字符串对象
Python 有一个优雅的特性，就是变量之间的短字符串是共享的，这一特性可以节省所需的内存空间。短字符串就是那些长度为 0 个或者 1 个字节的字符串。而全局变量 “interned” 对应一个用于索引这些短字符串的字典。数组 “characters” 也可用于索引那些长度为 1 个字节的字符串，比如单个字母。后面我们将看到数组 “characters” 是如何被使用的。
static
PyStringObject
*
characters
[
UCHAR_MAX
+
1
];
static
PyObject
*
interned
;
下面一起看看：当你在 Python 脚本中将一个短字符串赋值给一个变量时，背后发生了哪些事情。
static
PyStringObject
*
characters
[
UCHAR_MAX
+
1
];
static
PyObject
*
interned
;
内容为 ‘a’ 的字符串对象将被添加到 “interned” 字典中。字典中键（key）是一个指向该字符串对象的指针，而对应的值 就是一个相同的指针。在数组 “characters” 中，这一新的字符串对象在偏移量为 97 的位置被引用，因为字符 ‘a’ 的ASCII码值便是 97。变量 “s2” 也指向了这一字符串对象。
而，当另外一个变量也被相同的字符串 ‘a’ 赋值时，又会如何呢？
1>>> s3 = 'a'
上述代码执行后，将返回之前已创建的内容相同的字符串对象。因此，‘s1’ 和 ‘s3’ 两个变量都将指向同一个字符串对象。 数组 “characters” 便是用于检测字符串 ‘a’ 是否已经存在，若存在，则返回指向该字符串对象的指针。
if
(
size
==
1
&&
(
op
=
characters
[
*
str
&
UCHAR_MAX
])
!=
NULL
)
{
...
return
(
PyObject
*
)
op
;
}
下面我们新建一个内容为 ‘c’ 的短字符串：
1>>> s4 = 'c'
那么，我们将得到如下结果：
我们还能发现，当按照下面 Python 脚本中的方式对一个字符串元素进行访问时，数组 “characters” 仍有用武之地。
>>>
s5
=
'abc'
>>>
s5
[
0
]
'a'
上面第二行代码中，返回的是数组 “characters” 偏移量为 97 的位置内的指针元素，而非新建一个值为 ‘a’的字符串。当我们访问某个字符串中的元素时，一个名叫 “string_item” d的函数将被调用，下方给出了函数体代码。其中，参数 ‘a’ 便对应着字符串 “abc”，而参数 ‘i’ 便是访问数组的索引值（本例中便为 0 ），函数返回的是指向某个字符串对象的指针。
static
PyObject
*
string_item
(
PyStringObject
*
a
,
register
Py_ssize
_
t
i
)
{
char
pchar
;
PyObject
*
v
;
...
pchar
=
a
->
ob_sval
[
i
];
v
=
(
PyObject
*
)
characters
[
pchar
&
UCHAR_MAX
];
if
(
v
==
NULL
)
//
allocate
string
else
{
...
Py_INCREF
(
v
);
}
return
v
;
}
数组 “characters” 也可用于函数名长度为 1 时的情形，如下所示：
>>> def a(): pass
字符串查找
下面看看，当你在如下 Python 代码中进行字符串查找操作时，又会有那些事情发生呢？
>>>
s
=
'adcabcdbdabcabd'
>>>
s
.
find
(
'abcab'
)
>>>
11
函数 “find” 返回一个索引值，说明是在字符串 “abcd” 的哪个位置找到字符串 “s” 的。若字符串未找到，函数返回值为 -1。
那么，内部到底干了些啥事情？内部调用了一个名为 “fastsearch” 的函数。这个函数是一个介于 BoyerMoore 和 Horspool 算法之间的混合版本，它兼具两者的优良特性。
我们将 “s”（s = ‘adcabcdbdabcabd’）称作主字符串，而将 “p”（p = ‘abcab’）称作模式串。n 和 m 分别表示字符串 s 和 字符串 p 的长度，其中，n = 15, m = 5。
在如下代码段中，明显看到，程序将进行首次判定：若 m > n,我们就知道必然不能找到这样的索引号，因此函数直接返回 -1 即可。
w
=
n
-
m
;
if
