The dict object in Python is a primitive Python data type, stored as a key-value pair, whose Chinese name translates to dictionary, and as the name implies, it is highly efficient at finding the corresponding value by key name, with a time complexity at the constant level of O(1).
dict underlying implementation
In Python2, the underlying dict relies on a Hash Table implementation, which uses the open address method to resolve conflicts.
So the time complexity of the lookup will be O(1).
The principle of Dict operation implementation (including insertion, deletion, and buffer pooling, etc.)
First of all: the element search strategy for PyDictObject objects.
There are two search strategies, lookdict and lookdict_string. lookdict_string is the special form of lookdict when searching for PyStringObject, then the main logic of the generic search strategy lookdict is.
(1) The lookup for the first entry.
a) get the index of entry according to the hash value
b) if the entry is in the unused state, the search is over; if the key pointed to by the entry is the same as the search key, the search is successful
c) if the current entry is in the dummy state, set the freeslot (here the freeslot is returned as the next immediately available address to store the entry)
d) check the active state of entry, if the value pointed to by the key and the value of the search is the same, the search is successful
(2) the traversal of the remaining elements of the probe chain to find.
a) according to the detection function used to obtain the next entry to be checked on the detection chain
b) check an entry in the unused state, indicating that the search failed.
If freeslot is not empty, then return freeslot; otherwise return the entry in the unused state
c) check whether the key of entry and the reference of the key searched, the same search success, return entry
d) check whether the key of entry and the value of the searched key is the same, the same search is successful, return entry
e) traversal process, found dummy state entry, and freeslot is not set, then set freeslot
The next is: PyDictObject object element insertion and deletion strategy.
Need to first use the search strategy, search success, then directly replace the value, search failure, return to the unused state or dummy state entry, set the key, value and hash value, and according to the current inserted elements to adjust the size of the ma_table (the basis for adjustment is the loading rate, according to whether it is greater than 2/3 to adjust). Deletion is similar, first calculate the hash value, then search for the corresponding entry, and if the search is successful, delete the elements maintained in the entry, and modify the entry from the active state to the dummy state.
In the process of PyDictObject implementation, the buffer pool is used. When the PyDictObject object is destroyed, it starts to accept the buffered PyDictObject objects, and the number of objects that can be accepted by the defined buffer pool is 80. When creating a new PyDictObject, if there is one in the buffer pool, it can be taken out from the buffer pool directly.