CODEWITHSUNDEEP
pythonlistsearchdictionarytime-complexity
GniruT
GniruT

Reputation: 731

Is it faster to search in a dictionary than in a list?

I'm new to Python and I've noticed that there are 2 ways to search for a key in a dictionary:

d={1: 'a', 2: 'b',...}
if 1 in d: ...

or

if 1 in d.keys():

I thought they were the same but since I've had to search in a dictionary of 100 000 elements, I've seen that the second way takes too much time. I've looked for and read that this is so because d.keys() returns a list then the time complexity to search an element is O(n) but the complexity of search in a dictionary is O(1). Is that true?

Upvotes: 3

Views: 2151

Answers (1)

Anton
Anton

Reputation: 459

Yes, it is true. Most dictionaries are implemented as a hash-map. so you have O(1) for the access. that is much faster then O(n) for a list.

Why does it take just O(1)? Because a hash map hashes every key, and put it in the resulting bucket. If you search for a key, it will hash your input and look if there is a value. if there is a value it returns it, otherwise you get informed that there is no entry. just as a quick glance...

if you are interested in stuff like this, you should have a look in "introduction to algorithms" by cormen

Upvotes: 3

Related Questions