Python部分底层原理

列表sort()排序实现引用，浅拷贝，深拷贝列表的引用深浅拷贝 字典底层实现集合元素的查找总结

列表sort()排序实现

list.sort()内部实现机制为：Timesort

Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用（TimSort 是 Python 中 list.sort 的默认实现）。该算法找到数据中已经排好序的块-分区，每一个分区叫一个run，然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序，现在Java SE7和Android也采用Timsort算法对数组排序。

最坏时间复杂度为：O(n logn)

空间复杂度为：O(n)

引用，浅拷贝，深拷贝

列表的引用

# 定义一个新列表 l1 = [1, 2, 3, 4, 5] # 对l2赋值 l2 = l1 print(l1) l2[0] = 100 print(l1)

示例结果：

[1, 2, 3, 4, 5] [100, 2, 3, 4, 5]

l2与l1指向同一片内存空间

深浅拷贝

如果想复制l1的值，对l2进行操作不影响l1，就需要进行浅拷贝或者深拷贝。

浅拷贝：如果列表中的元素中没有列表或者字典，有如下方法可以进行浅拷贝：l2 = l1[:] //1.利用切片 l2 = copy.copy(l1) //2.import copy模块 l3 = list(l1) //3.使用列表生成方法 //4.建立空列表，使用extend方法 l2 = [] l2.extend(l1) //5.列表生成式： [i for i in l1] 深拷贝：同样的引用机制，元素中出现列表时，想要复制所有的数据，需要进行深拷贝：l2 = copy.deepcopy(l1) //import copy模块

字典底层实现

首先，在内存中开出一块儿不小的空间，也就是相当于C或者Java中的数组，Python中的列表，记录下其首地址。现在要存入{name：张放放}字典，Java中叫Map，通过哈希函数（散列函数）将"name"映射为一个数值，比如，按照字母的ascall码值相加，得到一个数值，将其对数组长度取余数，作为数组下标，将{name:张放放}，对键的引用和对值的引用分开存入。但是这里可能有一个问题 ，如果要存入的键B哈希后取模的地址已经存放了数值A，那么应该怎么处理？首先进行A和B的匹配，如果发现A的键与B的键是相同的，这个时候B的value会覆盖A的value，如果发现A.key!=B.key,那么继续往下一个地址去看，直到找到一个空的地址然后存入。这也就是set与dict都没有重复元素的原因。查找的时候，计算出要查找的"name"的哈希值，找数组下标，开始匹配键key，匹配到后拿出。

集合元素的查找

set存储原理与字典相同，但是只存入一个内容，没有键值对。也无法重复存放。

总结

不同于C++中map与set实现用红黑树，插入，查找和删除都可以在logn的时间复杂度完成，Python中的字典与集合底层依靠哈希表(hash table)实现, 使用开放寻址法解决冲突,实现插入和查找的O₍₁₎复杂度。但是相应的总有空白元素的数组, Python至少保证1/3的数组是空的，也就是用空间来换取时间的一种方法。 【参考文章】

[1] Python列表赋值，复制，深拷贝以及5种浅拷贝详解[2] python字典实现原理-哈希函数-解决哈希冲突方法[3] Set中的元素为什么不允许重复[4] python sort函数内部实现原理