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.

Related articles

Can python replace JavaScript?

python can replace JavaScript; Pyjamas can be used to achieve Python instead of JavaScript, Pyjamas is a Python ajax development framework that can be used instead of HTML and JavaScript to write web applications , you can reuse and import classes and mod

Python+AI to colorize old photos

Colorize old photos with NoGAN's image enhancement technique.NoGAN is a new type of GAN that takes the least amount of time for GAN training.

python reverse Dict

A very common dictionary task is if we have a dictionary and want to flip its keys and values, the keys will become the values and the values will become the keys

Pyecharts Draws Visual Earth

Here we use the global dataset of the number of new crown infections as our test data, let's first look at the data as a whole import pandas as pd df = pd.read_csv("owid-covid-data.csv") df_0608 = df[df['date'] == '2022-06-08']

Python Retry Mechanism

To avoid functional problems caused by some network or other uncontrollable factors, such as. For example, when sending a request, there will be a request timeout problem often due to network instability.

How do you make Python code more professional?

Write your own code only for yourself to see, in fact, how to write. Once you have a team to work with, or to share your code, you have to write it properly, and professional code can accumulate technical influence for yourself.

Merge two or more dict

Suppose we have two or more dict and we want to merge them all into a single dict with a unique key

Mapping lists to dictionaries

The last task of the list code snippet, if given a list and mapping it to a dictionary, that is, we want to convert our list to a dictionary with numeric keys