If I have a dictionary in Python, what is the time complexity of searching for a non-existent key?
d = {}
if key not in d:
print "Key not found!"
Does in do a linear search across the array of keys?
Is there an O(1) implementation of searching a data structure for a particular string? Effectively for a contains() method.
It must be amortised O(1) for a dictionary, because in the end the in operator is just performing a membership lookup, the not doesn't have an additional overhead on that. Take a look at this answer for further details regarding the time complexity of the in operator in the case of a dictionary.
It's O(1) dictionary is implemented as a hash table and in does hash table lookup
Dictionaries are usually O(1) for lookups.
It's perfectly acceptable to have a class that returns a constant for it's hash, but this degrades dictionary lookups to be linear.
eg.
class dumbint(int):
def __hash__(self):
return 0
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(100)}' 'dumbint(-1) in d'
100000 loops, best of 3: 3.64 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(1000)}' 'dumbint(-1) in d'
10000 loops, best of 3: 31.7 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(10000)}' 'dumbint(-1) in d'
1000 loops, best of 3: 803 usec per loop
strings have a good hash function, so you'll get O(1) lookups for exact matches. Searching for a substring in the keys is a much more difficult problem.
