How to implement python dict

The dict object in Python indicates that it is a primitive Python data type, stored in the form of key-value pairs, and its Chinese name is translated into a dictionary. As the name suggests, it is very efficient to find the corresponding value through the key name. The time complexity is O(1) at the constant level.

dict underlying implementation (recommended learning: Python video tutorial）

In Python2, the bottom layer of dict is implemented by Hash Table, and the open address method is used to resolve conflicts.

So the time complexity of its search will be O(1).

Dict operation implementation principle (including insertion, deletion, and buffer pool, etc.)

First introduce: PyDictObject object element search strategy:

There are two search strategies, namely lookdict and lookdict_string. Lookdict_string is the special form of lookdict when searching for PyStringObject. Then the main logic of the general search strategy lookdict is:

(1) Search for the first entry:

a) Obtain the entry index according to the hash value

b) If the entry is in the unused state, the search ends; if the key pointed to by the entry is the same as the searched key If the keys are the same, the search is successful

c) If the current entry is in the dummy state, set freeslot (the freeslot here can be returned as the next immediately available address to store the entry)

d) Check the Active entry. If the value pointed to by the key is the same as the searched value, the search is successful

(2) Traverse and search the elements in the remaining detection chain:

a )According to the detection function used, obtain the next entry to be checked on the detection chain

b) An unused entry is detected, indicating that the search failed:

If the freeslot is not empty , then return freeslot; otherwise return unused entry

c) Check whether the key of entry is the same as the reference of the key being searched. If they are the same, the search is successful and return entry

d) Check entry Whether the value of the key is the same as the value of the searched key. If they are the same, the search is successful and entry

is returned. e) During the traversal process, if an entry in dummy state is found and freeslot is not set, set freeslot

Next is: Strategy for inserting and deleting elements of the PyDictObject object:

You need to use the search strategy first. If the search is successful, the value will be replaced directly. If the search fails, the entry in unused state or dummy state will be returned. Set the key, value and hash values, and adjust the size of ma_table according to the currently inserted elements (the adjustment is based on the loading rate, adjusted according to whether it is greater than 2/3); deletion is also similar, first calculate the hash value, and then Search the corresponding entry, the search is successful, delete the elements maintained in the entry, and change the entry from the Active state to the dummy state

In the implementation process of PyDictObject, the buffer pool will be used. When the PyDictObject object is destroyed, it begins to accept buffered PyDictObject objects. The number of objects that the defined buffer pool can accept is 80. When creating a new PyDictObject object, if there is one in the buffer pool, it can be taken out directly from the buffer pool. Use

For more Python-related technical articles, please visit the Python Tutorial column to learn!

The above is the detailed content of How to implement python dict. For more information, please follow other related articles on the PHP Chinese website!