Implementation principle of Python dictionary

A few questions ？

• Python Inside dict and set How efficient is it ？
• Why are they disordered ？
• Why not all Pythoon Objects can be treated as dict Key or set Elements in ？
• Why? dict And set The order of elements depends on the order in which they are added , And why in the life cycle of the mapping object , This order is not invariable ？
• Why not in an iterative loop dict or set While adding elements ？

 

 

  Hash table of Dictionary

The hash table is a sparse array （ An array that always has blank elements ）.

The cells in a hash table are usually called table elements .dict In the hash table of , Each key value pair occupies a table element , Every table element has two parts , One is a reference to a key , One is a reference to a value .

 

Python Try to make sure that about one third of the table elements are empty ;

 

If you want to put an object in a hash table , First calculate the hash value of this element .（Python use hash Method ）;

 

Hash table algorithm

 

Adding new elements and updating existing key values are almost the same as above ;

The former will put a new element when it finds an empty table element ; For the latter , After finding the corresponding table element , The value object in the original table will be replaced with the new value .

 

When inserting a new value ,Python You may decide whether to reallocate memory to expand it according to the congestion of the hash table . Increased the size of the hash table , The number of bits occupied by the hash value and the number of bits used as an index will increase , The purpose is to reduce the probability of sending hash conflict .

 

 

dict Implementation and advantages and disadvantages of 【 The reality is to trade space for time 】

 

1、 Keys must be hashable

Hashable objects must meet the following requirements ：

1. Support hash() function , And pass __hash__() The hash value obtained by method is invariant ;
2. Supported by __eq__() Method to detect equality ;
3. if a==b It's true , be hash(a)==hash(b) It's true .

 

2、 Dictionaries are expensive in memory

Hash table used , And the hash table must be sparse , Resulting in inefficiency in space .

 

3、 Key queries are fast

Dictionary types have a huge memory overhead , But they provide fast access regardless of the size of the data .

 

4、 The order of the keys depends on the order of addition

When to dict When a hash conflict occurs when a new key is added to the , New keys may be scheduled to be stored in another location .

 

5、 Adding new keys to a dictionary may change the order of existing keys

Whenever you add a new key to the dictionary ,Python The interpreter may decide to expand the dictionary .

The result of the expansion is to create a larger hash table , And add the existing elements in the dictionary to the new table . New hash conflicts may occur , Causes the order of the keys in the new hash table to change .

 

 

remarks ：

    1、 Don't iterate and modify the dictionary at the same time

    2、dict.keys()、dict.values()、dict.items() What is returned is a dictionary view object , It's not a list . More like a collection , Can iterate .

 

 

example

# Try to modify the dictionary during the iteration 
for key, value in c.items():
if max_values == value:
if key == ignore_word:
del c[key]