dict和list的查找速度
為什么dict比list查找速度要快呢？list用索引查找只需要對應到位置就好了，這不是一步到位嗎？dict如果用hash查找，那還要把dict里的每一個hashcode和目標hash對比一遍，直到找到相等的，這樣不是花的時間更多嘛？
還有dict為什么占用內存大呢？
奶尤糯米團子
2020-05-21
2 回答
舉報
0/150
提交
取消
2020-07-11
樓上講的挺好的，數據結構里有一章節“查找”就是講這個的
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占用內存少。
希望此答案對你有所幫助