Is a Python dictionary as efficient as a tree or a hash?

Question

I use a lot of Python dictionaries:

dic = dict() #ou
dic = {}

dic['113654'] = {'nome': 'João', 'idade': 21}
dic['853872'] = {'nome': 'Maria', 'idade': 27}
dic['427845'] = {'nome': 'Fernando', 'idade': 33}
dic['720720'] = {'nome': 'Lucas', 'idade': 16}

They make it very easy to check if a key exists and take its value:

cod = '853872'
if cod in dic:
    return dic[cod]

My question is: is using dictionaries that way efficient? Python dictionaries implement an efficient way to find keys (hash, tree, etc.)? Or when my dictionary gets too big you should use a more traditionally efficient data structure like a tree or a hash for example?

Answer 1

The internal implementation of the Python dictionary is using tables hash, then has complexity O(1) to find keys, this can be confirmed in official Python wiki (thanks to Alexciuffa).

It is, in theory, and in almost all situations, faster than a tree that has O(log n) complexity, but it cannot have the keys naturally classified as a tree can, and cannot have repeated keys. A dictionary was not "ordained". According to the jsbueno below in comment it can now be ordered using an auxiliary structure, so it keeps O(1) for access to the element and manages to traverse all elements in the order they were inserted, at the cost of taking up more space that could, Which for Python is not a big deal because I’ve done this before. It is still unclassified and could only be so efficiently with a tree or something like that.