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.
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.