dict和list的查找速度

为什么dict比list查找速度要快呢？list用索引查找只需要对应到位置就好了，这不是一步到位吗？dict如果用hash查找，那还要把dict里的每一个hashcode和目标hash对比一遍，直到找到相等的，这样不是花的时间更多嘛？

还有dict为什么占用内存大呢？

奶尤糯米团子

2020-05-21

源自：初识Python 6-3

关注问题我要回答

594

操作

收起

2 回答

kuo先生
2020-07-11

楼上讲的挺好的，数据结构里有一章节“查找”就是讲这个的

0 回复有任何疑惑可以回复我~

收起回答

qq_慕侠4234563
2020-05-22

python中list对象的存储结构采用的是线性表，如果你要输出list(10000),系统会从索引0逐个往下查找，知道查到索引为10000，才会输出，因此其查询复杂度为O(n),而dict对象的存储结构采用的是散列表(hash表)，它是随机性的与hash比对，一旦比对成功就返回value值，其在最优情况下一下就匹对成功，查询复杂度为O(1)，所以说dict比list查找速度快；

内存占用上，dict需要存key和value两项内容，而list只需存元素一项内容，相比之下，list比dict占用内存少。

希望此答案对你有所帮助