2

I don't fundamentally understand why searching for a key in dictionary is faster than iterating through the keys of a dictionary to find a matching key. I imagine that when searching for a key in python with something like key in dict the background code will be iterating through keys to look for matches. So why would it be slower to do this manually with something like for i in dict: key == i?

The Nightman
  • 5,609
  • 13
  • 41
  • 74
  • "I imagine that when searching for a key in python with something like `key in dict` the background code will be iterating through keys to look for matches" - [you imagine wrong](https://en.wikipedia.org/wiki/Hash_table). – user2357112 Mar 01 '17 at 01:07
  • 1
    [Sorting and Searching](https://www.amazon.com/dp/0201896850). With the appropriate choice of algorithms and data structures, you can find stuff in log(n) or less. – jww Mar 01 '17 at 01:09
  • 1
    See also [here](http://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table) and many other questions about how dictionary/set lookups are implemented in terms of performance. – TigerhawkT3 Mar 01 '17 at 01:11

2 Answers2

4

Because dictionaries in python are implemented using hash tables. Think something similar to indices in a relational database, which make key seeking operations faster.

Reference

JavoSN
  • 464
  • 3
  • 12
3

You imagine incorrectly: searching for a single key uses a hashing function, so it's an indirect reference (two-step computation) to the needed location in memory. Think of it as an array reference of the form

array[hash_function(key)]
Prune
  • 76,765
  • 14
  • 60
  • 81