python dict 和 list 的速度问题

[yangmt92]

初学 python 我不能理解 dict 为什么比 list 快

比如 list[5]是从头遍历 那么 dict['key']不是对 key 的遍历吗

[polo2222]

dict['key']不是对 key 的遍历。

python dict 的实现使用了 hash 表， access 的复杂度是 O(1)。

[justfly]

list[5] 也不是遍历 也是 O(1)

[justfly]

ps 只有链表随机读才需要从头遍历

[BOYPT]

先问是不是,再问为什么系列

[kfll]

楼主理解的不对，是查询表上， dict 会比 list 快，你可以类比一下数据库有索引和没有索引的情况。

https://wiki.python.org/moin/TimeComplexity

应该比较 list 的 x in s 和 set 的 x in s 或者 dict 的 Get Item

[yangmt92]

@kfll 对，我是这个意思。刚刚看了一下哈希初步明白了。 dict 的 x in s 是 position = f(key),O(1)。 list 的 x in s ,O(N)

[jugelizi]

dict 就是查字典的意思嘛，你按索引查字典和一页一翻你说哪个快

[yangmt92]

@polo2222 多谢提醒哈希

[yangmt92]

@jugelizi 又有一点迷惑了，到底是一个 f(x)生成，还是索引，字典索引相当根据特征于分类查询

[yangmt92]

@jugelizi 不过还是快，可能我需要了解一下 dict 或者哈希实现