Python中list(set)操作的时间复杂度是否为O(1)？实现原理是什么？

Great question—this is a super common point of confusion when working with Python's hash table-based structures. Let’s break this down clearly:

First, let’s fix the dict.keys() misconception #

When folks say dict.keys() is O(1), they’re talking about the time to create the keys view object—not the time to iterate over all keys or turn them into a list. The dict_keys view isn’t a copy of the keys; it’s a dynamic "window" that points directly to the dictionary’s underlying hash table. Creating this window just requires a quick reference to existing data, so it’s constant-time.

But if you run list(dict.keys()), that’s still O(n)—because now you have to loop through every key in the hash table and add it to the new list. The O(1) only applies to making the view, not converting it.

Why list(set) is definitely O(n) #

Sets in Python use the same hash table structure as dictionaries (they just skip storing values alongside keys). When you call list(a) on a set a, Python has to do three things that all scale with the set’s size:

• Traverse every bucket in the set’s hash table
• Pull out every element stored in those buckets
• Add each element to a brand-new list

This means every single element in the set gets processed exactly once. If your set has n elements, that’s n operations—so the time complexity is O(n).

Take your example:

a = set(range(n))
s = list(a)

No matter how big n is, this will always be O(n). There’s no way to turn a set into a list without touching every element—after all, the list needs to contain all of them.

The underlying implementation breakdown #

Python’s hash tables for sets (and dicts) have buckets that might be empty or hold elements. When converting to a list, the interpreter loops through all buckets, checks if there’s an element present, and if so, adds it to the list. Even with empty buckets adding a tiny bit of overhead, the number of elements you need to process is directly tied to the set’s size—hence O(n) time.

Quick recap #

• dict.keys() is O(1) only for creating the view; converting that view to a list is still O(n)
• list(set) is always O(n) because it requires iterating through every element to build the list
• Both sets and dicts use hash tables, but the operations you’re comparing (making a view vs. building a list) have totally different goals and performance profiles

内容的提问来源于stack exchange，提问作者Pythoner