Python 3中列表转集合的实现原理及时间复杂度分析

1. Python将列表转换为集合的底层机制 #

Python的集合基于哈希表实现，把列表转成集合时必须遍历整个列表的所有元素，不存在能跳过遍历的技巧，具体流程如下：

• 初始化一个空的哈希表结构（集合的底层存储）
• 逐个取出列表中的元素：
  1. 计算当前元素的哈希值；
  2. 根据哈希值定位哈希表中的对应位置：
     • 若位置为空，直接将元素插入该位置；
     • 若位置已有元素，会进行相等性检查：如果元素相同则跳过（去重），如果不同则通过开放寻址法等方式处理哈希冲突，找到合适位置插入。
• 遍历完成后，哈希表中的元素就构成了最终的集合。

2. 转换操作的算法复杂度 #

• 平均情况：O(n)，其中n是列表的长度。因为哈希表的单次插入操作平均时间复杂度为O(1)，遍历n个元素的总复杂度就是O(n)。
• 最坏情况：O(n²)。当所有元素的哈希值完全相同（极端哈希冲突场景），每次插入都需要遍历冲突区域的所有元素，单次插入复杂度变为O(n)，总复杂度也就变成了O(n²)。不过这种情况在实际应用中几乎不会出现。

内容的提问来源于stack exchange，提问作者Kevin Flowers Jr