5

What's the asymptotic complexity of dict.keys() in python?

I found this website but it does not have the answer. I am using Python 3, but I guess this is not version specific.

Alex Riley
  • 169,130
  • 45
  • 262
  • 238
Filip Haglund
  • 13,919
  • 13
  • 64
  • 113
  • 2
    It's `O(1)`, but requires one additional function call. – Ashwini Chaudhary Aug 24 '15 at 12:12
  • 6
    It is version specific in that with Python 2 `keys()` returns a list and in Python 3 it returns a dictionary view object. – Alex Riley Aug 24 '15 at 12:14
  • Are you looking at an operation in dict.keys() such as in or the generation itself of the dictionary view? – zom-pro Aug 24 '15 at 12:32
  • 1
    possible duplicate of [Python dictionary keys. "In" complexity](http://stackoverflow.com/questions/17539367/python-dictionary-keys-in-complexity) – zom-pro Aug 24 '15 at 12:32
  • 3
    I don't think this is a duplicate - the other question is about `in` on dicts, this is about the method itself. They're closely related but not the same. – Daenyth Aug 24 '15 at 12:53
  • I am using this to get a list or other iterator to go through the dict and delete some keys. Currently casting the result of .keys() to a list. – Filip Haglund Aug 24 '15 at 12:55

1 Answers1

7

In Python 3, dict.keys() returns a view object. Essentially, this is just a window directly onto the dictionary's keys. There is no looping over the hashtable to build a new object, for example. This makes calling it a constant-time, that is O(1), operation.

View objects for dictionaries are implemented starting here; the creation of new view objects uses dictview_new. All that this function does is create the new object that points back at the dictionary and increase reference counts (for garbage tracking).

In Python 2, dict.keys() returns a list object. To create this new list, Python must loop over the hashtable, putting the dictionary's keys into the list. This is implemented as the function dict_keys. The time complexity here is linear with the size of the dictionary, that is O(n), since every slot in the table must be visited.

N.B. dict.viewkeys() in Python 2 does the same as dict.keys() in Python 3.

Alex Riley
  • 169,130
  • 45
  • 262
  • 238