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 ：
-
Support hash() function , And pass __hash__() The hash value obtained by method is invariant ;
-
Supported by __eq__() Method to detect equality ;
-
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]
