Python的基本数据结构包括：列表（list），元组（tuple），字典（dict），集合（set）。
基本数据结构
- 列表是动态的，长度大小不固定，可以随意增/删/修元素
- 元组是静态的，长度大小固定，无法增/删/修元素
- 相对于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成
- 集合和字典基本相同，区别是集合没有键和值的配对，是一系列无序的、唯一的元素集合
列表和元组
列表和元组存储方式的差异：列表的存储空间比元祖更大(16字节)，主要包括两个部分：存储指针，指向对应元素（8字节）；存储已经分配的长度大小（8字节），方便实时追踪列表空间的使用情况，当空间不足时，及时分配额外空间。
1 2 3 4 5 6 7
l = [1, 2, 3] t = tuple(l) print(t.__sizeof__()) print(l.__sizeof__()) #+RESULTS: : 48 : 64
列表的over-allocating机制：列表在
append进行元素扩充时，为了减小每次增加/删减操作时空间分配的开销，其在每次分配空间时都会额外多分配一些，保证其操作的高效性：增加/删除的时间复杂度都为O(1)。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
l = [] print(l.__sizeof__()) # 空列表的存储空间为40字节 l.append(1) print(l.__sizeof__()) # 加入元素1,列表额外分配了4个元素的空间: size为72 l1 = [1] print(l1.__sizeof__()) # 初始化的列表不会额外分配：size为48 l.append(2) l.append(3) l.append(4) print(l.__sizeof__()) # 存储空间没有超出，size为72 l.append(5) print(l.__sizeof__()) # 存储空间超出，再次分配4个元素的空间：size为104 #+RESULTS: : 40 : 72 : 48 : 72 : 104
列表和元组的性能对比：相对于列表，元组属于更轻量级的数据结构，其性能速度更优。另外，Python的垃圾回收机制（后续会讲），在对待一些静态变量，如元组，当其不被使用且占用空间不大时，Python会暂时缓存该部分内存。因此当下次重新创建同样大小的内存时，Python便不会发送寻找内存的请求，能够加快程序的运行速度。对于索引操作，两者差距很小
1 2 3 4 5 6 7 8 9
python3 -m timeit 'x = (1,2,3,4,5,6)' python3 -m timeit 'x = [1,2,3,4,5,6]' python3 -m timeit 'x = (1,2,3,4,5,6)' 'y=x[3]' 'x = [1,2,3,4,5,6]' python3 -m timeit 'x = [1,2,3,4,5,6]' 'y=x[3]' 'x = (1,2,3,4,5,6)' #+RESULTS: : 20000000 loops, best of 5: 14.6 nsec per loop : 5000000 loops, best of 5: 57.9 nsec per loop : 5000000 loops, best of 5: 79.9 nsec per loop : 5000000 loops, best of 5: 80.1 nsec per loop
字典和集合
- 字典和集合的工作原理：
初始化操作 字典和集合的内部结构都是一张哈希表，只是字典多了键/值。但是为了更好的空间利用率，哈希表会将索引和哈希值、键、值单独分开：
Indices(稀疏)：
None index None None index None … Entries（不稀疏）：
hash0 key0 value0 hash1 key1 value1 hash2 key2 value2 - 插入操作 当向字典/集合插入一个元素时，Python会首先计算键的Hash值，然后和mask值（mask=PyDicMinSize - 1）做与操作：index=hash(key) & mask。index值存储的是Hash值表的位置。如果Index表中该位置为空，则该元素就会被插入其中。 如果该值被占用，则Python会比较两个元素的哈希值和键值是否相等：
- 如果两者都相等，则表明该元素已经存在，如果值不同，则更新值。
- 如果两者有一个不相等，则出现“哈希冲突”，即两者键不相等，但是哈希值相，最简单基于线性查找/二次查找寻找空位（内部实现当然会优化，这里不关心）
- 查找操作 直接基于哈希值找到Index表的位置，然后对应找到数据位置；然后，比较哈希表位置中元素的哈希值和键，如果相等直接返回；否则继续查找，直到找到或者抛出异常。
- 删除操作 删除操作，Python会暂时对该位置的元素赋予一个特殊的值（作标记），等到重新调整哈希表大小时，再将其删除。这样操作主要还是为了节省操作时间。 为了保证其高效性，字典和集合内的哈希表，通常会保证至少留有1/3的剩余空间。随着元素的不断插入，当剩余空间少于1/3时，Python会重新获取更大的内存空间，进行哈希表的扩充。这种情况下，表内的所有元素都会被重新排放。