algorithm - How do Python dictionary hash lookups work?

Question

How do Python dictionary lookup algorithms work internally?

mydi['foo'] 

If the dictionary has 1,000,000 terms, is a tree search executed? Would I expect performance in terms of the length of the key string, or the size of the dictionary? Maybe stuffing everything into a dictionary is just as good as writing a tree search index for strings of size 5 million?

Answer 1

Here's some pseudo-code closer to what actually happens. Imagine the dictionary has a data attribute containing the key,value pairs and a size which is the number of cells allocated.

def lookup(d, key):
    perturb = j = hash(key)
    while True:
        cell = d.data[j % d.size]
        if cell.key is EMPTY:
            raise IndexError
        if cell.key is not DELETED and (cell.key is key or cell.key == key):
            return cell.value
        j = (5 * j) + 1 + perturb
        perturb >>= PERTURB

The perturb value ensures that all bits of the hash code are eventually used when resolving hash clashes but once it has degraded to 0 the (5*j)+1 will eventually touch all cells in the table.

size is always much larger than the number of cells actually used so the hash is guaranteed to eventually hit an empty cell when the key doesn't exist (and should normally hit one pretty quickly). There's also a deleted value for a key to indicate a cell which shouldn't terminate the search but which isn't currently in use.

As for your question about the length of the key string, hashing a string will look at all of the characters in the string, but a string also has a field used to store the computed hash. So if you use different strings every time to do the lookup the string length may have a bearing, but if you have a fixed set of keys and re-use the same strings the hash won't be recalculated after the first time it is used. Python gets a benefit from this as most name lookups involve dictionaries and a single copy of each variable or attribute name is stored internally, so every time you access an attribute x.y there is a dictionary lookup but not a call to a hash function.