list, tuple, dictionary, set的底层细节
列表实现细节
python中的列表的英文名是list，因此很容易和其它语言(C++, Java等)标准库中常见的链表混淆。事实上CPython的列表根本不是列表（可能换成英文理解起来容易些：python中的list不是list）。在CPython中，列表被实现为长度可变的数组。可参考《Python高级编程（第2版）》
从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。
这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。不幸的是，在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。
利用 list.insert(i,item) 方法在任意位置插入一个元素——复杂度O(N) 利用 list.pop(i) 或 list.remove(value) 删除一个元素——复杂度O(N)
| 操作 | 复杂度 |
|---|---|
| 复制 | O(N) |
| 添加元素(在尾部添加) | O(1) |
| 插入元素(在指定位置插入) | O(N) |
| 获取元素 | O(1) |
| 修改元素 | O(1) |
| 删除元素 | O(N) |
| 遍历 | O(N) |
| 获取长度为k的切片 | O(k) |
| 删除切片 | O(N) |
| 列表扩展 | O(k) |
| 测试是否在列表中 | O(N) |
| min()/max() | O(n) |
| 获取列表长度 | O(1) |
字典实现细节
CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。
Python中所有不可变的内置类型都是可哈希的。可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。
字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).
字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为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是字典曾经达到的最大元素数目，而不是当前的元素数目。换句话说，如果一个字典曾经元素个数很多，后来又大大减小了，那么遍历这个字典可能会花费相当长的事件。因此在某些情况下，如果需要频繁的遍历某个词典，那么最好创建一个新的字典对象，而不是仅在旧字典中删除元素。
集合实现细节
集合是一种鲁棒性很好的数据结构，当元素顺序的重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，大部分情况下这种数据结构极其有用。
python的内置集合类型有两种：
set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象。
frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。
CPython中集合和字典非常相似。事实上，集合被实现为带有空值的字典，只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。
由于这一点，可以快速的向集合中添加元素、删除元素、检查元素是否存在。平均时间复杂度为O(1),最坏的事件复杂度是O(n)。
哈希函数
- 哈希函数就是一个映射，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可；
- 并不是所有的输入都只对应唯一一个输出，也就是哈希函数不可能做成一个一对一的映射关系，其本质是一个多对一的映射，这也就引出了下面一个概念–冲突。
只要不是一对一的映射关系，冲突就必然会发生
冲突解决方法（python所使用的）开放地址
线性探测再散列
例如 哈希函数为： H（key） = key %11,key 为关键字，采用开放地址法中的线性探测再散列解决冲突，依次输入
9 个关键字，19，01，23，14，55，68，11，82，36，构造哈希表（表长=11）
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 55 | 01 | 23 | 14 | 68 | 11 | 82 | 36 | 19 | ||
| 探测次数 | 1 | 1 | 2 | 1 | 3 | 6 | 2 | 5 | 1 |
如上表，例如 14%11=3，将14放入3号位置，11%11 = 0，将11放入0号位置，而此时3号位已经有元素。
就顺着表往后放，直到5号没有元素，11放入5号。
二次探测再散列
例如 哈希函数为： H（key） = key %11,key 为关键字，采用开放地址法中的二次探测再散列解决冲突，依次输入
9 个关键字，19，01，23，14，55，68，11，82，36，构造哈希表（表长=11）
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 55 | 01 | 23 | 14 | 36 | 82 | 68 | 19 | 11 | ||
| 探测次数 | 1 | 1 | 2 | 1 | 2 | 1 | 4 | 1 | 3 |
对于01%11=1，将01放入1号位置， 11%11=0，此时0号位置已经有元素，
则查找 0 + 1^2 = 1,有元素
查找 0 - 1^2 = -1 ,没有则放入，如果还有元素则查找0 + 2^2, 0-2^2…. 0+k^2, 0 - k^2。
扩展（哈希冲突解决方法）
开放地址
开放地址的意思是除了哈希函数得出的地址可用，当出现冲突的时候其他的地址也一样可用，常见的开放地址思想的方法有线性探测再散列，二次探测再散列，这些方法都是在第一选择被占用的情况下的解决方法。
再哈希法
这个方法是按顺序规定多个哈希函数，每次查询的时候按顺序调用哈希函数，调用到第一个为空的时候返回不存在，调用到此键的时候返回其值。
链地址法
将所有关键字哈希值相同的记录都存在同一线性链表中，这样不需要占用其他的哈希地址，相同的哈希值在一条链表上，按顺序遍历就可以找到。
公共溢出区
其基本思想是：所有关键字和基本表中关键字为相同哈希值的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
装填因子α
一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为表中填入的记录数和哈希表长度的壁纸，也就是标志着哈希表的装满程度。直观看来，α越小，发生冲突的可能性就越小，反之越大。一般0.75比较合适，涉及数学推导。