Python 中的set, list 和 dict

分析对比一下这几种数据结构查找的时间复杂度，原因是最近面试了几个人，有些开发经验，但是都没有回答的很好。

这里写一段代码对比一下：

In [1]: l = list(range(100000))

In [2]: s = set(range(100000))

In [3]: d = dict(zip(range(100000), range(100000)))

In [4]: %timeit 99999 in l
1.06 ms ± 9.94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]: %timeit 99999 in s
46.4 ns ± 0.255 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [6]: %timeit d.get(99999)
115 ns ± 0.937 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

1ms = 1000000ns，可以看出，列表和集合字典的查找时间绝对不在一个量级上，特别是在数据量很大的情况下。由于在 Python 中 set 和 dict 都是通过 hash 的方式实现的，所以查找的时间复杂度是 O(1)，而列表的时间复杂度则是 O(n)。