As it is in the comments and in the other answer, dictionaries in Python are a hash table with search time O (1) - and the information about it is here: link
That said, about the code design you ask - chave in dict
vs dict[chave]
: access time is the same - except that if the key does not exist, the second form raises an exception.
When you are going to recupear a value that is not sure if it exists in the dictionary the recommended is to use the .get
method:
meu_valor = dicionario.get("chave")
In this case, if "key" does not exist, .get
returns None and life goes on. The .get
also accepts a second parameter that is returned when the key does not exist, instead of None.
This saves lines of code - of type
if chave in dicionario:
valor = dicionario[chave]
else:
valor = None
or
try:
valor = dicionario[chave]
except KeyError:
valor = None
Of these, this second case would be the only one that would have any difference of performance, due to the creation time of the try / except context.
See also% method of% of% with% s: they not only retrieve a default value if there is no - but in this case, they assign the new value. For example, a loop to create a dictionary with all the words in a text and the position of each word within it in a list could be:
palavras = texto.split()
posicoes = {}
for indice, palavra in enumerate(palavras):
posicoes.setdefault(palavra, []).append(indice)
In this case, if the word has not yet been found, an empty list is created that is both assigned there and returned by the method. If .setdefault
already exists, the existing list is returned.
Now, since you're interested in this and want to know about binary search, here's the interesting fact: Python has a well-defined interface for mapping objects - and it's easy to implement an object that behaves exactly like a dictionary, but with the internal algorithms you decide on. If you want to create a dictionary that is internally a binary tree, it's pretty easy - the recommended way to do this is to inherit the
dict
class. There are several classes in
posicoes[palavra]
that are the basis for implementing very useful and varied data structures. A binary tree would have O (log (n)) search, but with the advantage that you can have the keys sorted and use slices in it, for example. Check out:
link
I have several "super-dictionaries" implemented in module collections.abc.MutableMapping
- some are more toy, others I use even in production:
link