在字典中搜索比在列表中搜索更快吗？
Is it faster to search in a dictionary than in a list?
我是 Python 的新手，我注意到有两种方法可以在字典中搜索关键字：
d={1: 'a', 2: 'b',...}
if 1 in d: ...
或
if 1 in d.keys():
我认为它们是相同的，但由于我不得不在包含 100 000 个元素的字典中进行搜索，我发现第二种方法花费了太多时间。我一直在寻找并阅读这是因为 d.keys() returns 一个列表然后搜索元素的时间复杂度是 O(n) 但在字典中搜索的复杂度是 O(1) .是真的吗？
是的，这是真的。大多数字典都是作为哈希映射实现的。所以你有 O(1) 的访问权限。这比列表的 O(n) 快得多。
为什么只需要 O(1)？
因为哈希映射对每个键进行哈希处理，并将其放入生成的存储桶中。如果您搜索一个键，它会散列您的输入并查看是否有值。如果有一个值它 returns 它，否则你会被告知没有条目。快速浏览一下...
如果您对此类内容感兴趣，您应该看看 cormen
的 "introduction to algorithms"
我是 Python 的新手，我注意到有两种方法可以在字典中搜索关键字：
d={1: 'a', 2: 'b',...}
if 1 in d: ...
或
if 1 in d.keys():
我认为它们是相同的，但由于我不得不在包含 100 000 个元素的字典中进行搜索，我发现第二种方法花费了太多时间。我一直在寻找并阅读这是因为 d.keys() returns 一个列表然后搜索元素的时间复杂度是 O(n) 但在字典中搜索的复杂度是 O(1) .是真的吗？
是的，这是真的。大多数字典都是作为哈希映射实现的。所以你有 O(1) 的访问权限。这比列表的 O(n) 快得多。
为什么只需要 O(1)？ 因为哈希映射对每个键进行哈希处理，并将其放入生成的存储桶中。如果您搜索一个键，它会散列您的输入并查看是否有值。如果有一个值它 returns 它，否则你会被告知没有条目。快速浏览一下...
如果您对此类内容感兴趣，您应该看看 cormen
的 "introduction to algorithms"