6

I read from python3 document, that python use hash table for dict(). So the search time complexity should be O(1) with O(N) as the worst case. However, recently as I took a course, the teacher says that happens only when you use int as the key. If you use a string of length L as keys the search time complexity is O(L).

I write a code snippet to test out his honesty

import random
import string
from time import time
import matplotlib.pyplot as plt

def randomString(stringLength=10):
    """Generate a random string of fixed length """
    letters = string.ascii_lowercase
    return ''.join(random.choice(letters) for i in range(stringLength))

def test(L):
    #L: int length of keys

    N = 1000 # number of keys
    d = dict()
    for i in range(N):
        d[randomString(L)] = None

    tic = time()
    for key in d.keys():
        d[key]
    toc = time() - tic

    tic = time()
    for key in d.keys():
        pass
    t_idle = time() - tic

    t_total = toc - t_idle
    return t_total

L = [i * 10000 for i in range(5, 15)]
ans = [test(l) for l in L]

plt.figure()
plt.plot(L, ans)
plt.show()

The result is very interesting. As you can see, the x-axis is the length of the strings used as keys and the y-axis is the total time to query all 1000 keys in the dictionary.

enter image description here

Can anyone explain this result?

Please be gentle on me. As you can see, if I ask this basic question, that means I don't have the ability to read python source code or equivalently complex insider document.

3
  • 2
    Rather than force every single person to read the code, try to understand what you're doing, and then divine what the graph axes are, could you just explain what the graph axes are, and what your interpretation of this data is?
    – jarmod
    Commented Mar 3, 2020 at 18:36
  • I read it as - X-axis is the length of a key.. and Y-axis is time taken to search
    – ajayramesh
    Commented Mar 3, 2020 at 18:41
  • How is that result very interesting? Commented Mar 3, 2020 at 18:41

2 Answers 2

10

Since a dictionary is a hashtable, and looking up a key in a hashtable requires computing the key's hash, then the time complexity of looking up the key in the dictionary cannot be less than the time complexity of the hash function.

In current versions of CPython, a string of length L takes O(L) time to compute the hash of if it's the first time you've hashed that particular string object, and O(1) time if the hash for that string object has already been computed (since the hash is stored):

>>> from timeit import timeit
>>> s = 'b' * (10**9) # string of length 1 billion
>>> timeit(lambda: hash(s), number=1)
0.48574538500002973 # half a second
>>> timeit(lambda: hash(s), number=1)
5.301000044255488e-06 # 5 microseconds

So that's also how long it takes when you look up the key in a dictionary:

>>> s = 'c' * (10**9) # string of length 1 billion
>>> d = dict()
>>> timeit(lambda: s in d, number=1)
0.48521506899999167 # half a second
>>> timeit(lambda: s in d, number=1)
4.491000026973779e-06 # 5 microseconds

You also need to be aware that a key in a dictionary is not looked up only by its hash: when the hashes match, it still needs to test that the key you looked up is equal to the key used in the dictionary, in case the hash matching is a false positive. Testing equality of strings takes O(L) time in the worst case:

>>> s1 = 'a'*(10**9)
>>> s2 = 'a'*(10**9)
>>> timeit(lambda: s1 == s2, number=1)
0.2006020820001595

So for a key of length L and a dictionary of length n:

  • If the key is not present in the dictionary, and its hash has already been cached, then it takes O(1) average time to confirm it is absent.
  • If the key is not present and its hash has not been cached, then it takes O(L) average time because of computing the hash.
  • If the key is present, it takes O(L) average time to confirm it is present whether or not the hash needs to be computed, because of the equality test.
  • The worst case is always O(nL) because if every hash collides and the strings are all equal except in the last places, then a slow equality test has to be done n times.
2
  • Thanks! Does that mean hash() function has some kind of cache? Like what @lru_cache() does?
    – River
    Commented Mar 3, 2020 at 18:49
  • 1
    I imagine the cached hash is stored in the string object itself, rather than elsewhere. It wouldn't really make sense to use a dictionary to cache the hashes of objects, because you'd need to compute their hashes to check the cache anyway.
    – kaya3
    Commented Mar 3, 2020 at 18:54
2

only when you use int as the key. If you use a string of length L as keys the search time complexity is O(L)

Just to address a point not covered by kaya3's answer....

Why people often say a hash table insertion, lookup or erase is a O(1) operation.

For many real-world applications of hash tables, the typical length of keys doesn't tend to grow regardless of how many keys you're storing. For example, if you made a hash set to store the names in a telephone book, the average name length for the first 100 people is probably very close to the average length for absolutely everyone. For that reason, the time spent to look for a name is no worse when you have a set of ten million names, versus that initial 100 (this kind of analysis normally ignores the performance impact of CPU cache sizes, and RAM vs disk speeds if your program starts swapping). You can reason about the program without thinking about the length of the names: e.g. inserting a million names is likely to take roughly a thousand times longer than inserting a thousand.

Other times, an application has a hash tables where the key may vary significantly. Imagine say a hash set where the keys are binary data encoding videos: one data set is old Standard Definition 24fps video clips, while another is 8k UHD 60fps movies. The time taken to insert these sets of keys won't simply be in the ratio of the numbers of such keys, because there's vastly different amounts of work involved in key hashing and comparison. In this case - if you want to reason about insertion time for different sized keys, a big-O performance analysis would be useless without a related factor. You could still describe the relative performance for data sets with similar sized keys considering only the normal hash table performance characteristics. When key hashing times could become a problem, you may well want to consider whether your application design is still a good idea, or whether e.g. you could have used a set of say filenames instead of the raw video data.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.