Clever Geek Handbook

Does Python optimize dictionary searches under the hood?

For example:

d = {"John": "Doe", "Paul": "Allen", "Bill": "Gates"}

Just imagine it had several thousand / million such names, all unique by name.

If I wanted to know if the "Paul" key exists, what does it do under the hood?

+3


source to share


2 answers


Python's dictionary implementation reduces the average dictionary lookup complexity to O (1) by requiring key objects to provide a hash function. Such a hash function takes information in a key object and uses it to create an integer called a hash value. This hash value is then used to determine which bucket this (key, value) pair should be placed in. The pseudocode for this search function might look something like this:

def lookup(d, key):
    '''dictionary lookup is done in three steps:
       1. A hash value of the key is computed using a hash function.

       2. The hash value addresses a location in d.data which is
          supposed to be an array of "buckets" or "collision lists"
          which contain the (key,value) pairs.

       3. The collision list addressed by the hash value is searched
         sequentially until a pair is found with pair[0] == key. The
         return value of the lookup is then pair[1].
   '''
   h = hash(key)                  # step 1
   cl = d.data[h]                 # step 2
   for pair in cl:                # step 3
       if key == pair[0]:
           return pair[1]
   else:
       raise KeyError, "Key %s not found." % key


From Python Wiki

+4


source


Python dictionaries are implemented using a hash table. So the search is O (1) on average (depending on the strength of your hash function).

Literature:



+1


source






More articles:


All Articles