极客时间已完结课程限时免费阅读

14 | 答疑（一）：列表和元组的内部实现是怎样的？

14 | 答疑（一）：列表和元组的内部实现是怎样的？-极客时间

14 | 答疑（一）：列表和元组的内部实现是怎样的？

2019-06-10 景霄 来自北京
《Python核心技术与实战》
课程介绍

讲述：冯永吉

时长06:47大小5.43M

你好，我是景霄。
转眼间，专栏上线已经一个月了，而我们也在不知不觉中完成了第一大章基础篇的学习。我非常高兴看到很多同学一直在坚持积极地学习，并且留下了很多高质量的留言，值得我们互相思考交流。也有一些同学反复推敲，指出了文章中一些表达不严谨或是不当的地方，我也表示十分感谢。
大部分留言，我都在相对应的文章中回复过了。而一些手机上不方便回复，或是很有价值很典型的问题，我专门摘录了出来，作为今天的答疑内容，集中回复。

问题一：列表和元组的内部实现

第一个问题，是胡峣同学提出的，有关列表（list）和元组（tuple）的内部实现，想知道里边是 linked list 或 array，还是把 array linked 一下这样的方式？
关于这个问题，我们可以分别从源码来看。
先来看 Python 3.7 的 list 源码。你可以先自己阅读下面两个链接里的内容。
listobject.h：https://github.com/python/cpython/blob/949fe976d5c62ae63ed505ecf729f815d0baccfc/Include/listobject.h#L23
listobject.c: https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Objects/listobject.c#L33
我把 list 的具体结构放在了下面：
可以看到，list 本质上是一个 over-allocate 的 array。其中，ob_item 是一个指针列表，里面的每一个指针都指向列表的元素。而 allocated 则存储了这个列表已经被分配的空间大小。
需要注意的是，allocated 与列表实际空间大小的区别。列表实际空间大小，是指 len(list) 返回的结果，即上述代码注释中的 ob_size，表示这个列表总共存储了多少个元素。实际情况下，为了优化存储结构，避免每次增加元素都要重新分配内存，列表预分配的空间 allocated 往往会大于 ob_size（详见正文中的例子）。
所以，它们的关系为：allocated >= len(list) = ob_size。
如果当前列表分配的空间已满（即 allocated == len(list)），则会向系统请求更大的内存空间，并把原来的元素全部拷贝过去。列表每次分配空间的大小，遵循下面的模式：
0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
我们再来分析元组。下面是 Python 3.7 的 tuple 源码，同样的，你可以先自己阅读一下。
tupleobject.h： https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Include/tupleobject.h#L25
tupleobject.c：https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Objects/tupleobject.c#L16
同样的，下面为 tuple 的具体结构：
你可以看到，它和 list 相似，本质也是一个 array，但是空间大小固定。不同于一般 array，Python 的 tuple 做了许多优化，来提升在程序中的效率。
举个例子，当 tuple 的大小不超过 20 时，Python 就会把它缓存在内部的一个 free list 中。这样，如果你以后需要再去创建同样的 tuple，Python 就可以直接从缓存中载入，提高了程序运行效率。

问题二：为什么在旧哈希表中，元素会越来越稀疏？

第二个问题，是 Hoo 同学提出的，为什么在旧哈希表中，元素会越来越稀疏？
我们可以先来看旧哈希表的示意图：
--+-------------------------------+
| 哈希值 (hash) 键 (key) 值 (value)
--+-------------------------------+
0 | hash0 key0 value0
--+-------------------------------+
1 | hash1 key1 value1
--+-------------------------------+
2 | hash2 key2 value2
--+-------------------------------+
. | ...
__+_______________________________+
你会发现，它是一个 over-allocate 的 array，根据元素键（key）的哈希值，来计算其应该被插入位置的索引。
因此，假设我有下面这样一个字典：
{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}
那么这个字典便会存储为类似下面的形式：
entries = [
['--', '--', '--']
[-230273521, 'dob', '1999-01-01'],
['--', '--', '--'],
['--', '--', '--'],
[1231236123, 'name', 'mike'],
['--', '--', '--'],
[9371539127, 'gender', 'male']
]
这里的’---‘，表示这个位置没有元素，但是已经分配了内存。
我们知道，当哈希表剩余空间小于 1/3 时，为了保证相关操作的高效性并避免哈希冲突，就会重新分配更大的内存。所以，当哈希表中的元素越来越多时，分配了内存但里面没有元素的位置，也会变得越来越多。这样一来，哈希表便会越来越稀疏。
而新哈希表的结构，改变了这一点，也大大提高了空间的利用率。新哈希表的结构如下所示：
Indices
----------------------------------------------------
None | index | None | None | index | None | index ...
----------------------------------------------------
Entries
--------------------
hash0 key0 value0
---------------------
hash1 key1 value1
---------------------
hash2 key2 value2
---------------------
...
---------------------
你可以看到，它把存储结构分成了 Indices 和 Entries 这两个 array，而’None‘代表这个位置分配了内存但没有元素。
我们同样还用上面这个例子，它在新哈希表中的存储模式，就会变为下面这样：
indices = [None, 1, None, None, 0, None, 2]
entries = [
[1231236123, 'name', 'mike'],
[-230273521, 'dob', '1999-01-01'],
[9371539127, 'gender', 'male']
]
其中，Indices 中元素的值，对应 entries 中相应的索引。比如indices中的1，就对应着entries[1]，即’'dob': '1999-01-01'‘。
对比之下，我们会清晰感受到，新哈希表中的空间利用率，相比于旧哈希表有大大的提升。

问题三：有关异常的困扰

第三个问题，是“不瘦到 140 不改名”同学提出的，对“NameError”异常的困惑。这是很常见的一个错误，我在这里也解释一下。
这个问题其实有点 tricky，如果你查阅官方文档，会看到这么一句话”When an exception has been assigned using as target, it is cleared at the end of the except clause. ”
这句话意思是，如果你在异常处理的 except block 中，把异常赋予了一个变量，那么这个变量会在 except block 执行结束时被删除，相当于下面这样的表示：
e = 1
try:
1 / 0
except ZeroDivisionError as e:
try:
pass
finally:
del e
这里的 e 一开始指向整数 1，但是在 except block 结束时被删除了（del e），所以程序执行就会抛出“NameError”的异常。
因此，这里提醒我们，在平时写代码时，一定要保证 except 中异常赋予的变量，在之后的语句中不再被用到。

问题四：关于多态和全局变量的修改

最后的问题来自于 farFlight 同学，他提了两个问题：
Python 自己判断类型的多态和子类继承的多态 Polymorphism 是否相同？
函数内部不能直接用 += 等修改全局变量，但是对于 list 全局变量，却可以使用 append、extend 之类修改，这是为什么呢?
我们分别来看这两个问题。对于第一个问题，要搞清楚多态的概念，多态是指有多种不同的形式。因此，判断类型的多态和子类继承的多态，在本质上都是一样的，只不过你可以把它们理解为多态的两种不同表现。
再来看第二个问题。当全局变量指向的对象不可变时，比如是整型、字符串等等，如果你尝试在函数内部改变它的值，却不加关键字 global，就会抛出异常：
x = 1
def func():
x += 1
func()
x
## 输出
UnboundLocalError: local variable 'x' referenced before assignment
这是因为，程序默认函数内部的 x 是局部变量，而你没有为其赋值就直接引用，显然是不可行。
不过，如果全局变量指向的对象是可变的，比如是列表、字典等等，你就可以在函数内部修改它了：
x = [1]
def func():
x.append(2)
func()
x
## 输出
[1, 2]
当然，需要注意的是，这里的x.append(2)，并没有改变变量 x，x 依然指向原来的列表。事实上，这句话的意思是，访问 x 指向的列表，并在这个列表的末尾增加 2。
今天主要回答这些问题，同时也欢迎你继续在留言区写下疑问和感想，我会持续不断地解答。希望每一次的留言和答疑，都能给你带来新的收获和价值。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 48

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
13 | 搭建积木：Python 模块化
下一篇
15 | Python对象的比较、拷贝
unpreview
 写留言

精选留言(24)

  • 夜路破晓
    2019-06-10
    个人认知：感觉会看源码的人都很牛！我也想成人牛人，那么问题来了： 如何学习看源码？

    作者回复: 根据需求，首先了解每一个block，每一个函数的大概意思，然后看下去，不懂的多去google一下，看多了你的水平自然就提高了

    共 5 条评论
    73
  • SCAR
    2019-06-10
    对于问题四的2而言，是因为python是动态语言，不要求声明变量，但是约定在函数体中赋值的变量是局部变量，所以需要理解的是“赋值”这个动作，不管是常规的完整赋值或是增强赋值，只有函数体内初次出现赋值就认为定义了局部变量。这样你就很好理解了，老师的例子中x+=1，出现了赋值，那么这个x就是局部变量了，而x+=1这个增强赋值的第二步会去找函数体内x的引用，于是就出现了找不到的错误。如果把x+=1改成print(x),则是打印出1，因为函数体没出现赋值，那么这个x是最上面赋值的x，它是全局的。
    展开
    共 8 条评论
    59
  • 阿卡牛
    2019-06-10
    over-allocate是什么意思

    作者回复: 会分配比实际元素多的空间，比如一个array实际有5个元素，但是如果是over-allocate的array，可能会分配10个元素的空间大小

    共 2 条评论
    17
  • yshan
    2019-06-10
    重新查了下理解了下多态：多态就是多种形态。 有了继承，才有多态了。 继承了就具有父类的方法，然后子类就能够覆写父类方法，子类就能够调用该方法实现自己的需求。
    10
  • 小侠龙旋风
    2019-06-13
    1.细看了over-allocated分配空间大小的增长规律，4 4 8 9 10 11 12...不知道这样设计的缘由。 2."当tuple的大小不超过20时，Python会把它缓存在内部的一个free list中。"这句话突然让我想起了小整数池。 小整数池的概念：Python提前建立好范围在[-5, 256]的整数对象，且不会被垃圾回收。无论这个整数处于LEGB中的哪个位置，所有位于这个范围内的整数使用的都是同一个对象。 主要目的是为了避免频繁申请和销毁小整数的内存空间，提高程序的运行效率。 3.说一下我所理解的新哈希表的设计思想： indice下标，entry入口。用下标去寻找对应元素。 维护一个数据量较小的结构，去访问一个数据量较大的结构。 同理，也被运用于函数： 函数的本质是在堆Heap中放置的对象； 函数名的本质是放在栈Stack中的地址，指向堆中放置的对象。 以上，思维比较发散，说得不对还望指出。
    展开
    9
  • 18646333118
    2019-06-11
    辛苦老师，希望能用更通俗的语言或者例子来帮助我们这帮菜鸟理解哈哈，有的时候感觉老师明白，但是编辑成文字总是差一点 哈
    5
  • xavier
    2019-07-11
    对于我这种野生程序员来说，收获颇多。每一篇都是从基础开始，然后循序渐进。感谢老师！
    3
  • Geek_d848f7
    2019-06-10
    老师，原谅我还是不太理解这2点吧 1. 列表分配大小时，遵循下面模式：0、4、8…，我看源代码的确这样，但是怎么算都对不上，求指导； 2. 哈希的存储怎么知道是如图形式呢？尤其是无元素位置，这个位置为啥要分配呢？
    3
  • 隰有荷
    2019-08-23
    不太明白为什么新哈希表的结构是 Indices None | index | None | None | index | None | Entries 这种形式? None和index的排列有什么规则吗？为什么会有None?
    展开
    共 2 条评论
    2
  • 瞳梦
    2019-07-08
    list的append()并不是一个赋值操作，不会去定义新的变量。而是会根据LEGB规则去寻找list这个变量。
    2
  • KaitoShy
    2019-06-10
    怎么得上面的存储方式的？和hash存储有关么？还是python实现的造成的？
    1
  • 程序员人生
    2019-06-10
    想问一下Mr King，问题3我在pycharm中执行了一下没报错啊？
    1
  • me
    2022-09-13 来自四川
    x = 1 def func(): x += 1 func() 报错,分析原因: (从两个角度分析) 1> 从右往左 先要明白赋值操作的一个概念, 被赋值=被引用； 再来看函数体内的 x += 1, 本质上就是x = x + 1 (扩展一下,若x是列表 x+=[1] 等同于 x.extend() 原地改变, 但放在此处依旧会报错, 报错原因于 x+=1同理) 继续分析, x = x + 1，右边的x变量在函数体里没有找到(在函数体里没有定义此变量),就去全局作用域里找, 找到啦, 右边的值最终为2.. 重点来了, 记住python在作用域里对变量的赋值操作规则, 在函数体内,若对某一变量未定义,对其赋值视为在函数体里定义了该变量; 在函数体内,若对某一变量已经定义,对其赋值视为修改该变量的值; 这里左边的x变量在函数体里未定义,那么按照规则会定义一个局部变量x,但右边的x是全局变量... 冲突了. 2> 从左往右 根据报错的角度分析 是因为函数体里无x变量,赋值操作是定义该x变量,而赋值语句中又有还没有定义好的x变量)
    展开
    1
  • Geek_145846
    2022-04-25
    想学学Python 没想到还要重新拾起 C ++，学海无涯苦作舟的感觉 哭
  • 独一无二
    2022-02-22
    如果当前列表分配的空间已满（即 allocated == len(list)），则会向系统请求更大的内存空间，并把原来的元素全部拷贝过去。 这里有个疑问？给列表分配的内存是一块连续的内存空间吗？
  • Jaden~お張嘉楽
    2021-05-18
    总结一下刚才那个问题答案： １．a = 1 a为不可变数据类型　函数体里　a+=1　此时的a 为局部变量，而此时执行 a +=1 时，重新复制给新a 但是新a， 找不到所在内存中的位置，所以报错了 ２．b = [] b为可变的数据类型　函数体内　b.append(1) 　此时b为全局的[] 所有执行函数体内append 是可以的
    共 1 条评论
  • lcqbug
    2021-04-30
    t1 = (1,2) t2 = (1,2) print(t1 is t2) 在cmd黑窗口中结尾为False 在pycharm中为True 这是为什么呢
    展开
    共 2 条评论
  • Alery
    2019-11-22
    问题四的第二个问题，全局列表x之所以可以在函数中x.append是因为，x指向的列表不变，但是如果列表中的元素超过了列表预留的空间就会重新开启一个更大的列表x指向这个新的列表，这个时候x不也变了吗？为什么还能在函数中使用？
  • 追风筝的人
    2019-10-27
    Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. class Solution: def isPalindrome(self, x: int) -> bool: if (x>=0): return x==int(str(x)[::-1]) else : return False 老师 int(str(x)[::-1]) 这一行可以解释下具体意思吗 从后向前读取元素 最后要把string类型转为int类型 吗？
    展开
  • 追风筝的人
    2019-10-27
    class Solution: def isPalindrome(self, x: int) -> bool: return str(x) == str(x)[::-1] 老师：str(x) == str(x)[::-1] 两个::是什么意思
    共 2 条评论