python中list,set,dict,tuple底层实现细节
1. list
python中的列表的英文名是list，因此很容易和其它语言(C++, Java等)标准库中常见的链表混淆。事实上CPython的列表根本不是列表（可能换成英文理解起来容易些：python中的list不是list）。在CPython中，列表被实现为长度可变的数组。
从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数过分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。
不幸的是，在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。
利用 list.insert方法在任意位置插入一个元素——复杂度O(N)
利用 list.delete或del删除一个元素——复杂度O(N)
python没有数组，有列表，列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这就意味着每次进行增删操作都需要对数组的大小进行重新分配。这样的结构在对列表进行操作时的时间复杂度会很高。为了避免这种情况，这里要引入分配槽的概念，分配槽的大小不等同于列表大小，分配槽大小是指在内存中已经分配了的槽空间数。这样能避免每次列表添加数据都调用分配函数，这样均摊的时间复杂度就会比较低。增长模式为：0，4，8，16，25，35，46，58，72，88……。所以python实现队列并对队列进行操作时，与正常数组实现的队列不大一样（因为我的开发语言是python所以有时会对python一些特性进行分析）
要分清列表大小和分配的槽大小，这很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小，这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。
append()
向列表添加一个整数：l.append(1) 时发生了什么？调用了底层的 C 函数 app1()。
下面是 list_resize() 函数。它会多申请一些内存，避免频繁调用 list_resize() 函数。列表的增长模式为：0，4，8，16，25，35，46，58，72，88……
python的这个值是怎么来的呢
So just checking very quickly, Ruby (1.9.1-p129) appears to use 1.5x when appending to an array, and Python (2.6.2) uses 1.125x plus a constant: (in Objects/listobject.c):
换个说法，每当来了一个新要求的大小（比如插入操作中的原大小+1,或删除操作中原大小-1）：newsize，这时python并不直接对list的空间进行调整。而是作个比较，若新要求的大小在总容量之下，总容量的一半之上则，不进行调整。现在分配了 4 个用来装列表元素的槽空间，并且第一个空间中为整数 1。如下图显示 l[0] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。
列表追加元素操作的平均复杂度为 O(1)。
继续添加新的元素：l.append(2)。调用 list_resize 函数，参数为 n+1 = 2， 但是因为已经申请了 4 个槽空间，所以不需要再申请内存空间。再添加两个整数的情况也是一样的：l.append(3)，l.append(4)。下图显示了我们现在的情况。
insert()
在列表偏移量 1 的位置插入新元素，整数 5：l.insert(1,5)，内部调用ins1() 函数。
虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 8 个槽空间，但是列表的大小却只是 5。
列表插入操作的平均复杂度为 O(n)。
pop()
取出列表最后一个元素 即l.pop()，调用了 listpop() 函数。在 listpop() 函数中会调用 list_resize 函数，如果取出元素后列表的大小小于分配的槽空间数的一半，将会缩减列表的大小。
列表 pop 操作的平均复杂度为 O(1).
可以看到 pop 操作后槽空间 4 依然指向原先的整数对象，但是最为关键的是现在列表的大小已经变为 4。
继续 pop 一个元素。在 list_resize() 函数中，size – 1 = 4 – 1 = 3 已经小于所分配的槽空间大小的一半，所以缩减分配的槽空间为 6，同时现在列表的大小为 3。
可以看到槽空间 3 和 4 依然指向原先的整数，但是现在列表的大小已经变为 3。
再从缩小来看，当newsize小于allocated/2时，意味着需要缩小空间大小了（节约内存）。
该缩小多少呢，同样是基于上面那个函数。由它计算出一个增量来，在什么基础上增呢？allocated/2，对就是在这个基础上，因为一旦由于删除操作导致newsize恰好小于allocated/2时，就会执行缩小list空间大小的操作。这样，即节省了内存，又不至于减少内存过少，导致效率降低（想像一下，如果每次小于allocated/2时，就缩小为allocated/2，那么如果对于那么删除后立即执行插入操作效率就很不理想了。）
以上这个策略，可以实现不会过去频繁地调用realloc这个低效率的函数。
对比tuple
列表是python中简单而重要的数据结构 list_sample = [1, 2, 3]
超预分配的量大概只有总量的八分之一，保证不太浪费的情况下，也有线性的摊分复杂度。
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
当增加或删除都有可能引起allocated的变化，当目前的allocated满足 allocated >= newsize && newsize >= (allocated >> 1) 这个关系时，allocated不变，不然更新分配值 allocated = new_allocated + newsize
由于python列表中的元素可以是任意的对象。 在底层实现上，由于对象大小未知，并不能像数组那样连续排在内存里。python列表维护了一个指针数组，每个指针指向不同的对象， 这也造成了一些弊端，例如列表中对象大小一样的时候就很亏了，浪费空间不说，跟C的数组相比，它离散的对象位置不能很好地利用CPU高速缓存，造成了遍历需要更多的CPU周期。当然也有优点，例如在某个位置insert一个新的元素时，只要挪动部分指针的值就OK了。
一些操作的时间复杂度：
append:O(len(append_str))
insert:O(len(str) + len(insert_str))
tuple与list有什么区别？最重要的区别就是tuple是immutable，而list是mutable，
那么也就是说tuple大小将不会改变，就不用像list那样搞预分配了，更节省内存。
分别遍历list和tuple，跑得的时间是6.925s和6.771s从实测看来，这个结论是不明显的。
list和tuple在c实现上是很相似的，对于元素数量大的时候，都是一个数组指针，指针指向相应的对象，找不到tuple比list快的理由。但对于小对象来说，tuple会有一个对象池，所以小的、重复的使用tuple还有益处的。
为什么要有tuple，还有很多的合理性。实际情况中的确也有不少大小固定的列表结构，例如二维地理坐标等；另外tuple也给元素天然地赋予了只读属性。
认为tuple比list快的人大概是把python的tuple和list类比成C++中的数组和列表了。
dict()
字典是python中最通用的数据结构之一。dict可以将一组唯一的键映射到相应的值。
我们也可以用前面列表推导的方式来创建一个字典。
在遍历字典元素时，有一点需要特别注意。字典里的keys(), values()和items()3个方法的返回值不再是列表，而是视图对象（view objects）。
keys(): 返回dict_keys对象，可以查看字典所有键
values():返回dict_values对象，可以查看字典的所有值
items():返回dict_items对象，可以查看字典所有的{key, value}二元元组。
视图对象可以动态查看字典的内容，因此每次字典发生变化的时候，视图都会相应的改变，见下面这个例子：
视图无需冗余的将所有值都保存在内存中，像列表那样。但你仍然可以获取其长度（使用len）,也可以测试元素是否包含在其中（使用in子句）。当然，视图是迭代的。
实现细节
CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。
Python中所有不可变的内置类型都是可哈希的。可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。
字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).
操作 平均复杂度 平摊最坏情况复杂度
获取元素 O(1) O(n)
修改元素 O(1) O(n)
删除元素 O(1) O(n)
复制 O(n) O(n)
遍历 O(n) O(n)
还有一点很重要，在复制和遍历字典的操作中，最坏的复杂度中的n是字典曾经达到的最大元素数目，而不是当前的元素数目。换句话说，如果一个字典曾经元素个数很多，后来又大大减小了，那么遍历这个字典可能会花费相当长的事件。因此在某些情况下，如果需要频繁的遍历某个词典，那么最好创建一个新的字典对象，而不是仅在旧字典中删除元素。
字典的缺点和替代方案
使用字典的常见陷阱就是，它并不会按照键的添加顺序来保存元素的顺序。在某些情况下，字典的键是连续的，对应的散列值也是连续值（例如整数），那么由于字典的内部实现，元素的实现可能和添加的顺序相同：
但是，如果散列方法不同的其它数据类型，那么字典就不会保存元素顺序。
set()
集合是一种鲁棒性很好的数据结构，当元素顺序的重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，大部分情况下这种数据结构极其有用。
python的内置集合类型有两种：
set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象。
frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。
set里的元素必须是唯一的，不可变的。但是set是可变的，所以set作为set的元素会报错。
实现细节
CPython中集合和字典非常相似。事实上，集合被实现为带有空值的字典，只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。
由于这一点，可以快速的向集合中添加元素、删除元素、检查元素是否存在。平均时间复杂度为O(1),最坏的事件复杂度是O(n)。